Estimating similarity and distance using FracMinHash.

Area of Science:

• Computational Biology
• Bioinformatics
• Genomics

Background:

• Genomic and metagenomic data analysis requires scalable computational models.
• Sketching techniques, particularly FracMinHash, are valuable for large-scale biological data analysis.
• While FracMinHash is established for Jaccard and containment indices, theoretical gaps exist for other metrics.

Purpose of the Study:

• To develop a theoretical framework for estimating similarity/distance metrics using FracMinHash sketches.
• To establish conditions for sound estimation and recommend parameters for accuracy.
• To introduce a novel, efficient FracMinHash sketch generator.

Main Methods:

• Developed a theoretical framework for FracMinHash-based metric estimation.
• Identified conditions and scale factors for accurate estimation.
• Implemented frac-kmc, a parallel FracMinHash sketch generation tool.

Main Results:

• Validated theoretical findings with experimental evidence.
• frac-kmc demonstrated to be the fastest FracMinHash sketch generator.
• Achieved accurate and precise cosine similarity estimation on real genomic data using frac-kmc.

Conclusions:

• The theoretical framework enables sound estimation of various metrics from FracMinHash sketches.
• frac-kmc offers a significant speedup and parallelization for sketch generation.
• This work enhances the utility of FracMinHash for large-scale genomic data analysis.