Optimizing sparse and skew hashing: faster k -mer dictionaries

Area of Science:

• Bioinformatics
• Computational Biology
• Data Structures

Background:

• Efficiently representing k-mer sets is crucial for bioinformatics applications.
• The sparse and skew hashing (SSHash) data structure offers space effectiveness and fast queries.
• SSHash is order-preserving, aiding in the compression of associated k-mer data.

Purpose of the Study:

• To accelerate queries within the SSHash indexing paradigm without sacrificing space efficiency.
• To develop a refined data structure with optimized lookup complexity and reduced cache misses.
• To provide a simpler and faster algorithm for streaming k-mer lookups.

Main Methods:

• Proposing a refined data structure for sparse and skew hashing.
• Developing a new algorithm for streaming lookup queries.
• Benchmarking against existing k-mer indexing structures like SBWT and FMSI.

Main Results:

• The refined SSHash structure achieves less complex lookups and fewer cache misses.
• A simpler and faster algorithm for streaming lookup queries is presented.
• SSHash demonstrates significant speed improvements in both construction and querying compared to SBWT and FMSI, while maintaining competitive space efficiency.

Conclusions:

• The enhanced SSHash provides a faster and more efficient method for k-mer representation and querying in bioinformatics.
• The proposed refinements maintain or improve upon the space-effectiveness of SSHash.
• SSHash offers a compelling alternative to existing indexing methods, particularly for applications requiring high query performance.