RSHash: a fast and space-efficient hash table for k-mers

Large genomic data collections can be viewed as a continuous string of DNA characters. The essential operations for data structures indexing the k-mer content of such a string are lookup and locate. Lookup determines whether a query k-mer q exists in the string and locate returns all locations in the string where q is present. High-throughput DNA sequencing generates very many k-mer sets of size exceeding billions of characters. In such scenarios, memory consumption and query efficiency pose significant challenges to a data structure supporting the above mentioned queries. To address this problem, we describe a simple, compressed, static data structure for k-mers that answers lookup and can be extended for supporting locate. The general scheme follows the use of minimizers like the state-of-the art SSHash. However, instead of using minimum perfect hash functions our solution (RSHash for Rank-Select Hash) relies on bitvectors with rank and select support, a multiple layered minimizer scheme, and a clever buffering strategy. We can show that RSHash is on average 40% and in some cases up to two times faster than SSHash while having the same memory requirements. Indeed we can go as low as 8 bits per canonical 31-mer on a human dataset.

https://github.com/jonsmcode/rshash.