Fast Hashing of Spaced Seeds with DuoHash

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Alignment-free methods and k-mer statistics are crucial for high-throughput sequence analysis.
• Spaced seeds improve sensitivity over k-mers for tasks like similarity search but are computationally intensive.
• Efficient spaced seed hashing is needed to overcome computational bottlenecks in sequence analysis.

Purpose of the Study:

• To present DuoHash, a novel framework for efficient spaced seed hashing.
• To accelerate the computation of hash values for spaced seeds in DNA sequences.
• To demonstrate the utility of DuoHash for spaced k-mer counting.

Main Methods:

• Developed DuoHash, a framework utilizing efficient spaced seed binary encoding.
• Incorporated precomputed tables to accelerate hash value computation for forward and reverse DNA strands.
• Evaluated DuoHash performance against existing algorithms on short reads.

Main Results:

• DuoHash achieves speedups of up to 11x compared to existing algorithms for medium-density spaced seeds.
• Demonstrated significant performance improvements in spaced k-mer counting.
• The framework effectively handles the computational demands of spaced seed hashing.

Conclusions:

• DuoHash provides a substantial performance improvement for spaced seed hashing in sequence analysis.
• The framework is applicable to critical tasks like spaced k-mer counting and similarity search.
• DuoHash enhances the efficiency of high-throughput genomic data processing.