{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,21]],"date-time":"2026-03-21T21:27:32Z","timestamp":1774128452766,"version":"3.50.1"},"reference-count":32,"publisher":"Oxford University Press (OUP)","issue":"1","license":[{"start":{"date-parts":[[2024,12,12]],"date-time":"2024-12-12T00:00:00Z","timestamp":1733961600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"National Library of Medicine Training Program in Biomed-ical Informatics and Data Science","award":["T15LM007093"],"award-info":[{"award-number":["T15LM007093"]}]},{"DOI":"10.13039\/100000060","name":"National Institute of Allergy and Infectious Diseases","doi-asserted-by":"publisher","award":["P01-AI152999"],"award-info":[{"award-number":["P01-AI152999"]}],"id":[{"id":"10.13039\/100000060","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["IIS-2239114"],"award-info":[{"award-number":["IIS-2239114"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["EF-2126387"],"award-info":[{"award-number":["EF-2126387"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024,12,26]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:sec>\n                  <jats:title>Motivation<\/jats:title>\n                  <jats:p>Sampling k-mers is a ubiquitous task in sequence analysis algorithms. Sampling schemes such as the often-used random minimizer scheme are particularly appealing as they guarantee at least one k-mer is selected out of every w consecutive k-mers. Sampling fewer k-mers often leads to an increase in efficiency of downstream methods. Thus, developing schemes that have low density, i.e. have a small proportion of sampled k-mers, is an active area of research. After over a decade of consistent efforts in both decreasing the density of practical schemes and increasing the lower bound on the best possible density, there is still a large gap between the two.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Results<\/jats:title>\n                  <jats:p>We prove a near-tight lower bound on the density of forward sampling schemes, a class of schemes that generalizes minimizer schemes. For small w and k, we observe that our bound is tight when k\u22611(mod\u00a0w). For large w and k, the bound can be approximated by 1w+k\u2308w+kw\u2309. Importantly, our lower bound implies that existing schemes are much closer to achieving optimal density than previously known. For example, with the current default minimap2 HiFi settings w\u2009=\u200919 and k\u2009=\u200919, we show that the best known scheme for these parameters, the double decycling-set-based minimizer of Pellow et al. is at most 3% denser than optimal, compared to the previous gap of at most 50%. Furthermore, when k\u22611(mod\u00a0w) and the alphabet size \u03c3 goes to \u221e, we show that mod-minimizers introduced by Groot Koerkamp and Pibiri achieve optimal density matching our lower bound.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Availability and implementation<\/jats:title>\n                  <jats:p>Minimizer implementations: github.com\/RagnarGrootKoerkamp\/minimizers ILP and analysis: github.com\/treangenlab\/sampling-scheme-analysis.<\/jats:p>\n               <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btae736","type":"journal-article","created":{"date-parts":[[2024,12,12]],"date-time":"2024-12-12T21:20:35Z","timestamp":1734038435000},"source":"Crossref","is-referenced-by-count":4,"title":["A near-tight lower bound on the density of forward sampling schemes"],"prefix":"10.1093","volume":"41","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2946-6915","authenticated-orcid":false,"given":"Bryce","family":"Kille","sequence":"first","affiliation":[{"name":"Department of Computer Science, Rice University , Houston, TX 77005,","place":["United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2091-1237","authenticated-orcid":false,"given":"Ragnar","family":"Groot Koerkamp","sequence":"additional","affiliation":[{"name":"Department of Computer Science, ETH Zurich , Zurich 8092,","place":["Switzerland"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Drake","family":"McAdams","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Rice University , Houston, TX 77005,","place":["United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alan","family":"Liu","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Rice University , Houston, TX 77005,","place":["United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Todd J","family":"Treangen","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Rice University , Houston, TX 77005,","place":["United States"]},{"name":"Ken Kennedy Institute, Rice University , Houston, TX 77005,","place":["United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2024,12,12]]},"reference":[{"key":"2024122721054140200_btae736-B1","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1145\/3307339.3342144","author":"DeBlasio","year":"2019"},{"key":"2024122721054140200_btae736-B2","doi-asserted-by":"publisher","first-page":"e10805","DOI":"10.7717\/peerj.10805","article-title":"Syncmers are more sensitive than minimizers for selecting conserved k-mers in biological sequences","volume":"9","author":"Edgar","year":"2021","journal-title":"PeerJ"},{"key":"2024122721054140200_btae736-B3","first-page":"37","author":"Ekim","year":"2020"},{"key":"2024122721054140200_btae736-B4","doi-asserted-by":"publisher","author":"Golan","year":"2024","DOI":"10.1101\/2024.10.28.620726"},{"key":"2024122721054140200_btae736-B5","doi-asserted-by":"publisher","first-page":"11:1","DOI":"10.4230\/LIPIcs.WABI.2024.11","author":"Groot Koerkamp","year":"2024"},{"key":"2024122721054140200_btae736-B6","author":"Gurobi Optimization, LLC","year":"2024"},{"key":"2024122721054140200_btae736-B7","doi-asserted-by":"publisher","first-page":"1288","DOI":"10.1089\/cmb.2022.0275","article-title":"Differentiable learning of sequence-specific minimizer schemes with DeepMinimizer","volume":"29","author":"Hoang","year":"2022","journal-title":"J Comput Biol"},{"key":"2024122721054140200_btae736-B8","doi-asserted-by":"publisher","author":"Irber","year":"2022","DOI":"10.1101\/2022.01.11.475838"},{"key":"2024122721054140200_btae736-B9","doi-asserted-by":"publisher","first-page":"btad512","DOI":"10.1093\/bioinformatics\/btad512","article-title":"Minmers are a generalization of minimizers that enable unbiased local Jaccard estimation","volume":"39","author":"Kille","year":"2023","journal-title":"Bioinformatics"},{"key":"2024122721054140200_btae736-B10","doi-asserted-by":"publisher","first-page":"3094","DOI":"10.1093\/bioinformatics\/bty191","article-title":"Minimap2: pairwise alignment for nucleotide sequences","volume":"34","author":"Li","year":"2018","journal-title":"Bioinformatics"},{"key":"2024122721054140200_btae736-B11","doi-asserted-by":"publisher","first-page":"1145","DOI":"10.1016\/j.disc.2005.10.032","article-title":"Independence number of de Bruijn graphs","volume":"306","author":"Lichiardopol","year":"2006","journal-title":"Discrete Math"},{"key":"2024122721054140200_btae736-B12","first-page":"1","author":"Loukides","year":"2021"},{"key":"2024122721054140200_btae736-B13","doi-asserted-by":"publisher","first-page":"11093","DOI":"10.1109\/tkde.2022.3231780","article-title":"Bidirectional string anchors for improved text indexing and top-k similarity search","volume":"35","author":"Loukides","year":"2023","journal-title":"IEEE Trans Knowl Data Eng"},{"key":"2024122721054140200_btae736-B14","doi-asserted-by":"publisher","first-page":"i110","DOI":"10.1093\/bioinformatics\/btx235","article-title":"Improving the performance of minimizers and winnowing schemes","volume":"33","author":"Mar\u00e7ais","year":"2017","journal-title":"Bioinformatics"},{"key":"2024122721054140200_btae736-B15","doi-asserted-by":"publisher","first-page":"i13","DOI":"10.1093\/bioinformatics\/bty258","article-title":"Asymptotically optimal minimizers schemes","volume":"34","author":"Mar\u00e7ais","year":"2018","journal-title":"Bioinformatics"},{"key":"2024122721054140200_btae736-B16","first-page":"309","article-title":"Sur les permutations circulaires distinctes","volume":"11","author":"Moreau","year":"1872","journal-title":"Nouvelles Ann Math"},{"key":"2024122721054140200_btae736-B17","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1016\/0095-8956(72)90006-8","article-title":"A proof of Golomb\u2019s conjecture for the de Bruijn graph","volume":"13","author":"Mykkeltveit","year":"1972","journal-title":"J. Comb Theory B"},{"key":"2024122721054140200_btae736-B18","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1515\/crll.1832.9.105","article-title":"\u00dcber eine besondere art von umkehrung der reihen","volume":"1832","author":"M\u00f6bius","year":"1832","journal-title":"J. Comb Theory B"},{"key":"2024122721054140200_btae736-B19","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1186\/s13059-024-03414-4","article-title":"When less is more: sketching with minimizers in genomics","volume":"25","author":"Ndiaye","year":"2024","journal-title":"Genome Biol"},{"key":"2024122721054140200_btae736-B20","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1007\/978-3-319-43681-4_21","author":"Orenstein","year":"2016"},{"key":"2024122721054140200_btae736-B21","doi-asserted-by":"publisher","first-page":"1154","DOI":"10.1101\/gr.277644.123","article-title":"Efficient minimizer orders for large values of k using minimum decycling sets","volume":"33","author":"Pellow","year":"2023","journal-title":"Genome Res"},{"key":"2024122721054140200_btae736-B22","doi-asserted-by":"publisher","first-page":"i185","DOI":"10.1093\/bioinformatics\/btac245","article-title":"Sparse and skew hashing of k-mers","volume":"38","author":"Pibiri","year":"2022","journal-title":"Bioinformatics"},{"key":"2024122721054140200_btae736-B23","doi-asserted-by":"publisher","first-page":"344","DOI":"10.1038\/s41586-023-06457-y","article-title":"The complete sequence of a human Y chromosome","volume":"621","author":"Rhie","year":"2023","journal-title":"Nature"},{"key":"2024122721054140200_btae736-B24","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1137\/0105015","article-title":"The combinatorial significance of a theorem of P\u00f3lya","volume":"5","author":"Riordan","year":"1957","journal-title":"J Soc Industrial Appl Math"},{"key":"2024122721054140200_btae736-B25","doi-asserted-by":"crossref","first-page":"734","DOI":"10.1089\/cmb.2004.11.734","article-title":"A preprocessor for shotgun assembly of large genomes","volume":"11","author":"Roberts","year":"2004","journal-title":"J Comput Biol"},{"key":"2024122721054140200_btae736-B26","first-page":"76","author":"Schleimer","year":"2003"},{"key":"2024122721054140200_btae736-B27","doi-asserted-by":"publisher","first-page":"4659","DOI":"10.1093\/bioinformatics\/btab790","article-title":"Theory of local k-mer selection with applications to long-read alignment","volume":"38","author":"Shaw","year":"2022","journal-title":"Bioinformatics"},{"key":"2024122721054140200_btae736-B28","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1186\/s13059-019-1891-0","article-title":"Improved metagenomic analysis with Kraken 2","volume":"20","author":"Wood","year":"2019","journal-title":"Genome Biol"},{"key":"2024122721054140200_btae736-B29","doi-asserted-by":"publisher","first-page":"i119","DOI":"10.1093\/bioinformatics\/btaa472","article-title":"Improved design and analysis of practical minimizers","volume":"36","author":"Zheng","year":"2020","journal-title":"Bioinformatics"},{"key":"2024122721054140200_btae736-B30","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1089\/cmb.2020.0432","article-title":"Lower density selection schemes via small universal hitting sets with short remaining path length","volume":"28","author":"Zheng","year":"2021","journal-title":"J Comput Biol"},{"key":"2024122721054140200_btae736-B31","doi-asserted-by":"publisher","first-page":"i187","DOI":"10.1093\/bioinformatics\/btab313","article-title":"Sequence-specific minimizers via polar sets","volume":"37","author":"Zheng","year":"2021","journal-title":"Bioinformatics"},{"key":"2024122721054140200_btae736-B32","doi-asserted-by":"publisher","first-page":"1251","DOI":"10.1089\/cmb.2023.0094","article-title":"Creating and using minimizer sketches in computational genomics","volume":"30","author":"Zheng","year":"2023","journal-title":"J Comput Biol"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/advance-article-pdf\/doi\/10.1093\/bioinformatics\/btae736\/61090794\/btae736.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/41\/1\/btae736\/61090794\/btae736.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/41\/1\/btae736\/61090794\/btae736.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,27]],"date-time":"2024-12-27T21:05:56Z","timestamp":1735333556000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/doi\/10.1093\/bioinformatics\/btae736\/7922553"}},"subtitle":[],"editor":[{"given":"Yann","family":"Ponty","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2024,12,12]]},"references-count":32,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,12,26]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btae736","relation":{},"ISSN":["1367-4811"],"issn-type":[{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2025,1]]},"published":{"date-parts":[[2024,12,12]]},"article-number":"btae736"}}