Dashing

Dashing estimates genomic similarities and computes distances between sequencing datasets using HyperLogLog sketches for scalable cardinality estimation.

Key Features:

• HyperLogLog sketches: Employs HyperLogLog sketching for compact representation and cardinality estimation of k-mer sets from genomes and sequencing datasets.
• Cardinality estimation: Uses specialized cardinality estimation techniques tailored for set operations to estimate counts of distinct elements in large datasets.
• Set unions and intersections: Directly estimates set unions and intersections to support overlap and similarity calculations between genomic datasets.
• Memory efficiency: Leverages HyperLogLog properties to perform cardinality estimation on large sets with minimal memory usage.
• Accuracy across sizes: Maintains high accuracy over a broad spectrum of input and sketch sizes.
• Performance and scale: Provides faster processing than traditional MinHash-based methods and can sketch and compute pairwise distances across more than 87,000 genomes in about six minutes.
• Pairwise distance computation: Computes pairwise distance metrics between genomes or sequencing datasets using sketch-derived cardinalities.

Scientific Applications:

• Large-scale genome analysis: Enables rapid similarity and distance estimation across tens of thousands of genomes for population-scale studies.
• Comparative genomics: Supports comparison of genome content and k-mer overlap to identify shared and unique genomic regions.
• Evolutionary biology: Facilitates inference of genetic relationships and variation patterns via distance metrics derived from set overlaps.
• Rapid genomic comparisons: Allows quick screening and clustering of sequencing datasets based on sketch-derived similarities.

Methodology:

Uses HyperLogLog sketches combined with specialized cardinality estimation techniques to estimate set unions and intersections and compute pairwise distances while preserving accuracy across input and sketch sizes.