Fast Spaced Seed Hashing

Hashing $k$-mers is a common function across many bioinformatics applications and it is widely used for indexing, querying and rapid similarity search. Recently, spaced seeds, a special type of pattern that accounts for errors or mutations, are routinely used instead of $k$-mers. Spaced seeds allow to improve the sensitivity, with respect to $k$-mers, in many applications, however the hashing of spaced seeds increases substantially the computational time. Hence, the ability to speed up hashing operations of spaced seeds would have a major impact in the field, making spaced seed applications not only accurate, but also faster and more efficient.
In this paper we address the problem of efficient spaced seed hashing. The proposed algorithm FSH exploits the similarity of adjacent spaced seed hash values in an input sequence in order to efficiently compute the next hash. We report a series of experiments on reads hashing using several spaced seeds. In the experiments, our algorithm can compute the hashing values of spaced seeds with a speedup, with respect to the traditional approach, between 1.6x to 5.3x, depending on the structure of the spaced seed.


The program FSH can be found at the repository: FSH


The software is freely available for academic use.
For questions about the tool, please contact Matteo Comin.


Please cite the following paper:
M.Comin, S.Girotto, C.Pizzi
Fast Spaced Seed Hashing
Accepted at the 17th The Workshop on Algorithms in Bioinformatics (WABI) 2017.