EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

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

Jonas Schulte-Mattler iD, Knut Reinert iD

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).

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

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)

Sequence Analysis, DNASoftwareDNAGenomicsAlgorithmsHigh-Throughput Nucleotide Sequencing

Substanzen

DNA

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}
}
Kostenlos starten →