Table 2 Examples of bioinformatic software utilizing sketching algorithms
Software | Purpose | Sketching algorithm |
|---|---|---|
GROOT [25] | Variant detection in metagenomes | MinHash (KHF) |
mashtree [26] | Phylogenetic tree construction | MinHash (KMV) |
MashMap [27] | Long read alignment | Minimizer/MinHash (KMV) |
MASH [1] | Sequence analysis | MinHash (KMV) |
sourmash [22] | Sequence analysis | MinHash (KMV) |
finch [23] | Sequence analysis | MinHash (KMV) |
MiniMap2 [28] | Read alignment | Minimizer |
ABySS [29] | Genome assembly | Bloom filter |
Lighter [30] | Sequencing error correction | Bloom filter |
BIGSI [31] | Sequence index and search | Bloom filter |
khmer [32] | Sequence analysis | Count-Min sketch |
FastEtch [33] | Genome assembly | Count-Min sketch |
dashing [2] | Sequence analysis | HyperLogLog |
krakenUniq [34] | Metagenome classification | HyperLogLog |
HULK [4] | Sequence analysis | Histosketch |
ntCard [35] | Sequence analysis | ntCard |
BBsketch [24] | Sequence analysis | MinHash |
MHAP [21] | Genome assembly | MinHash |
MC-MinH [20] | Sequence clustering | MinHash |
KmerGenie [36] | Sequence analysis | Count-Min sketch variant |
Squeakr [37] | Sequence analysis | Counting Quotient Filter |
Mantis [38] | Sequence index and search | Counting Quotient Filter |
kssd [39] | Sequence analysis | K-mer Substring Space Decomposition |