CoChat
Sign Up
Cited by 3,373Genomics and Phylogenetic StudiesAlgorithms and Data CompressionFractal and DNA sequence analysis

Mash: fast genome and metagenome distance estimation using MinHash

Open access
Brian Ondov, Todd J. Treangen, Páll Melsted, Adam B. Mallonee, Nicholas H. Bergman, Sergey Koren, Adam M. Phillippy·2016·Genome biology
DOI 10.1186/s13059-016-0997-xPMC PMC4915045

Published version of a preprint

Open this paper in CoChat — free accountOpen PDF

Abstract

Mash extends the MinHash dimensionality-reduction technique to include a pairwise mutation distance and P value significance test, enabling the efficient clustering and search of massive sequence collections. Mash reduces large sequences and sequence sets to small, representative sketches, from which global mutation distances can be rapidly estimated. We demonstrate several use cases, including the clustering of all 54,118 NCBI RefSeq genomes in 33 CPU h; real-time database search using assembled or unassembled Illumina, Pacific Biosciences, and Oxford Nanopore data; and the scalable clustering of hundreds of metagenomic samples by composition. Mash is freely released under a BSD license ( https://github.com/marbl/mash ).

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

OpenAlex · 10.1186/s13059-016-0997-x

Cites

10 of 10 references verified0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Alignment projection-mapping methods were previously shown to align more UTR bases than translated methods.

    “Alignment projection-mapping methods were previously shown53 to align more UTR bases than translated methods.”

    From Progressive Cactus is a multiple-genome aligner for the thousand-genome era (2020) · cites this paper as [53]

    The Background section describes Mash’s alignment-free distance estimates and compares them with alignment-based measures, but does not compare projection-mapping with translated methods. Searches for UTR bases, projection mapping, and untranslated regions found no passage addressing which method aligns more UTR bases. (LLM, conf=0.77)

    Experimental — accuracy not yet measured

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

Flagged first, then by citations

Research works printed but not linked: 44

  1. [2]GenBank and WGS Statistics. http://www.ncbi.nlm.nih.gov/genbank/statistics. Accessed 31 May 2016.
  2. [3]Stephens ZD Lee SY Faghri F Campbell RH Zhai C Efron MJ Big data: astronomical or genomical? PLoS Biol 2015 13 e1002195 10.1371/journal.pbio.1002195 26151137 PMC4494865 · DOI · Paper page
  3. [4]Broder AZ. On the resemblance and containment of documents. Compression and Complexity of Sequences 1997 - Proceedings 1998:21–29.
  4. [7]Chum O, Philbin J, Zisserman A. Near Duplicate Image Detection: min-Hash and tf-idf Weighting. In: Proceedings of the British Machine Vision Conference 2008. Durham, UK: British Machine Vision Association and Society for Pattern Recognition; 2008.
  5. [8]Narayanan M Karp RM Gapped local similarity search with provable guarantees Algorithms in Bioinformatics, Proceedings 2004 3240 74 86 10.1007/978-3-540-30219-3_7 · DOI
  6. [9]Berlin K Koren S Chin CS Drake JP Landolin JM Phillippy AM Assembling large genomes with single-molecule sequencing and locality-sensitive hashing Nat Biotechnol 2015 33 623 30 10.1038/nbt.3238 26006009 · DOI
  7. [10]Yang X Zola J Aluru S Parallel metagenomic sequence clustering via sketching and maximal quasi-clique enumeration on map-reduce clouds Parallel & Distributed Processing Symposium (IPDPS), 2011 IEEE International. IEEE 2011 1223 1233
  8. [11]Drew J Hahsler M Strand: fast sequence comparison using mapreduce and locality sensitive hashing Proceedings of the 5th ACM Conference on Bioinformatics, Computational Biology, and Health Informatics 2014 Newport Beach, CA ACM
  9. [12]Rasheed Z Rangwala H A Map-Reduce Framework for Clustering Metagenomes 2013 IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum: IEEE 2013
  10. [13]Vinga S Almeida J Alignment-free sequence comparison-a review Bioinformatics 2003 19 513 23 10.1093/bioinformatics/btg005 12611807 · DOI
  11. [14]Haubold B Alignment-free phylogenetics and population genetics Brief Bioinform 2014 15 407 18 10.1093/bib/bbt083 24291823 · DOI
  12. [15]Blaisdell BE A measure of the similarity of sets of sequences not requiring sequence alignment Proc Natl Acad Sci U S A 1986 83 5155 9 10.1073/pnas.83.14.5155 3460087 PMC323909 · DOI
  13. [16]Torney DC Burks C Davison D Sirotkin KM Bell GI Marr TG Computation of d2: a measure of sequence dissimilarity Computers and DNA: the proceedings of the Interface between Computation Science and Nucleic Acid Sequencing Workshop, held December 12 to 16, 1988 in Santa Fe, New Mexico 1990 Redwood City Addison-Wesley Pub. Co
  14. [17]Lippert RA Huang H Waterman MS Distributional regimes for the number of k-word matches between two random sequences Proc Natl Acad Sci U S A 2002 99 13980 9 10.1073/pnas.202468099 12374863 PMC137823 · DOI
  15. [18]Yang K Zhang L Performance comparison between k-tuple distance and four model-based distances in phylogenetic tree reconstruction Nucleic Acids Res 2008 36 e33 10.1093/nar/gkn075 18296485 PMC2275138 · DOI
  16. [19]Deloger M El Karoui M Petit MA A genomic distance based on MUM indicates discontinuity between most bacterial species and genera J Bacteriol 2009 191 91 9 10.1128/JB.01202-08 18978054 PMC2612450 · DOI
  17. [20]Yi H Jin L Co-phylog: an assembly-free phylogenomic approach for closely related organisms Nucleic Acids Res 2013 41 e75 10.1093/nar/gkt003 23335788 PMC3627563 · DOI
  18. [21]Haubold B Klotzl F Pfaffelhuber P andi: fast and accurate estimation of evolutionary distances between closely related genomes Bioinformatics 2015 31 1169 75 10.1093/bioinformatics/btu815 25504847 · DOI
  19. [22]Fan H Ives AR Surget-Groba Y Cannon CH An assembly and alignment-free method of phylogeny reconstruction from next-generation sequencing data BMC Genomics 2015 16 522 10.1186/s12864-015-1647-5 26169061 PMC4501066 · DOI
  20. [23]Konstantinidis KT Tiedje JM Genomic insights that advance the species definition for prokaryotes Proc Natl Acad Sci U S A 2005 102 2567 72 10.1073/pnas.0409727102 15701695 PMC549018 · DOI
  21. [24]Schatz MC Phillippy AM The rise of a digital immune system Gigascience 2012 1 4 10.1186/2047-217X-1-4 23587178 PMC3617452 · DOI
  22. [26]Saitou N Nei M The neighbor-joining method: a new method for reconstructing phylogenetic trees Mol Biol Evol 1987 4 406 25 3447015
  23. [27]Miller W Rosenbloom K Hardison RC Hou M Taylor J Raney B 28-way vertebrate alignment and conservation track in the UCSC Genome Browser Genome Res 2007 17 1797 808 10.1101/gr.6761107 17984227 PMC2099589 · DOI
  24. [29]Kuhner MK Felsenstein J A simulation comparison of phylogeny algorithms under equal and unequal evolutionary rates Mol Biol Evol 1994 11 459 68 8015439
  25. [30]Loman NJ Quick J Simpson JT A complete bacterial genome assembled de novo using only nanopore sequencing data Nat Methods 2015 12 733 5 10.1038/nmeth.3444 26076426 · DOI
  26. [31]Song L Florea L Langmead B Lighter: fast and memory-efficient sequencing error correction without counting Genome Biol 2014 15 509 10.1186/s13059-014-0509-9 25398208 PMC4248469 · DOI
  27. [32]Seth S Valimaki N Kaski S Honkela A Exploration and retrieval of whole-metagenome sequencing samples Bioinformatics 2014 30 2471 9 10.1093/bioinformatics/btu340 24845653 PMC4230234 · DOI
  28. [33]Maillet N Lemaitre C Chikhi R Lavenier D Peterlongo P Compareads: comparing huge metagenomic experiments BMC Bioinformatics 2012 13 Suppl 19 S10 10.1186/1471-2105-13-S19-S10 23282463 PMC3526429 · DOI
  29. [34]Maillet N Collet G Vannier T Lavenier D Peterlongo P COMMET: comparing and combining multiple metagenomic datasets 2014 IEEE International Conference on Bioinformatics and Biomedicine (BIBM): IEEE 2014
  30. [35]Rusch DB Halpern AL Sutton G Heidelberg KB Williamson S Yooseph S The Sorcerer II Global Ocean Sampling expedition: northwest Atlantic through eastern tropical Pacific PLoS Biol 2007 5 e77 10.1371/journal.pbio.0050077 17355176 PMC1821060 · DOI
  31. [36]Human Microbiome Project C Structure, function and diversity of the healthy human microbiome Nature 2012 486 207 14 10.1038/nature11234 22699609 PMC3564958 · DOI · Paper page
  32. [38]Freedman MJ Nissim K Pinkas B Efficient private matching and set intersection Advances in Cryptology - Eurocrypt 2004, Proceedings 2004 3027 1 19 10.1007/978-3-540-24676-3_1 · DOI
  33. [39]De Cristofaro E Faber S Gasti P Tsudik G Genodroid: are privacy-preserving genomic tests ready for prime time? Proceedings of the 2012 ACM workshop on Privacy in the electronic society 2012 Raleigh, NC ACM
  34. [40]Solomon B Kingsford C Large-scale search of transcriptomic read sets with sequence bloom trees bioRxiv 2015
  35. [41]Fofanov Y Luo Y Katili C Wang J Belosludtsev Y Powdrill T How independent are the appearances of n-mers in different genomes? Bioinformatics 2004 20 2421 8 10.1093/bioinformatics/bth266 15087315 · DOI
  36. [43]Roberts M Hunt BR Yorke JA Bolanos RA Delcher AL A preprocessor for shotgun assembly of large genomes J Comput Biol 2004 11 734 52 10.1089/cmb.2004.11.734 15579242 · DOI
  37. [44]Deorowicz S Kokot M Grabowski S Debudaj-Grabysz A KMC 2: fast and resource-frugal k-mer counting Bioinformatics 2015 31 1569 76 10.1093/bioinformatics/btv022 25609798 · DOI
  38. [46]Patrascu M Thorup M The power of simple tabulation hashing J ACM 2012 59 14 10.1145/2220357.2220361 · DOI
  39. [47]Ukkonen E Approximate string-matching with Q-grams and maximal matches Theor Comput Sci 1992 92 191 211 10.1016/0304-3975(92)90143-4 · DOI
  40. [48]Bar-Yossef Z, Jayram TS, Kumar R, Sivakumar D, Trevisan L. Counting distinct elements in a data stream. In: Proceedings of the 6th International Workshop on Randomization and Approximation Techniques. Springer-Verlag; 2002. p. 1–10.
  41. [49]Phillippy AM Schatz MC Pop M Genome assembly forensics: finding the elusive mis-assembly Genome Biol 2008 9 R55 10.1186/gb-2008-9-3-r55 18341692 PMC2397507 · DOI
  42. [60]Siek JG Lee L-Q Lumsdaine A The Boost Graph Library: User Guide and Reference Manual 2001 New York, NY Pearson Education
  43. [62]Kamada T Kawai S An algorithm for drawing general undirected graphs Inform Process Lett 1989 31 7 15 10.1016/0020-0190(89)90102-6 · DOI
  44. [63]Bankevich A Nurk S Antipov D Gurevich AA Dvorkin M Kulikov AS SPAdes: a new genome assembly algorithm and its applications to single-cell sequencing J Comput Biol 2012 19 455 77 10.1089/cmb.2012.0021 22506599 PMC3342519 · DOI

Cited by

Sorted by citations

Authors
Ondov, B., Treangen, T. J., Melsted, P., Mallonee, A. B., Bergman, N. H., Koren, S., & Phillippy, A. M.
Affiliations
  • University of Iceland (IS)
  • National Institutes of Health (US)
Corresponding author
Adam M. Phillippy
ORCID
Venue
Genome biology
Publisher
Springer Science and Business Media LLC
Published
2016-06-20
Volume
17
Issue
1
Pages
132-132
ISSN
  • 1465-6906 (ISSN-L)
  • 1474-760X
DOI
10.1186/s13059-016-0997-x
PMC
PMC4915045
OpenAlex
W2950150251
Cited by
3,373
References
10
Citations by year
2026: 435 · 2025: 489 · 2024: 445 · 2023: 396 · 2022: 421 · 2021: 436 · 2020: 314 · 2019: 219 · 2018: 127 · 2017: 66 · 2016: 20 · 2012: 1
FWCI
75.04
Type
journal article
Language
en
Open access
Licence
Locations
  • Genome biology (publishedVersion, cc-by)
  • bioRxiv (Cold Spring Harbor Laboratory) (acceptedVersion, cc-by)
  • PubMed Central (publishedVersion, cc-by)
  • PubMed (publishedVersion)
Funders
  • National Human Genome Research Institute (Intramural Research Program)
  • Science and Technology Directorate (HSHQDC-07-C-00020)
Topics
  • Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › Genomics and Phylogenetic Studies
  • Physical Sciences › Computer Science › Artificial Intelligence › Algorithms and Data Compression
  • Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › Fractal and DNA sequence analysis
Keywords
MinHash, sequence clustering, sequence database searching, dimensionality reduction
MeSH terms
Phylogeny, Software, Cluster Analysis, Genome, Evolution, Molecular, Genomics, Databases, Nucleic Acid, Metagenome, Metagenomics

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review