{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T22:05:37Z","timestamp":1774649137384,"version":"3.50.1"},"reference-count":40,"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\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["2029170"],"award-info":[{"award-number":["2029170"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1453527"],"award-info":[{"award-number":["1453527"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1931531"],"award-info":[{"award-number":["1931531"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1356529"],"award-info":[{"award-number":["1356529"]}],"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>Sketching is now widely used in bioinformatics to reduce data size and increase data processing speed. Sketching approaches entice with improved scalability but also carry the danger of decreased accuracy and added bias. In this article, we investigate the minimizer sketch and its use to estimate the Jaccard similarity between two sequences.<\/jats:p><\/jats:sec><jats:sec><jats:title>Results<\/jats:title><jats:p>We show that the minimizer Jaccard estimator is biased and inconsistent, which means that the expected difference (i.e. the bias) between the estimator and the true value is not zero, even in the limit as the lengths of the sequences grow. We derive an analytical formula for the bias as a function of how the shared k-mers are laid out along the sequences. We show both theoretically and empirically that there are families of sequences where the bias can be substantial (e.g. the true Jaccard can be more than double the estimate). Finally, we demonstrate that this bias affects the accuracy of the widely used mashmap read mapping tool.<\/jats:p><\/jats:sec><jats:sec><jats:title>Availability and implementation<\/jats:title><jats:p>Scripts to reproduce our experiments are available at https:\/\/github.com\/medvedevgroup\/minimizer-jaccard-estimator\/tree\/main\/reproduce.<\/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\/btac244","type":"journal-article","created":{"date-parts":[[2022,4,14]],"date-time":"2022-04-14T11:10:15Z","timestamp":1649934615000},"page":"i169-i176","source":"Crossref","is-referenced-by-count":20,"title":["The minimizer Jaccard estimator is biased and inconsistent"],"prefix":"10.1093","volume":"38","author":[{"given":"Mahdi","family":"Belbasi","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, The Pennsylvania State University , University Park, PA, USA"}]},{"given":"Antonio","family":"Blanca","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, The Pennsylvania State University , University Park, PA, USA"}]},{"given":"Robert S","family":"Harris","sequence":"additional","affiliation":[{"name":"Department of Biology, The Pennsylvania State University , University Park, PA, USA"}]},{"given":"David","family":"Koslicki","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, The Pennsylvania State University , University Park, PA, USA"},{"name":"Department of Biology, The Pennsylvania State University , University Park, PA, USA"},{"name":"Huck Institutes of the Life Sciences, The Pennsylvania State University , University Park, PA, USA"}]},{"given":"Paul","family":"Medvedev","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, The Pennsylvania State University , University Park, PA, USA"},{"name":"Huck Institutes of the Life Sciences, The Pennsylvania State University , University Park, PA, USA"},{"name":"Department of Biochemistry and Molecular Biology, The Pennsylvania State University , University Park, PA, USA"}]}],"member":"286","published-online":{"date-parts":[[2022,6,27]]},"reference":[{"key":"2023041407543215800_","doi-asserted-by":"crossref","first-page":"1","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":"2023041407543215800_","author":"Blanca","year":"2021"},{"key":"2023041407543215800_","first-page":"21","author":"Broder","year":"1997"},{"key":"2023041407543215800_","first-page":"705616","author":"Chin","year":"2019"},{"key":"2023041407543215800_","first-page":"29","volume-title":"Latin American Symposium on Theoretical Informatics","author":"Cormode","year":"2004"},{"key":"2023041407543215800_","doi-asserted-by":"crossref","first-page":"900","DOI":"10.12688\/f1000research.6924.1","article-title":"The khmer software package: enabling efficient nucleotide sequence analysis","volume":"4","author":"Crusoe","year":"2015","journal-title":"F1000Res"},{"key":"2023041407543215800_","first-page":"167","author":"DeBlasio","year":"2019"},{"key":"2023041407543215800_"},{"key":"2023041407543215800_","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":"2023041407543215800_","first-page":"137","article-title":"Hyperloglog: the analysis of a near-optimal cardinality estimation algorithm","author":"Flajolet","year":"2007"},{"key":"2023041407543215800_","doi-asserted-by":"crossref","first-page":"5344","DOI":"10.1093\/bioinformatics\/btaa1054","article-title":"Minimally overlapping words for sequence similarity search","volume":"36","author":"Frith","year":"2020","journal-title":"Bioinformatics"},{"key":"2023041407543215800_"},{"key":"2023041407543215800_","first-page":"66","author":"Jain","year":"2017"},{"key":"2023041407543215800_","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":"2023041407543215800_","doi-asserted-by":"crossref","first-page":"1","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":"2023041407543215800_","doi-asserted-by":"crossref","first-page":"i111","DOI":"10.1093\/bioinformatics\/btaa435","article-title":"Weighted minimizer sampling improves long read mapping","volume":"36","author":"Jain","year":"2020","journal-title":"Bioinformatics"},{"key":"2023041407543215800_","doi-asserted-by":"crossref","first-page":"2103","DOI":"10.1093\/bioinformatics\/btw152","article-title":"Minimap and miniasm: fast mapping and de novo assembly for noisy long sequences","volume":"32","author":"Li","year":"2016","journal-title":"Bioinformatics"},{"key":"2023041407543215800_","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":"2023041407543215800_","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":"2023041407543215800_","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":"2023041407543215800_","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1146\/annurev-biodatasci-072018-021156","article-title":"Sketching and sublinear data structures in genomics","volume":"2","author":"Mar\u00e7ais","year":"2019","journal-title":"Annu. Rev. Biomed. Data Sci"},{"key":"2023041407543215800_","doi-asserted-by":"crossref","first-page":"i127","DOI":"10.1093\/bioinformatics\/btz354","article-title":"Locality-sensitive hashing for the edit distance","volume":"35","author":"Mar\u00e7ais","year":"2019","journal-title":"Bioinformatics"},{"key":"2023041407543215800_","volume-title":"Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis","author":"Mitzenmacher","year":"2017"},{"key":"2023041407543215800_"},{"key":"2023041407543215800_","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":"2023041407543215800_","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":"2023041407543215800_","doi-asserted-by":"crossref","first-page":"1006","DOI":"10.12688\/f1000research.19675.1","article-title":"Large-scale sequence comparisons with sourmash","volume":"8","author":"Pierce","year":"2019","journal-title":"F1000Res"},{"key":"2023041407543215800_","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":"2023041407543215800_","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1186\/s13059-019-1809-x","article-title":"When the levee breaks: a practical guide to sketching algorithms for processing the flood of genomic data","volume":"20","author":"Rowe","year":"2019","journal-title":"Genome Biol"},{"key":"2023041407543215800_","author":"Sahlin","year":"2021"},{"key":"2023041407543215800_","doi-asserted-by":"crossref","first-page":"472","DOI":"10.1089\/cmb.2019.0299","article-title":"De novo clustering of long-read transcriptome data using a greedy, quality value-based algorithm","volume":"27","author":"Sahlin","year":"2020","journal-title":"J. Comput. Biol"},{"key":"2023041407543215800_","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1038\/s41467-020-20340-8","article-title":"Error correction enables use of oxford nanopore technology for reference-free transcriptome analysis","volume":"12","author":"Sahlin","year":"2021","journal-title":"Nat. Commun"},{"key":"2023041407543215800_","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/s13059-019-1632-4","article-title":"Skmer: assembly-free and alignment-free sample identification using genome skims","volume":"20","author":"Sarmashghi","year":"2019","journal-title":"Genome Biol"},{"key":"2023041407543215800_","first-page":"76","author":"Schleimer","year":"2003"},{"key":"2023041407543215800_","author":"Shaw","year":"2021"},{"key":"2023041407543215800_","first-page":"3154","author":"Shrivastava","year":"2017"},{"key":"2023041407543215800_","doi-asserted-by":"crossref","first-page":"453","DOI":"10.1145\/2714064.2660195","article-title":"Fast splittable pseudorandom number generators","volume":"49","author":"Steele","year":"2014","journal-title":"SIGPLAN Not"},{"key":"2023041407543215800_","volume-title":"All of Statistics: A Concise Course in Statistical Inference","author":"Wasserman","year":"2013"},{"key":"2023041407543215800_","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1093\/bioinformatics\/bty651","article-title":"BinDash, software for fast genome distance estimation on a typical personal laptop","volume":"35","author":"Zhao","year":"2019","journal-title":"Bioinformatics"},{"key":"2023041407543215800_","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\/article-pdf\/38\/Supplement_1\/i169\/49886980\/btac244.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/38\/Supplement_1\/i169\/49886980\/btac244.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,22]],"date-time":"2024-09-22T06:55:55Z","timestamp":1726988155000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/38\/Supplement_1\/i169\/6617497"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,24]]},"references-count":40,"journal-issue":{"issue":"Supplement_1","published-print":{"date-parts":[[2022,6,24]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btac244","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]]}}}