{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T15:26:42Z","timestamp":1781018802703,"version":"3.54.1"},"reference-count":21,"publisher":"Oxford University Press (OUP)","issue":"Supplement_1","license":[{"start":{"date-parts":[[2022,6,27]],"date-time":"2022-06-27T00:00:00Z","timestamp":1656288000000},"content-version":"vor","delay-in-days":3,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"NSERC","doi-asserted-by":"publisher","award":["RGPIN-07185-2020"],"award-info":[{"award-number":["RGPIN-07185-2020"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000002","name":"National Institutes of Health","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000002","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000060","name":"National Institute of Allergy and Infectious Diseases","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000060","id-type":"DOI","asserted-by":"publisher"}]},{"name":"NIH NIAID","award":["R01HG011392"],"award-info":[{"award-number":["R01HG011392"]}]},{"name":"National Science Foundation Smart and Connected Health Integrative Projects","award":["2013998"],"award-info":[{"award-number":["2013998"]}]},{"name":"National Science Foundation Early-concept Grants for Exploratory Research","award":["2118251"],"award-info":[{"award-number":["2118251"]}]},{"DOI":"10.13039\/501100020884","name":"Agencia Nacional de Investigaci\u00f3n y Desarrollo","doi-asserted-by":"publisher","award":["FB0001"],"award-info":[{"award-number":["FB0001"]}],"id":[{"id":"10.13039\/501100020884","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006221","name":"U.S-Israel Binational Science Foundation","doi-asserted-by":"publisher","award":["2018302"],"award-info":[{"award-number":["2018302"]}],"id":[{"id":"10.13039\/100006221","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-2008838"],"award-info":[{"award-number":["CCF-2008838"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022,6,24]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:sec><jats:title>Motivation<\/jats:title><jats:p>Bait enrichment is a protocol that is becoming increasingly ubiquitous as it has been shown to successfully amplify regions of interest in metagenomic samples. In this method, a set of synthetic probes (\u2018baits\u2019) are designed, manufactured and applied to fragmented metagenomic DNA. The probes bind to the fragmented DNA and any unbound DNA is rinsed away, leaving the bound fragments to be amplified for sequencing. Metsky et al. demonstrated that bait-enrichment is capable of detecting a large number of human viral pathogens within metagenomic samples.<\/jats:p><\/jats:sec><jats:sec><jats:title>Results<\/jats:title><jats:p>We formalize the problem of designing baits by defining the Minimum Bait Cover problem, show that the problem is NP-hard even under very restrictive assumptions, and design an efficient heuristic that takes advantage of succinct data structures. We refer to our method as Syotti. The running time of Syotti shows linear scaling in practice, running at least an order of magnitude faster than state-of-the-art methods, including the method of Metsky et al. At the same time, our method produces bait sets that are smaller than the ones produced by the competing methods, while also leaving fewer positions uncovered. Lastly, we show that Syotti requires only 25\u2009min to design baits for a dataset comprised of 3 billion nucleotides from 1000 related bacterial substrains, whereas the method of Metsky et al. shows clearly super-linear running time and fails to process even a subset of 17% of the data in 72\u2009h.<\/jats:p><\/jats:sec><jats:sec><jats:title>Availability and implementation<\/jats:title><jats:p>https:\/\/github.com\/jnalanko\/syotti.<\/jats:p><\/jats:sec><jats:sec><jats:title>Supplementary information<\/jats:title><jats:p>Supplementary data are available at Bioinformatics online.<\/jats:p><\/jats:sec>","DOI":"10.1093\/bioinformatics\/btac226","type":"journal-article","created":{"date-parts":[[2022,4,14]],"date-time":"2022-04-14T11:10:15Z","timestamp":1649934615000},"page":"i177-i184","source":"Crossref","is-referenced-by-count":20,"title":["Syotti: scalable bait design for DNA enrichment"],"prefix":"10.1093","volume":"38","author":[{"given":"Jarno N","family":"Alanko","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Helsinki , Helsinki, Finland"},{"name":"Faculty of Computer Science, Dalhousie University , Halifax, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ilya B","family":"Slizovskiy","sequence":"additional","affiliation":[{"name":"Department of Veterinary Population Medicine, University of Minnesota , St. Paul, MN, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Daniel","family":"Lokshtanov","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of California , Santa Barbara, CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Travis","family":"Gagie","sequence":"additional","affiliation":[{"name":"Faculty of Computer Science, Dalhousie University , Halifax, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Noelle R","family":"Noyes","sequence":"additional","affiliation":[{"name":"Department of Veterinary Population Medicine, University of Minnesota , St. Paul, MN, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christina","family":"Boucher","sequence":"additional","affiliation":[{"name":"Department of Computer and Information Science and Engineering, University of Florida , Gainesville, FL, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2022,6,27]]},"reference":[{"key":"2023041407552398400_","doi-asserted-by":"crossref","first-page":"356","DOI":"10.1111\/1755-0998.12721","article-title":"Baitstools: software for hybridization capture bait design","volume":"18","author":"Campana","year":"2018","journal-title":"Mol. Ecol. Resour"},{"key":"2023041407552398400_","doi-asserted-by":"crossref","first-page":"4293","DOI":"10.1093\/bioinformatics\/bty548","article-title":"MrBait: universal identification and design of targeted-enrichment capture probes","volume":"34","author":"Chafin","year":"2018","journal-title":"Bioinformatics"},{"key":"2023041407552398400_","first-page":"641","article-title":"The complexity of the minimum k-Cover problem","volume":"10","author":"Cole","year":"2005","journal-title":"J. Autom. Lang. Comb"},{"key":"2023041407552398400_","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1038\/s41564-019-0637-9","article-title":"Metagenomic sequencing with spiked primer enrichment for viral diagnostics and genomic surveillance","volume":"5","author":"Deng","year":"2020","journal-title":"Nat. Microbiol"},{"key":"2023041407552398400_","volume-title":"Parameterized Complexity","author":"Downey","year":"2012"},{"key":"2023041407552398400_","doi-asserted-by":"crossref","first-page":"552","DOI":"10.1145\/1082036.1082039","article-title":"Indexing compressed text","volume":"52","author":"Ferragina","year":"2005","journal-title":"J. ACM"},{"key":"2023041407552398400_","first-page":"326","author":"Gog","year":"2014"},{"key":"2023041407552398400_","doi-asserted-by":"crossref","DOI":"10.1128\/AAC.01324-19","article-title":"Capturing the resistome: a targeted capture method to reveal antibiotic resistance determinants in metagenomes","volume":"64","author":"Guitor","year":"2019","journal-title":"Antimicrob. Agents Chemother"},{"key":"2023041407552398400_","doi-asserted-by":"crossref","first-page":"4353","DOI":"10.1093\/bioinformatics\/btaa552","article-title":"Antholigo: automating the design of oligonucleotides for capture\/enrichment technologies","volume":"36","author":"Jayaraman","year":"2020","journal-title":"Bioinformatics"},{"key":"2023041407552398400_","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/s12859-015-0501-8","article-title":"MetCap: a bioinformatics probe design pipeline for large-scale targeted metagenomics","volume":"16","author":"Kushwaha","year":"2015","journal-title":"BMC Bioinformatics"},{"key":"2023041407552398400_","doi-asserted-by":"crossref","first-page":"1658","DOI":"10.1128\/JCM.01463-16","article-title":"Targeted enrichment for pathogen detection and characterization in three felid species","volume":"55","author":"Lee","year":"2017","journal-title":"J. Clin. Microbiol"},{"key":"2023041407552398400_","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781139940023","volume-title":"Genome-Scale Algorithm Design: Biological Sequence Analysis in the Era of High-Throughput Sequencing","author":"M\u00e4kinen","year":"2015"},{"key":"2023041407552398400_","doi-asserted-by":"crossref","first-page":"1875","DOI":"10.1093\/molbev\/msw056","article-title":"BaitFisher: a software package for multispecies target DNA enrichment probe design","volume":"33","author":"Mayer","year":"2016","journal-title":"Mol. Biol. Evol"},{"key":"2023041407552398400_","doi-asserted-by":"crossref","first-page":"160","DOI":"10.1038\/s41587-018-0006-x","article-title":"Capturing sequence diversity in metagenomes with comprehensive and scalable probe design","volume":"37","author":"Metsky","year":"2019","journal-title":"Nat. Biotechnol"},{"key":"2023041407552398400_","doi-asserted-by":"crossref","first-page":"142","DOI":"10.1186\/s40168-017-0361-8","article-title":"Enrichment allows identification of diverse, rare elements in metagenomic resistome-virulome sequencing","volume":"5","author":"Noyes","year":"2017","journal-title":"Microbiome"},{"key":"2023041407552398400_","doi-asserted-by":"crossref","first-page":"470","DOI":"10.1038\/sj.embor.7400145","article-title":"Multicellular microorganisms: laboratory versus nature","volume":"5","author":"Palkova","year":"2004","journal-title":"EMBO Rep"},{"key":"2023041407552398400_","doi-asserted-by":"crossref","first-page":"4\u2013es","DOI":"10.1145\/1242471.1242472","article-title":"A taxonomy of suffix array construction algorithms","volume":"39","author":"Puglisi","year":"2007","journal-title":"ACM Comput. Surv"},{"key":"2023041407552398400_","doi-asserted-by":"crossref","first-page":"e2584","DOI":"10.7717\/peerj.2584","article-title":"VSEARCH: a versatile open source tool for metagenomics","volume":"4","author":"Rognes","year":"2016","journal-title":"PeerJ"},{"key":"2023041407552398400_","doi-asserted-by":"crossref","first-page":"1983","DOI":"10.3389\/fmicb.2020.01983","article-title":"Detection of antimicrobial resistance genes in the milk production environment: impact of host dna and sequencing depth","volume":"11","author":"Rubiola","year":"2020","journal-title":"Front. Microbiol"},{"key":"2023041407552398400_","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1007\/BFb0027775","volume-title":"Concurrency and Parallelism, Programming, Networking, and Security: Second Asian Computing Science Conference, ASIAN \u201996, Singapore, December 2-5, 1996, Proceedings, Volume 1179 of Lecture Notes in Computer Science","author":"Shi","year":"1996"},{"key":"2023041407552398400_","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1002\/0471250953.bi0313s48","article-title":"Clustal omega","volume":"48","author":"Sievers","year":"2014","journal-title":"Curr. Protoc. Bioinformatics"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/38\/Supplement_1\/i177\/49887123\/btac226.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/38\/Supplement_1\/i177\/49887123\/btac226.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,22]],"date-time":"2024-09-22T06:55:43Z","timestamp":1726988143000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/38\/Supplement_1\/i177\/6617487"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,24]]},"references-count":21,"journal-issue":{"issue":"Supplement_1","published-print":{"date-parts":[[2022,6,24]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btac226","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2022,7,1]]},"published":{"date-parts":[[2022,6,24]]}}}