FSH: Fast spaced seed hashing exploiting adjacent hashes

FSH is a tool for the fast computation of spaced seed hashings. It was developed with the support of the Italian Ministry of Education, University and Reasearch Research within the Project of National Interest PRIN 20122F87B2 ``Compositional Approaches for the Analysis and Mining of Omics Data", PI Cinzia Pizzi

Background: Patterns with wildcards in specified positions, namely spaced seeds, are increasingly used instead of k-mers in many bioinformatics applications that require indexing, querying and rapid similarity search, as they can provide better sensitivity. Many of these applications require to compute the hashing of each position in the input sequences with respect to the given spaced seed, or to multiple spaced seeds. While the hashing of k-mers can be rapidly computed by exploiting the large overlap between consecutive k-mers, spaced seeds hashing is usually computed from scratch for each position in the input sequence, thus resulting in slower processing.

Results: The method proposed in this paper, Fast Spaced-seed Hashing (FSH), exploits the similarity of the hash values of spaced seeds computed at adjacent positions in the input sequence. In our experiments we compute the hash for each positions of metagenomics reads from several datasets, with respect to different spaced seeds. We also propose a generalized version of the algorithm for the simultaneous computation of multiple spaced seeds hashing. 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.

Conclusions: Spaced seed hashing is a routine task for several bioinformatics application. FSH allows to perform this task efficiently and raise the question of whether other hashing can be exploited to further improve the speed up. This has the potential of major impact in the field, making spaced seed applications not only accurate, but also faster and more efficient.

Download

FSH was implemented by Samuele Girotto and it is freely available for academic us at FSH bitbucket repository.
Contact address: Cinzia Pizzi

Reference

If you use FSH, please cite:
S.Girotto, M.Comin, C.Pizzi: FSH: fast spaced seed hashing exploiting adjacent hashes
accepted at BMC Algorithms for Molecular Biology, 2018

A preliminary version appeared at WABI 2017:
S.Girotto, M.Comin, C.Pizzi: Fast Spaced Seed Hashing
17th Workshop on Algorithms in Bioinformatics - WABI 2017 Open access