Dashing: fast and accurate genomic distances with HyperLogLog

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Accurate and rapid estimation of genomic similarity is crucial for comparative genomics.
• Existing methods like MinHash have limitations in speed and accuracy across diverse datasets.
• Scalability is a key challenge when analyzing large-scale genomic data.

Purpose of the Study:

• To introduce Dashing, a novel software tool for fast and accurate genome similarity estimation.
• To evaluate Dashing's performance against existing methods in terms of speed and accuracy.
• To demonstrate Dashing's capability in handling large-scale genomic datasets.

Main Methods:

• Utilizes the HyperLogLog (HLL) sketch algorithm for data summarization.
• Employs specialized cardinality estimation techniques for set unions and intersections.
• Implements optimized algorithms for rapid sketching and pairwise distance calculations.

Main Results:

• Dashing achieves significantly faster genome summarization compared to MinHash-based approaches.
• Demonstrates superior accuracy across various input and sketch sizes.
• Successfully processed and calculated pairwise distances for over 87,000 genomes in just 6 minutes.

Conclusions:

• Dashing offers a highly efficient and accurate solution for estimating genomic similarities.
• The HyperLogLog approach provides a scalable and effective alternative for large-scale genomic analyses.
• Dashing is an open-source tool, promoting accessibility and further development in the field.