Mash: fast genome and metagenome distance estimation using MinHash

被引:1776
作者
Ondov, Brian D. [1 ]
Treangen, Todd J. [1 ]
Melsted, Pall [2 ]
Mallonee, Adam B. [1 ]
Bergman, Nicholas H. [1 ]
Koren, Sergey [3 ]
Phillippy, Adam M. [3 ]
机构
[1] Natl Biodef Anal & Countermeasures Ctr, Frederick, MD USA
[2] Univ Iceland, Fac Ind Engn, Mech Engn & Comp Sci, Reykjavik, Iceland
[3] NHGRI, Genome Informat Sect, Computat & Stat Genom Branch, NIH, Bethesda, MD 20892 USA
来源
GENOME BIOLOGY | 2016年 / 17卷
基金
美国国家卫生研究院;
关键词
Comparative genomics; Genomic distance; Alignment; Sequencing; Nanopore; Metagenomics; ALIGNMENT; SIMILARITY; ALGORITHM; SEQUENCES; SEARCH;
D O I
10.1186/s13059-016-0997-x
中图分类号
Q81 [生物工程学(生物技术)]; Q93 [微生物学];
学科分类号
071005 ; 0836 ; 090102 ; 100705 ;
摘要
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).
引用
收藏
页数:14
相关论文
共 55 条
  • [1] BASIC LOCAL ALIGNMENT SEARCH TOOL
    ALTSCHUL, SF
    GISH, W
    MILLER, W
    MYERS, EW
    LIPMAN, DJ
    [J]. JOURNAL OF MOLECULAR BIOLOGY, 1990, 215 (03) : 403 - 410
  • [2] [Anonymous], 2001, The Boost Graph Library: User Guide and Reference Manual, Portable Documents
  • [3] SPAdes: A New Genome Assembly Algorithm and Its Applications to Single-Cell Sequencing
    Bankevich, Anton
    Nurk, Sergey
    Antipov, Dmitry
    Gurevich, Alexey A.
    Dvorkin, Mikhail
    Kulikov, Alexander S.
    Lesin, Valery M.
    Nikolenko, Sergey I.
    Son Pham
    Prjibelski, Andrey D.
    Pyshkin, Alexey V.
    Sirotkin, Alexander V.
    Vyahhi, Nikolay
    Tesler, Glenn
    Alekseyev, Max A.
    Pevzner, Pavel A.
    [J]. JOURNAL OF COMPUTATIONAL BIOLOGY, 2012, 19 (05) : 455 - 477
  • [4] Bar-Yossef Z., 2002, Randomization and Approximation Techniques in Computer Science. 6th International Workshop, RANDOM 2002. Proceedings (Lecture Notes in Computer Science Vol.2483), P1
  • [5] Assembling large genomes with single-molecule sequencing and locality-sensitive hashing
    Berlin, Konstantin
    Koren, Sergey
    Chin, Chen-Shan
    Drake, James P.
    Landolin, Jane M.
    Phillippy, Adam M.
    [J]. NATURE BIOTECHNOLOGY, 2015, 33 (06) : 623 - +
  • [7] On the resemblance and containment of documents
    Broder, AZ
    [J]. COMPRESSION AND COMPLEXITY OF SEQUENCES 1997 - PROCEEDINGS, 1998, : 21 - 29
  • [8] Broder AZ, 2000, LECT NOTES COMPUT SC, V1848, P1
  • [9] Chum O., 2008, P BRIT MACH VIS C 20
  • [10] De Cristofaro E, 2012, P 2012 ACM WORKSH PR