Primer Design through Submodular Function Estimation
- 30 June 2026
- journal article
- Published by Oxford University Press (OUP) in Bioinformatics
- Vol. 42 (7)
Abstract
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.Keywords
Funding Information
- Agricultural Research Service (6064-32000-001-009S)
- Agricultural Research Service (58-6064-4-016)
- Florida State University
This publication has 17 references indexed in Scilit:
- A tool to automatically design multiplex PCR primer pairs for specific targets using diverse templatesScientific Reports, 2023
- Designing highly multiplex PCR primer sets with Simulated Annealing Design using Dimer Likelihood Estimation (SADDLE)Nature Communications, 2022
- Multiobjective optimization-driven primer design mechanism: towards user-specified parameters of PCR primerBriefings in Bioinformatics, 2022
- Nextstrain: real-time tracking of pathogen evolutionBioinformatics, 2018
- Diagnostics based on nucleic acid sequence variant profiling: PCR, hybridization, and NGS approachesAdvanced Drug Delivery Reviews, 2016
- Coming of age: ten years of next-generation sequencing technologiesNature Reviews Genetics, 2016
- PrimerStation: a highly specific multiplex genomic PCR primer design server for the human genomeNucleic Acids Research, 2006
- MuPlex: multi-objective multiplex PCR assay designNucleic Acids Research, 2005
- MultiPLX: automatic grouping and evaluation of PCR primersBioinformatics, 2004
- MAFFT: a novel method for rapid multiple sequence alignment based on fast Fourier transformNucleic Acids Research, 2002