Dashing 2: genomic sketching with multiplicities and locality-sensitive hashing
Preprint
Abstract
A genomic sketch is a small, probabilistic representation of the set of k-mers in a sequencing dataset. Sketches are building blocks for large-scale analyses that consider similarities between many pairs of sequences or sequence collections. While existing tools can easily compare 10,000s of genomes, relevant datasets can reach millions of sequences and beyond. Popular tools also fail to consider k -mer multiplicities, making them less applicable in quantitative settings. We describe a method called Dashing 2 that builds on the SetSketch data structure. SetSketch is related to HyperLogLog, but discards use of leading zero count in favor of a truncated logarithm of adjustable base. Unlike HLL, SetSketch can perform multiplicity-aware sketching when combined with the ProbMinHash method. Dashing 2 integrates locality-sensitive hashing to scale all-pairs comparisons to millions of sequences. Dashing 2 is free, open source software available at https://github.com/dnbaker/dashing2Keywords
All Related Versions
- Published version: Genome Research, 33 (7), 1218.
This publication has 19 references indexed in Scilit:
- Locality-sensitive hashing for the edit distanceBioinformatics, 2019
- High throughput ANI analysis of 90K prokaryotic genomes reveals clear species boundariesNature Communications, 2018
- BagMinHash - Minwise Hashing Algorithm for Weighted Sets2018
- Mash: fast genome and metagenome distance estimation using MinHashGenome Biology, 2016
- Reference sequence (RefSeq) database at NCBI: current status, taxonomic expansion, and functional annotationNucleic Acids Research, 2015
- Lighter: fast and memory-efficient sequencing error correction without countingGenome Biology, 2014
- BigWig and BigBed: enabling browsing of large distributed datasetsBioinformatics, 2010
- Local homology recognition and distance measures in linear time using compressed amino acid alphabetsNucleic Acids Research, 2004
- A Fast, Compact Approximation of the Exponential FunctionNeural Computation, 1999
- Pracniques: further remarks on reducing truncation errorsCommunications of the ACM, 1965