{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,17]],"date-time":"2026-08-17T23:14:25Z","timestamp":1787008465389,"version":"3.56.0"},"reference-count":39,"publisher":"Oxford University Press (OUP)","issue":"9","license":[{"start":{"date-parts":[[2023,8,21]],"date-time":"2023-08-21T00:00:00Z","timestamp":1692576000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"National Library of Medicine Training Program in Biomedical Informatics and Data Science","award":["T15LM007093"],"award-info":[{"award-number":["T15LM007093"]}]},{"DOI":"10.13039\/100000051","name":"National Human Genome Research Institute","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000051","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"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023,9,2]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:sec>\n                    <jats:title>Motivation<\/jats:title>\n                    <jats:p>The Jaccard similarity on k-mer sets has shown to be a convenient proxy for sequence identity. By avoiding expensive base-level alignments and comparing reduced sequence representations, tools such as MashMap can scale to massive numbers of pairwise comparisons while still providing useful similarity estimates. However, due to their reliance on minimizer winnowing, previous versions of MashMap were shown to be biased and inconsistent estimators of Jaccard similarity. This directly impacts downstream tools that rely on the accuracy of these estimates.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Results<\/jats:title>\n                    <jats:p>To address this, we propose the minmer winnowing scheme, which generalizes the minimizer scheme by use of a rolling minhash with multiple sampled k-mers per window. We show both theoretically and empirically that minmers yield an unbiased estimator of local Jaccard similarity, and we implement this scheme in an updated version of MashMap. The minmer-based implementation is over 10 times faster than the minimizer-based version under the default ANI threshold, making it well-suited for large-scale comparative genomics applications.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Availability and implementation<\/jats:title>\n                    <jats:p>MashMap3 is available at https:\/\/github.com\/marbl\/MashMap.<\/jats:p>\n                  <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btad512","type":"journal-article","created":{"date-parts":[[2023,8,21]],"date-time":"2023-08-21T15:05:21Z","timestamp":1692630321000},"source":"Crossref","is-referenced-by-count":40,"title":["Minmers are a generalization of minimizers that enable unbiased local Jaccard estimation"],"prefix":"10.1093","volume":"39","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, United States"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3821-631X","authenticated-orcid":false,"given":"Erik","family":"Garrison","sequence":"additional","affiliation":[{"name":"Department of Genetics, Genomics and Informatics, University of Tennessee Health Science Center , Memphis, TN, United States"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3760-564X","authenticated-orcid":false,"given":"Todd J","family":"Treangen","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Rice University , Houston, TX, United States"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Adam M","family":"Phillippy","sequence":"additional","affiliation":[{"name":"Genome Informatics Section, Computational and Statistical Genomics Branch, National Human Genome Research Institute, National Institutes of Health , Bethesda, MD, United States"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2023,8,21]]},"reference":[{"key":"2023091720051143700_btad512-B1","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1186\/s13059-019-1875-0","article-title":"Dashing: fast and accurate genomic distances with hyperloglog","volume":"20","author":"Baker","year":"2019","journal-title":"Genome Biol"},{"key":"2023091720051143700_btad512-B2","doi-asserted-by":"crossref","first-page":"i169","DOI":"10.1093\/bioinformatics\/btac244","article-title":"The minimizer Jaccard estimator is biased and inconsistent","volume":"38","author":"Belbasi","year":"2022","journal-title":"Bioinformatics"},{"key":"2023091720051143700_btad512-B3","doi-asserted-by":"crossref","first-page":"623","DOI":"10.1038\/nbt.3238","article-title":"Assembling large genomes with single-molecule sequencing and locality-sensitive hashing","volume":"33","author":"Berlin","year":"2015","journal-title":"Nat Biotechnol"},{"key":"2023091720051143700_btad512-B4","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1089\/cmb.2021.0431","article-title":"The statistics of k-mers from a sequence undergoing a simple mutation process without spurious matches","volume":"29","author":"Blanca","year":"2022","journal-title":"J Comput Biol"},{"key":"2023091720051143700_btad512-B5","first-page":"21","author":"Broder","year":"1997"},{"key":"2023091720051143700_btad512-B6","doi-asserted-by":"crossref","first-page":"27","DOI":"10.21105\/joss.00027","article-title":"sourmash: a library for MinHash sketching of DNA","volume":"1","author":"Brown","year":"2016","journal-title":"JOSS"},{"key":"2023091720051143700_btad512-B7","first-page":"225","author":"Cohen","year":"2007"},{"key":"2023091720051143700_btad512-B8","author":"Cohen","year":"2016"},{"key":"2023091720051143700_btad512-B9","doi-asserted-by":"crossref","first-page":"3066","DOI":"10.1038\/s41467-019-10934-2","article-title":"Strain-level metagenomic assignment and compositional estimation for long reads with metamaps","volume":"10","author":"Dilthey","year":"2019","journal-title":"Nat Commun"},{"key":"2023091720051143700_btad512-B10","doi-asserted-by":"crossref","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":"2023091720051143700_btad512-B11","first-page":"37","author":"Ekim","year":"2020"},{"key":"2023091720051143700_btad512-B12","first-page":"1188","author":"Ekim"},{"key":"2023091720051143700_btad512-B13","doi-asserted-by":"crossref","first-page":"lqad004","DOI":"10.1093\/nargab\/lqad004","article-title":"Blend: a fast, memory-efficient and accurate mechanism to find fuzzy seed matches in genome analysis","volume":"5","author":"Firtina","year":"2023","journal-title":"NAR Genom Bioinform"},{"key":"2023091720051143700_btad512-B14","author":"Guarracino","year":"2021"},{"key":"2023091720051143700_btad512-B15","first-page":"66","author":"Jain","year":"2017"},{"key":"2023091720051143700_btad512-B16","doi-asserted-by":"crossref","first-page":"i748","DOI":"10.1093\/bioinformatics\/bty597","article-title":"A fast adaptive algorithm for computing whole-genome homology maps","volume":"34","author":"Jain","year":"2018","journal-title":"Bioinformatics"},{"key":"2023091720051143700_btad512-B17","doi-asserted-by":"crossref","first-page":"705","DOI":"10.1038\/s41592-022-01457-8","article-title":"Long-read mapping to repetitive reference sequences using Winnowmap2","volume":"19","author":"Jain","year":"2022","journal-title":"Nat Methods"},{"key":"2023091720051143700_btad512-B18","doi-asserted-by":"crossref","first-page":"5114","DOI":"10.1038\/s41467-018-07641-9","article-title":"High throughput ANI analysis of 90K prokaryotic genomes reveals clear species boundaries","volume":"9","author":"Jain","year":"2018","journal-title":"Nat Commun"},{"key":"2023091720051143700_btad512-B19","doi-asserted-by":"crossref","first-page":"eaar6343","DOI":"10.1126\/science.aar6343","article-title":"High-resolution comparative analysis of great ape genomes","volume":"360","author":"Kronenberg","year":"2018","journal-title":"Science"},{"key":"2023091720051143700_btad512-B20","doi-asserted-by":"crossref","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":"2023091720051143700_btad512-B21","doi-asserted-by":"crossref","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":"2023091720051143700_btad512-B22","doi-asserted-by":"crossref","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":"2023091720051143700_btad512-B23","doi-asserted-by":"crossref","first-page":"456","DOI":"10.1093\/bioinformatics\/btaa777","article-title":"Fast gap-affine pairwise alignment using the wavefront algorithm","volume":"37","author":"Marco-Sola","year":"2021","journal-title":"Bioinformatics"},{"key":"2023091720051143700_btad512-B24","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1126\/science.abj6987","article-title":"The complete sequence of a human genome","volume":"376","author":"Nurk","year":"2022","journal-title":"Science"},{"key":"2023091720051143700_btad512-B25","doi-asserted-by":"crossref","first-page":"232","DOI":"10.1186\/s13059-019-1841-x","article-title":"Mash screen: high-throughput sequence containment estimation for genome discovery","volume":"20","author":"Ondov","year":"2019","journal-title":"Genome Biol"},{"key":"2023091720051143700_btad512-B26","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1186\/s13059-016-0997-x","article-title":"Mash: fast genome and metagenome distance estimation using MinHash","volume":"17","author":"Ondov","year":"2016","journal-title":"Genome Biol"},{"key":"2023091720051143700_btad512-B27","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1093\/bioinformatics\/bts649","article-title":"PBSIM: PacBio reads simulator\u2014toward accurate genome assembly","volume":"29","author":"Ono","year":"2013","journal-title":"Bioinformatics"},{"key":"2023091720051143700_btad512-B28","doi-asserted-by":"crossref","first-page":"15311","DOI":"10.1038\/ncomms15311","article-title":"A hybrid cloud read aligner based on minhash and kmer voting that preserves privacy","volume":"8","author":"Popic","year":"2017","journal-title":"Nat Commun"},{"key":"2023091720051143700_btad512-B29","author":"Rhie","year":"2023."},{"key":"2023091720051143700_btad512-B30","doi-asserted-by":"crossref","first-page":"3363","DOI":"10.1093\/bioinformatics\/bth408","article-title":"Reducing storage requirements for biological sequence comparison","volume":"20","author":"Roberts","year":"2004","journal-title":"Bioinformatics"},{"key":"2023091720051143700_btad512-B31","doi-asserted-by":"crossref","first-page":"2080","DOI":"10.1101\/gr.275648.121","article-title":"Effective sequence similarity detection with strobemers","volume":"31","author":"Sahlin","year":"2021","journal-title":"Genome Res"},{"key":"2023091720051143700_btad512-B32","first-page":"76","author":"Schleimer","year":"2003"},{"key":"2023091720051143700_btad512-B33","doi-asserted-by":"crossref","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":"2023091720051143700_btad512-B34","author":"Shaw","year":"2023"},{"key":"2023091720051143700_btad512-B35","doi-asserted-by":"crossref","first-page":"4848","DOI":"10.1093\/bioinformatics\/btac604","article-title":"A closed formula relevant to \u2018Theory of local k-mer selection with applications to long-read alignment\u2019 by Jim Shaw and Yun William Yu","volume":"38","author":"Spouge","year":"2022","journal-title":"Bioinformatics"},{"key":"2023091720051143700_btad512-B36","doi-asserted-by":"crossref","first-page":"437","DOI":"10.1038\/s41586-022-04601-8","article-title":"The human pangenome project: a global resource to map genomic diversity","volume":"604","author":"Wang","year":"2022","journal-title":"Nature"},{"key":"2023091720051143700_btad512-B37","first-page":"1146","author":"Wang","year":"2022"},{"key":"2023091720051143700_btad512-B38","doi-asserted-by":"crossref","first-page":"eabc6617","DOI":"10.1126\/science.abc6617","article-title":"Sequence diversity analyses of an improved rhesus macaque genome enhance its biomedical utility","volume":"370","author":"Warren","year":"2020","journal-title":"Science"},{"key":"2023091720051143700_btad512-B39","doi-asserted-by":"crossref","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"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/advance-article-pdf\/doi\/10.1093\/bioinformatics\/btad512\/51201597\/btad512.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/39\/9\/btad512\/51648656\/btad512.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/39\/9\/btad512\/51648656\/btad512.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,17]],"date-time":"2023-09-17T16:15:25Z","timestamp":1694967325000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/doi\/10.1093\/bioinformatics\/btad512\/7246743"}},"subtitle":[],"editor":[{"given":"Peter","family":"Robinson","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"editor"}]}],"short-title":[],"issued":{"date-parts":[[2023,8,21]]},"references-count":39,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2023,9,2]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btad512","relation":{"has-preprint":[{"id-type":"doi","id":"10.1101\/2023.05.16.540882","asserted-by":"object"}]},"ISSN":["1367-4811"],"issn-type":[{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2023,9,1]]},"published":{"date-parts":[[2023,8,21]]},"article-number":"btad512"}}