MaxGeomHash: An Algorithm for Variable-Size Random Sampling of Distinct Elements.

Area of Science:

• Bioinformatics and Computational Biology
• Genomics and Sequence Analysis
• Algorithm Design and Analysis

Background:

• The exponential growth of sequencing data necessitates scalable computational methods.
• K-mer sketching is a key technique for summarizing large sequence datasets.
• Existing methods like MinHash and FracMinHash have limitations in sketch size and scalability.

Purpose of the Study:

• To introduce MaxGeomHash, a novel sketching algorithm for efficient large-scale sequence analysis.
• To develop a permutation-invariant and parallelizable sketching algorithm producing sub-linear sketches.
• To provide a method that balances sketch size, storage, processing efficiency, and accuracy.

Main Methods:

• Developed the MaxGeomHash algorithm, producing sketches of size O(b log(n/b)) for parameter b.
• Introduced a variant, α-MaxGeomHash, generating sketches of size Θ(n^α).
• Studied algorithm properties, analyzed sample sizes, and empirically verified theoretical results.

Main Results:

• MaxGeomHash generates sub-linear, permutation-invariant, and parallelizable sketches.
• Empirical validation confirmed theoretical sample size predictions and similarity estimation quality.
• MaxGeomHash sketches enabled more accurate similarity tree construction than MinHash and more efficient than FracMinHash on genomic datasets.

Conclusions:

• MaxGeomHash offers an effective intermediate-sized sketching approach, balancing efficiency and accuracy.
• The algorithm provides a valuable new tool for large-scale genomic data analysis and comparison.
• The implementation is publicly available, facilitating further research and application.