FSH: fast spaced seed hashing exploiting adjacent hashes

Area of Science:

• Bioinformatics
• Computational Biology
• Sequence Analysis

Background:

• Spaced seeds offer higher sensitivity than k-mers in bioinformatics for similarity searches.
• Traditional spaced seed hashing is computationally intensive, requiring recalculation for each position.
• This inefficiency limits the speed of applications relying on spaced seed indexing and querying.

Purpose of the Study:

• To develop a computationally efficient method for spaced seed hashing.
• To accelerate bioinformatics applications that utilize spaced seeds for sequence analysis.
• To enable faster and more efficient similarity searches in large biological datasets.

Main Methods:

• Introduced Fast Spaced-seed Hashing (FSH), a novel algorithm.
• FSH exploits the similarity of hash values between adjacent positions in sequences.
• Developed a generalized version for simultaneous hashing of multiple spaced seeds.

Main Results:

• FSH achieves a speedup of 1.6x to 5.3x compared to traditional methods.
• Experimental results demonstrate efficiency on metagenomics read datasets.
• The generalized algorithm efficiently handles multiple spaced seed computations.

Conclusions:

• FSH provides an efficient solution for the routine task of spaced seed hashing.
• The method significantly enhances the speed and efficiency of spaced seed applications.
• Opens avenues for further research into optimizing hashing techniques in bioinformatics.