Researchers have developed a theoretical framework and a new software tool to improve the speed and accuracy of estimating similarity and distance metrics in genomic data. Published in Algorithms for Molecular Biology, the study by Mahmudur Rahman Hera and David Koslicki addresses the growing computational burden associated with analyzing large-scale genomic and metagenomic datasets. The work focuses on FracMinHash, a sketching technique that creates compressed representations of biological sequences to facilitate rapid comparisons. By establishing conditions under which these sketches can reliably estimate various similarity measures, the authors provide a robust foundation for scalable genomic analysis.
The increasing volume of genomic data necessitates computational models that are both scalable and precise. Traditional methods often struggle with the vast number of distinct k-mers found in sequencing samples. Sketching methods address this by creating a fingerprint, or sketch, of the k-mers, reducing the computational resources required for many-versus-many comparisons. FracMinHash has emerged as a popular technique in this domain, retaining a variable fraction of the input set of k-mers based on a tunable scale factor. While previous studies established unbiased estimators for containment and Jaccard indices, theoretical investigations for other metrics remained lacking.
The study presents a theoretical framework for estimating similarity and distance metrics using FracMinHash sketches when the metric is expressible in a specific mathematical form. The authors demonstrate that for a class of similarity and distance measures, there exists a scale factor for which the metric can be accurately measured by the sketches. This includes cosine similarity, Bray-Curtis dissimilarity, the first Kulczynski measure, and the Sorensen index. The theoretical analysis identifies conditions under which the estimation is sound, ensuring that the similarity between sketched sets approximates the similarity of the original sets with high probability.
Central to the theoretical contribution is the derivation of a recommended minimum scale factor for accurate results. The authors show that the probability of the estimated cosine similarity falling within a certain error range depends on the scale factor and the size of the sets being compared. For highly dissimilar sets, the probability guarantee becomes less meaningful, but the estimation remains reasonable as the estimated similarity reflects the dissimilarity. The study provides formulas to determine the scale factor based on desired confidence levels and tolerable error rates, allowing researchers to optimize computational efficiency without sacrificing accuracy.
In addition to the theoretical framework, the authors developed frac-kmc, a fast and efficient FracMinHash sketch generator program. frac-kmc is described as the fastest known FracMinHash sketch generator, offering accurate and precise results for cosine similarity estimation on real data. A key advantage of frac-kmc is its parallel capability, allowing for the speeding up of sketch generation using multiple CPU cores. This parallelism is an option lacking in existing serialized tools such as sourmash, which processes k-mers in a serialized manner and cannot parallelize the computation of a FracMinHash sketch.
Experimental results demonstrate that frac-kmc significantly outperforms existing tools in terms of speed. When run on 32 threads, frac-kmc finishes roughly 10 times faster than sourmash and roughly 6.7 times faster than Mash. Even on a single thread, frac-kmc runs up to 70% faster than sourmash for large files. The tool was tested on fastq.gz files containing metagenome samples from the Human Microbiome Project. The sketches produced by frac-kmc were verified to be identical to those produced by sourmash, confirming the correctness of the implementation. The speed improvements are particularly notable for large input files, where serialized tools face significant bottlenecks.
The accuracy of frac-kmc in estimating similarity metrics was evaluated using two datasets: the Ecoli dataset, containing 3,682 E. coli genome assemblies, and the HMP dataset, containing 300 metagenome samples from the human gut. The study compared the performance of frac-kmc against Simka and Mash. Simka, which uses all k-mers, was found to be extremely slow, failing to exit after more than 48 hours for 125 samples. Mash, which uses fixed-size MinHash sketches, was faster but less accurate. frac-kmc, while running 40-50% slower than Mash, offered a great improvement in accuracy for estimating cosine similarity and Bray-Curtis dissimilarity.
The resource usage of frac-kmc varies depending on the dataset. For the Ecoli dataset, where samples are small genomes, the wall-clock time and memory footprint are similar to Mash. However, for the HMP dataset, which consists of large metagenomes, frac-kmc runs about 2 to 2.1 times slower than Mash and uses roughly 100 times more memory. This higher resource usage is attributed to the larger FracMinHash sketches produced by frac-kmc, which facilitate the highly accurate results observed in the experiments. The trade-off between speed and accuracy is a critical consideration for researchers choosing between these tools.
The theoretical findings were supported by simulations showing that the recommended scale factors ensure that the estimated cosine similarity falls within the tolerable error range. In contrast, using a preset scale factor, such as the default 1/1000 in sourmash, can result in errors higher than expected, particularly when the input sets are not sufficiently large. The study highlights the importance of selecting an appropriate scale factor based on the specific requirements of the analysis, rather than relying on default values. This approach allows for more reliable similarity estimation in diverse genomic applications.
The implications of this work extend to various fields, including metagenomics, ecology, and community studies. The ability to rapidly and accurately estimate similarity and distance metrics using FracMinHash sketches can enhance the analysis of large-scale genomic data. The development of frac-kmc provides a practical tool for researchers to implement these theoretical insights. The study underscores the need for scalable and robust computational models in the face of exponential data growth. By providing both theoretical guarantees and an efficient implementation, the authors contribute to the advancement of genomic analysis techniques.
Limitations of the study include the focus on specific metrics and the assumption of strongly universal hash functions in the theoretical analysis. In practice, most FracMinHash implementations use MurMurHash3, which does not have a guarantee of universality. However, practical implementations yield results conforming to the theory developed in the study. The authors note that further improvements could involve studying other metrics that do not follow an agreeable mathematical form, such as Chord distance and Hellinger distance. Additionally, the code used to read sketches is written in Python, and a well-written C++ implementation may improve performance further.
The study concludes that sketching-based methods allow practitioners to lower computational resource usage while maintaining reasonable accuracy. The analysis of FracMinHash in estimating an array of similarity and distance metrics provides valuable insights into the conditions for reliable estimation. The introduction of frac-kmc as a fast and parallel tool addresses the need for efficient sketch generation. The findings suggest that when very large sequence files need to be sketched, using frac-kmc can be especially useful. This work lays the groundwork for future developments in genomic sketching techniques and their applications in large-scale data analysis.
The theoretical framework presented in the study relies on the properties of strongly 2-universal hash functions, which ensure that the hash values of distinct elements are uniformly distributed and independent. This mathematical foundation allows the authors to derive concentration bounds for the number of elements retained in a FracMinHash sketch. Specifically, the expected number of elements in a sketch is directly proportional to the scale factor and the size of the original set. The authors demonstrate that the actual number of elements in the sketch is well-concentrated around this expected value, with the probability of deviation decreasing exponentially as the set size or scale factor increases. This concentration property is critical for guaranteeing that the similarity metrics computed from the sketches closely approximate the metrics computed from the full sets.
For metrics such as the Jaccard index and containment index, the study confirms that unbiased estimators can be derived directly from the FracMinHash sketches. However, for other metrics like cosine similarity and Bray-Curtis dissimilarity, proving an unbiased estimator is not mathematically tractable. Instead, the authors establish conditions under which the estimated metric falls within a specified relative error of the true metric with high probability. The probability of this approximation holding depends on the size of the intersection between the two sets being compared. When the sets are highly dissimilar and their intersection is small, the probability guarantee becomes less meaningful, although the estimated similarity remains low, reflecting the underlying dissimilarity of the original data.
The practical implementation of frac-kmc was developed by modifying the source code of the k-mer counter KMC to retain only those k-mers whose hash values fall below a specific threshold. This approach avoids the need to iterate through all k-mers in the output, significantly reducing computational overhead. The tool uses the 64-bit MurMurHash function, which, while not theoretically guaranteed to be strongly universal, yields results in practice that conform to the theoretical predictions. The authors verified the correctness of frac-kmc by comparing its output with that of sourmash, confirming that the sketches produced by both programs are identical. This verification step ensures that the speed improvements in frac-kmc do not come at the cost of accuracy or compatibility with existing workflows.
The experimental evaluation of frac-kmc on real biological data revealed distinct performance characteristics depending on the nature of the input samples. For the E. coli dataset, which consists of many small genome assemblies, frac-kmc and Mash exhibited similar wall-clock times and memory footprints. In contrast, for the Human Microbiome Project dataset, which includes large metagenomic samples, frac-kmc required approximately 100 times more memory than Mash and ran about two times slower. This increased resource usage is a direct consequence of the larger FracMinHash sketches generated for metagenomic data, which contain more k-mers than the fixed-size MinHash sketches used by Mash. Despite the higher memory consumption, frac-kmc provided more accurate estimates of cosine similarity and Bray-Curtis dissimilarity, demonstrating a trade-off between resource efficiency and estimation precision.
The study also highlights the limitations of using default scale factors in existing tools. The default scale factor of 1/1000 in sourmash may not be sufficient to achieve high accuracy when the input sets are not sufficiently large. The authors show that for smaller sets, a larger scale factor is required to keep the estimation error within acceptable bounds. This finding underscores the importance of selecting an appropriate scale factor based on the specific characteristics of the data being analyzed. The recommended scale factor formulas provided in the study allow researchers to balance computational efficiency with estimation accuracy, ensuring that the results are reliable for downstream applications in genomics and metagenomics.
Subject of Research: Estimating similarity and distance using FracMinHash
Article Title: Estimating similarity and distance using FracMinHash
Article References: Rahman Hera, M., & Koslicki, D. (2025). Estimating similarity and distance using FracMinHash. Algorithms for Molecular Biology, 20(1), Article 8. https://doi.org/10.1186/s13015-025-00276-8
Image Credits: AI Generated
DOI: 10.1186/s13015-025-00276-8
Keywords: Estimating, similarity, distance, FracMinHash, scientific research, peer-reviewed research
News Source: Juliet Wilcox. (November 10, 2026). New Tool Speeds Up Genomic Similarity Estimation. Scienmag.
