On weighted k-mer dictionaries

Abstract

Abstract We consider the problem of representing a set of $$k$$ k -mers and their abundance counts, or weights, in compressed space so that assessing membership and retrieving the weight of a $$k$$ k -mer is efficient. The representation is called a weighted dictionary of $$k$$ k -mers and finds application in numerous tasks in Bioinformatics that usually count $$k$$ k -mers as a pre-processing step. In fact, $$k$$ k -mer counting tools produce very large outputs that may result in a severe bottleneck for subsequent processing. In this work we extend the recently introduced SSHash dictionary (Pibiri in Bioinformatics 38:185–194, 2022) to also store compactly the weights of the $$k$$ k -mers. From a technical perspective, we exploit the order of the $$k$$ k -mers represented in SSHash to encode runs of weights, hence allowing much better compression than the empirical entropy of the weights. We study the problem of reducing the number of runs in the weights to improve compression even further and give an optimal algorithm for this problem. Lastly, we corroborate our findings with experiments on real-world datasets and comparison with competitive alternatives. Up to date, SSHash is the only $$k$$ k -mer dictionary that is exact, weighted, associative, fast, and small.

Keywords

• k-mers
• Compression
• Hashing
• Graphs
• Path cover