Approximate Hashing for Bioinformatics

Guy Arbitman (1) , Shmuel T Klein (1) , Pierre Peterlongo (2) , Dana Shapira (3)

1 Department of Computer Science [Bar Ilan]
2 GenScale - Scalable, Optimized and Parallel Algorithms for Genomics
3 AUC - Ariel University Center

The paper extends ideas from data compression by deduplication to the Bioinformatic field. The specific problems on which we show our approach to be useful are the clustering of a large set of DNA strings and the search for approximate matches of long substrings, both based on the design of what we call an approximate hashing function. The outcome of the new procedure is very similar to the clustering and search results obtained by accurate tools, but in much less time and with less required memory.

Domaines: Bio-informatique [q-bio.QM]

Guy Arbitman, Shmuel T Klein, Pierre Peterlongo, Dana Shapira. Approximate Hashing for Bioinformatics. CIAA 2021 - 25th International Conference on Implementation and Application of Automata, Jul 2021, Bremen, Germany. pp.1-12. ⟨hal-03219482⟩