Optimizing sparse and skew hashing: faster k -mer dictionaries.

ABSTRACT:

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

SUBMITTER: Pibiri GE 

PROVIDER: S-EPMC12871628 | biostudies-literature | 2026 Jan

REPOSITORIES: biostudies-literature