{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,17]],"date-time":"2026-07-17T16:08:38Z","timestamp":1784304518842,"version":"3.55.0"},"reference-count":24,"publisher":"Oxford University Press (OUP)","issue":"7","funder":[{"DOI":"10.13039\/100007917","name":"USDA Agricultural Research Service","doi-asserted-by":"publisher","award":["6064-32000-001-009S"],"award-info":[{"award-number":["6064-32000-001-009S"]}],"id":[{"id":"10.13039\/100007917","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100007917","name":"USDA Agricultural Research Service","doi-asserted-by":"publisher","award":["58-6064-4-016"],"award-info":[{"award-number":["58-6064-4-016"]}],"id":[{"id":"10.13039\/100007917","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006597","name":"University of Florida","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006597","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026,7,2]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:sec>\n                    <jats:title>Motivation<\/jats:title>\n                    <jats:p>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\u2013primer 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.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Results<\/jats:title>\n                    <jats:p>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.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Availability<\/jats:title>\n                    <jats:p>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.<\/jats:p>\n                  <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btag478","type":"journal-article","created":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T05:27:45Z","timestamp":1782883665000},"source":"Crossref","is-referenced-by-count":0,"title":["Primer design through submodular function estimation"],"prefix":"10.1093","volume":"42","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8611-2828","authenticated-orcid":false,"given":"Yixin","family":"Chen","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, College of Engineering, Texas A&M University , College Station, TX 77843-3112,","place":["United States"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0200-5924","authenticated-orcid":false,"given":"Yunheng","family":"Han","sequence":"additional","affiliation":[{"name":"Department of Computer and Information Science and Engineering, Herbert Wertheim College of Engineering, University of Florida , Gainesville, FL 32611,","place":["United States"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-8152-612X","authenticated-orcid":false,"given":"Ao","family":"Wang","sequence":"additional","affiliation":[{"name":"Department of Computer and Information Science and Engineering, Herbert Wertheim College of Engineering, University of Florida , Gainesville, FL 32611,","place":["United States"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-7138-182X","authenticated-orcid":false,"given":"Aaron","family":"Hong","sequence":"additional","affiliation":[{"name":"Department of Computer and Information Science and Engineering, Herbert Wertheim College of Engineering, University of Florida , Gainesville, FL 32611,","place":["United States"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3703-834X","authenticated-orcid":false,"given":"Adam R","family":"Rivers","sequence":"additional","affiliation":[{"name":"United States Department of Agriculture , Gainesville, FL 32608,","place":["United States"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6506-1902","authenticated-orcid":false,"given":"Alan","family":"Kuhnle","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, College of Engineering, Texas A&M University , College Station, TX 77843-3112,","place":["United States"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9509-9725","authenticated-orcid":false,"given":"Christina","family":"Boucher","sequence":"additional","affiliation":[{"name":"Department of Computer and Information Science and Engineering, Herbert Wertheim College of Engineering, University of Florida , Gainesville, FL 32611,","place":["United States"]}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2026,6,30]]},"reference":[{"key":"2026071711471136500_btag478-B1","author":"Chen","year":"2024"},{"key":"2026071711471136500_btag478-B2","author":"Chen","year":"2024"},{"key":"2026071711471136500_btag478-B3","first-page":"151","author":"Cook","year":"1971"},{"key":"2026071711471136500_btag478-B4","doi-asserted-by":"crossref","first-page":"559","DOI":"10.1128\/CMR.13.4.559","article-title":"Multiplex PCR: optimization and application in diagnostic virology","volume":"13","author":"Elnifro","year":"2000","journal-title":"Clin Microbiol Rev"},{"key":"2026071711471136500_btag478-B5","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1038\/nrg.2016.49","article-title":"Coming of age: ten years of next-generation sequencing technologies","volume":"17","author":"Goodwin","year":"2016","journal-title":"Nat Rev Genet"},{"key":"2026071711471136500_btag478-B6","doi-asserted-by":"crossref","first-page":"4121","DOI":"10.1093\/bioinformatics\/bty407","article-title":"Nextstrain: real-time tracking of pathogen evolution","volume":"34","author":"Hadfield","year":"2018","journal-title":"Bioinformatics"},{"key":"2026071711471136500_btag478-B7","doi-asserted-by":"publisher","first-page":"W252","DOI":"10.1093\/nar\/gky319","article-title":"Oli2go: an automated multiplex oligonucleotide design tool","volume":"46","author":"Hendling","year":"2018","journal-title":"Nucleic Acids Res"},{"key":"2026071711471136500_btag478-B8","doi-asserted-by":"crossref","first-page":"1701","DOI":"10.1093\/bioinformatics\/bti219","article-title":"MultiPLX: automatic grouping and evaluation of PCR primers","volume":"21","author":"Kaplinski","year":"2005","journal-title":"Bioinformatics"},{"key":"2026071711471136500_btag478-B9","doi-asserted-by":"publisher","first-page":"3059","DOI":"10.1093\/nar\/gkf436","article-title":"MAFFT: a novel method for rapid multiple sequence alignment based on fast Fourier transform","volume":"30","author":"Katoh","year":"2002","journal-title":"Nucleic Acids Res"},{"key":"2026071711471136500_btag478-B10","author":"Kent","year":"2024"},{"key":"2026071711471136500_btag478-B11","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/j.addr.2016.04.005","article-title":"Diagnostics based on nucleic acid sequence variant profiling: PCR, hybridization, and NGS approaches","volume":"105","author":"Khodakov","year":"2016","journal-title":"Adv Drug Deliv Rev"},{"key":"2026071711471136500_btag478-B12","first-page":"10","article-title":"Methods for the extraction, storage, amplification and sequencing of DNA from environmental samples","volume":"42","author":"Lear","year":"2018","journal-title":"N Z J Ecol"},{"key":"2026071711471136500_btag478-B13","doi-asserted-by":"publisher","first-page":"468","DOI":"10.1186\/s12859-023-05121-9","article-title":"primerJinn: a tool for rationally designing multiplex PCR primer sets for amplicon sequencing and performing in silico PCR","volume":"24","author":"Limberis","year":"2023","journal-title":"BMC Bioinformatics"},{"key":"2026071711471136500_btag478-B14","doi-asserted-by":"publisher","first-page":"W544","DOI":"10.1093\/nar\/gki377","article-title":"MuPlex: multi-objective multiplex PCR assay design","volume":"33","author":"Rachlin","year":"2005","journal-title":"Nucleic Acids Res"},{"key":"2026071711471136500_btag478-B15","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1186\/1471-2105-11-143","article-title":"MPprimer: a program for reliable multiplex PCR primer design","volume":"11","author":"Shen","year":"2010","journal-title":"BMC Bioinformatics"},{"key":"2026071711471136500_btag478-B16","doi-asserted-by":"crossref","first-page":"174","DOI":"10.1186\/s12859-022-04710-1","article-title":"Prider: multiplexed primer design using linearly scaling approximation of set coverage","volume":"23","author":"Smolander","year":"2022","journal-title":"BMC Bioinformatics"},{"key":"2026071711471136500_btag478-B17","doi-asserted-by":"crossref","first-page":"e115","DOI":"10.1093\/nar\/gks596","article-title":"Primer3\u2013new capabilities and interfaces","volume":"40","author":"Untergasser","year":"2012","journal-title":"Nucleic Acids Res"},{"key":"2026071711471136500_btag478-B18","doi-asserted-by":"publisher","first-page":"6306","DOI":"10.1038\/s41467-024-6306","article-title":"Olivar: towards automated variant aware primer design for multiplex tiled amplicon sequencing of pathogens","volume":"15","author":"Wang","year":"2024","journal-title":"Nat Commun"},{"key":"2026071711471136500_btag478-B19","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1186\/s12859-016-1453-3","article-title":"MPD: multiplex primer design for next-generation targeted sequencing","volume":"18","author":"Wingo","year":"2017","journal-title":"BMC Bioinformatics"},{"key":"2026071711471136500_btag478-B20","doi-asserted-by":"crossref","first-page":"1881","DOI":"10.1038\/s41467-022-29500-4","article-title":"Designing highly multiplex PCR primer sets with simulated annealing design using dimer likelihood estimation (SADDLE)","volume":"13","author":"Xie","year":"2022","journal-title":"Nat Commun"},{"key":"2026071711471136500_btag478-B21","doi-asserted-by":"crossref","first-page":"W665","DOI":"10.1093\/nar\/gkl297","article-title":"PrimerStation: a highly specific multiplex genomic PCR primer design server for the human genome","volume":"34","author":"Yamada","year":"2006","journal-title":"Nucleic Acids Res"},{"key":"2026071711471136500_btag478-B22","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1093\/bib\/bbac121","article-title":"Multiobjective optimization-driven primer design mechanism: towards user-specified parameters of PCR primer","volume":"23","author":"Yang","year":"2022","journal-title":"Brief Bioinform"},{"key":"2026071711471136500_btag478-B23","doi-asserted-by":"crossref","first-page":"16451","DOI":"10.1038\/s41598-023-43825-0","article-title":"A tool to automatically design multiplex PCR primer pairs for specific targets using diverse templates","volume":"13","author":"Yang","year":"2023","journal-title":"Sci Rep"},{"key":"2026071711471136500_btag478-B24","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1186\/1471-2105-13-134","article-title":"Primer-BLAST: a tool to design target-specific primers for polymerase chain reaction","volume":"13","author":"Ye","year":"2012","journal-title":"BMC Bioinformatics"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/advance-article-pdf\/doi\/10.1093\/bioinformatics\/btag478\/68653557\/btag478.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/42\/7\/btag478\/68653557\/btag478.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/42\/7\/btag478\/68653557\/btag478.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,17]],"date-time":"2026-07-17T15:47:21Z","timestamp":1784303241000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/doi\/10.1093\/bioinformatics\/btag478\/8722296"}},"subtitle":[],"editor":[{"given":"Russell","family":"Schwartz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"editor"}]}],"short-title":[],"issued":{"date-parts":[[2026,6,30]]},"references-count":24,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2026,7,2]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btag478","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2026,7]]},"published":{"date-parts":[[2026,6,30]]},"article-number":"btag478"}}