Binary search and and set operations on compacted k -mer lists

Sorted lists of elements are particularly good for computing set operations. A single scan of the two lists is sufficient to materialize or count the results of the union, intersection, difference, and xor operators. In bioinformatics, only a few tools are designed to perform these operations on k -mers. A fast tool like KMC allows set operations at the cost of storing individual k -mers.

In this paper, we introduce a novel way to represent sorted k -mers as a collection of recomposed super- k -mer sorted lists. We introduce the concept of virtual super- k -mer and show how to construct, query and perform set operations on sorted lists of virtual super- k -mers.

In the implementation sklib, we demonstrate high throughput of the data structure for construction and set operations, while remaining competitive in query capabilities, within a controlled memory footprint (2–5x decrease in bits/element compared to KMC).