Yixin Chen
Yixin Chen has a total of 6 co-authors. Here are the top co-authors by number of shared publications:
- Alan Kuhnle
University of Florida
2 shared publications - Aaron Hong
University of Florida
1 shared publication - Adam R. Rivers
United States Department of Agriculture, Agricultural Research Service
1 shared publication - Ao Wang
Herbert Wertheim College of Engineering, University of Florida Department of Computer and Information Science and Engineering Gainesville, FL
1 shared publication - Christina Boucher
University of Florida
1 shared publication - Yunheng Han
Herbert Wertheim College of Engineering, University of Florida Department of Computer and Information Science and Engineering Gainesville, FL
1 shared publication
Latest Publications
- 30 June 2026
- Published by Oxford University Press (OUP) in Bioinformatics
- Vol. 42 (7)
Primer Design through Submodular Function Estimation
Motivation: Multiplex PCR-based enrichment is widely used in viral genome sequencing and pathogen surveillance. However, designing large sets of primers that maximize genome coverage while minimizing primer–primer interactions remains a major computational challenge. Existing methods such as SADDLE and Olivar use heuristics to optimize a Badness score for primer dimers but lack theoretical guarantees on solution quality. Results: We introduce PRISM, a new framework that formulates multiplex primer design as a constrained submodular maximization problem. Our method defines an objective that balances genome coverage and dimer risk, and applies a local search algorithm with a constant-factor approximation guarantee. Evaluations on viral genome datasets demonstrate that PRISM consistently achieves lower Badness scores compared to PrimalScheme, Olivar, and primerJinn. These results highlight the scalability and theoretical rigor of submodular optimization in primer design. Availability: PRISM is open-source and available at https://github.com/yhhan19/PRISM-new. The experimental data, scripts, and results used in this paper are archived on Figshare at https://doi.org/10.6084/m9.figshare.32806499. Supplementary information: Supplementary information: Supplementary material, including proofs and figures, is available at Bioinformatics online and on Figshare at https://doi.org/10.6084/m9.figshare.32806499.
- 30 June 2026
- Published by Oxford University Press (OUP) in Bioinformatics
- Vol. 42 (7)
Primer Design through Submodular Function Estimation
Motivation: Multiplex PCR-based enrichment is widely used in viral genome sequencing and pathogen surveillance. However, designing large sets of primers that maximize genome coverage while minimizing primer–primer interactions remains a major computational challenge. Existing methods such as SADDLE and Olivar use heuristics to optimize a Badness score for primer dimers but lack theoretical guarantees on solution quality. Results: We introduce PRISM, a new framework that formulates multiplex primer design as a constrained submodular maximization problem. Our method defines an objective that balances genome coverage and dimer risk, and applies a local search algorithm with a constant-factor approximation guarantee. Evaluations on viral genome datasets demonstrate that PRISM consistently achieves lower Badness scores compared to PrimalScheme, Olivar, and primerJinn. These results highlight the scalability and theoretical rigor of submodular optimization in primer design. Availability: PRISM is open-source and available at https://github.com/yhhan19/PRISM-new. The experimental data, scripts, and results used in this paper are archived on Figshare at https://doi.org/10.6084/m9.figshare.32806499. Supplementary information: Supplementary information: Supplementary material, including proofs and figures, is available at Bioinformatics online and on Figshare at https://doi.org/10.6084/m9.figshare.32806499.
- Open Access
- 4 August 2023
- Published by Association for Computing Machinery (ACM)
- p. 250-261
Approximation Algorithms for Size-Constrained Non-Monotone Submodular Maximization in Deterministic Linear Time
In this work, we study the problem of finding the maximum value of a non-negative submodular function subject to a limit on the number of items selected, a ubiquitous problem that appears in many applications, such as data summarization and nonlinear regression. We provide the first deterministic, linear-time approximation algorithms for this problem that do not assume the objective is monotone. We present three deterministic, linear-time algorithms: a single-pass streaming algorithm with a ratio of 23.313 + ε, which is the first linear-time streaming algorithm; a simpler deterministic linear-time algorithm with a ratio of 11.657; and a (4 + O(ε))-approximation algorithm. Finally, we present a deterministic algorithm that obtains ratio of e + ε in O_ε (n log(n)) time, close to the best known expected ratio of e - 0.121 in polynomial time.
- 4 August 2023
- Published by Association for Computing Machinery (ACM)
- p. 250-261
Open AccessApproximation Algorithms for Size-Constrained Non-Monotone Submodular Maximization in Deterministic Linear Time
In this work, we study the problem of finding the maximum value of a non-negative submodular function subject to a limit on the number of items selected, a ubiquitous problem that appears in many applications, such as data summarization and nonlinear regression. We provide the first deterministic, linear-time approximation algorithms for this problem that do not assume the objective is monotone. We present three deterministic, linear-time algorithms: a single-pass streaming algorithm with a ratio of 23.313 + ε, which is the first linear-time streaming algorithm; a simpler deterministic linear-time algorithm with a ratio of 11.657; and a (4 + O(ε))-approximation algorithm. Finally, we present a deterministic algorithm that obtains ratio of e + ε in O_ε (n log(n)) time, close to the best known expected ratio of e - 0.121 in polynomial time.