Document - Sparse and skew hashing of K-mers

2022

Journal article Open Access

Sparse and skew hashing of K-mers

Pibiri G. E.

Bioinformatics Time trade-off method

MOTIVATION: A dictionary of k-mers is a data structure that stores a set of n distinct k-mers and supports membership queries. This data structure is at the hearth of many important tasks in computational biology. High-throughput sequencing of DNA can produce very large k-mer sets, in the size of billions of strings-in such cases, the memory consumption and query efficiency of the data structure is a concrete challenge. RESULTS: To tackle this problem, we describe a compressed and associative dictionary for k-mers, that is: a data structure where strings are represented in compact form and each of them is associated to a unique integer identifier in the range [0,n). We show that some statistical properties of k-mer minimizers can be exploited by minimal perfect hashing to substantially improve the space/time trade-off of the dictionary compared to the best-known solutions. AVAILABILITY AND IMPLEMENTATION: https://github.com/jermp/sshash. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Source: Bioinformatics (Oxf., Online) 38 (2022): i185–i194. doi:10.1093/bioinformatics/btac245

Publisher: Oxford University Press., Oxford, Regno Unito

Metrics

Back to previous page

Cite as

BibTeX entry

@article{oai:it.cnr:prodotti:468874,
	title = {Sparse and skew hashing of K-mers},
	author = {Pibiri G. E.},
	publisher = {Oxford University Press., Oxford, Regno Unito},
	doi = {10.1093/bioinformatics/btac245},
	journal = {Bioinformatics (Oxf., Online)},
	volume = {38},
	year = {2022}
}