Optimizing sparse and skew hashing: faster k -mer dictionaries
Bioinformatics · 01.07.2026 · 42 (Supplement_1)
DOI: 10.1093/bioinformatics/btag264 ↗Kurz gefasst
Fachartikel in der Zeitschrift Bioinformatics, online erschienen am 07.07.2026. Verfasst von Giulio Ermanno Pibiri und 1 weiteren Autor:innen. Beteiligte Einrichtung: DAIS, Ca' Foscari University of Venice, Venice, Italy. Hauptthemen laut MEDLINE: Algorithms, Computational Biology. Die Arbeit wurde bisher 2-mal zitiert (Crossref) und nennt 26 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: NIH HHS, NHGRI NIH HHS, Silicon Valley Community Foundation.
Abstract (Originalsprache)
Motivation Representing a set of k-mers—strings of length k—in small space under fast lookup queries is a fundamental requirement for several applications in Bioinformatics. A data structure based on sparse and skew hashing (SSHash) was recently proposed for this purpose (Pibiri 2022): it combines good space effectiveness with fast lookup and streaming queries. It is also order-preserving, i.e. consecutive k-mers (sharing a prefix-suffix overlap of length k−1) are assigned consecutive hash codes which helps compressing satellite data typically associated with k-mers, like abundances and color sets in colored De Bruijn graphs. Results We study the problem of accelerating queries under the sparse and skew hashing indexing paradigm, without compromising its space effectiveness. We propose a refined data structure with less complex lookups and fewer cache misses. We give a simpler and faster algorithm for streaming lookup queries. The refined architecture translates to substantial performance gains, outperforming the original version of SSHash in both index construction speed and query efficiency. Compared to indexes with similar capabilities and based on the Burrows-Wheeler transform, like SBWT and FMSI, SSHash is significantly faster to build and query. SSHash is competitive in space with the fast (and default) modality of SBWT when both k-mer strands are indexed. While larger than FMSI, it is also more than one order of magnitude faster to query. Availability and Implementation The SSHash software is available at https://github.com/jermp/sshash, and also distributed via Bioconda. A benchmark of data structures for k-mer sets is available at https://github.com/jermp/kmer_sets_benchmark. The datasets used in this article are described and available at https://zenodo.org/records/17582116.
Schlagwörter
MeSH-Schlagwörter (MEDLINE)
Autor:innen und Institutionen
- DAIS, Ca' Foscari University of Venice, Venice, Italy.
- Department of Computer Science, University of Maryland, College Park, MD 20440, United States.
Förderung
- NIH HHS
- NHGRI NIH HHS
- Silicon Valley Community Foundation
- Chan Zuckerberg Initiative DAF
- NIH
Zitieren
APA
Pibiri, G. E., & Patro, R. (2026). Optimizing sparse and skew hashing: faster k -mer dictionaries. Bioinformatics, 42(Supplement_1). https://doi.org/10.1093/bioinformatics/btag264
Vancouver
Pibiri GE, Patro R. Optimizing sparse and skew hashing: faster k -mer dictionaries. Bioinformatics. 2026;42(Supplement_1). doi:10.1093/bioinformatics/btag264
BibTeX
@article{Pibiri2026,
author = {Pibiri, Giulio Ermanno and Patro, Rob},
title = {Optimizing sparse and skew hashing: faster k -mer dictionaries},
journal = {Bioinformatics},
year = {2026},
volume = {42},
number = {Supplement_1},
doi = {10.1093/bioinformatics/btag264}
}
EUVIMED