RSHash: a fast and space-efficient hash table for k -mers
Bioinformatics · 2026
DOI: 10.1093/bioinformatics/btag440 ↗Kurz gefasst
Fachartikel in der Zeitschrift Bioinformatics, 2026. Verfasst von Jonas Schulte-Mattler und 1 weiteren Autor:innen. Beteiligte Einrichtung: Institutfür Informatik, Freie Universität Berlin, Berlin 14195, Germany. Hauptthemen laut MEDLINE: Sequence Analysis, DNA, Software, DNA, Genomics. Die Arbeit nennt 14 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
Summary 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. Availability https://github.com/jonsmcode/rshash.
Schlagwörter
MeSH-Schlagwörter (MEDLINE)
Substanzen
Autor:innen und Institutionen
- Institutfür Informatik, Freie Universität Berlin, Berlin 14195, Germany.
- Max-Planck-Institut für Molekulare Genetik, Max-Planck-Gesellschaft, Berlin 14195, Germany.
ORCID-Profile: Jonas Schulte-Mattler, Knut Reinert
Zitieren
APA
Schulte-Mattler, J., & Reinert, K. (2026). RSHash: a fast and space-efficient hash table for k -mers. Bioinformatics. https://doi.org/10.1093/bioinformatics/btag440
Vancouver
Schulte-Mattler J, Reinert K. RSHash: a fast and space-efficient hash table for k -mers. Bioinformatics. 2026. doi:10.1093/bioinformatics/btag440
BibTeX
@article{SchulteMattler2026,
author = {Schulte-Mattler, Jonas and Reinert, Knut},
title = {RSHash: a fast and space-efficient hash table for k -mers},
journal = {Bioinformatics},
year = {2026},
doi = {10.1093/bioinformatics/btag440}
}
EUVIMED