Inverted colored de Bruijn Graph for practical kmer sets storage

Abstract

Petabases of sequencing data in the Sequence Read Archive (SRA) present a significant challenge for holistic reanalysis due to their sheer volume. Recent efforts have assembled this data into terabytes of unitigs, an efficient k-mer set representation that can reduce data size by an order of magnitude. However, these unitigs were compressed on a per-accession basis, leaving substantial cross-sample redundancy unexploited. While co-compression of related samples offers high space-saving potential, existing tools lack targeted decompression: the ability to retrieve specific documents at a cost proportional to their individual sizes rather than that of the entire collection. This paper introduces the "inverted de Bruijn graph" property, formalizing the concept of efficient targeted decompression, and presents kloe, its first implementation. kloe is a compression method for large, highly similar k-mer multi-sets, such as collections of unitigs from related samples. Unlike existing approaches that map k-mers to colors (samples), kloe takes a complementary route by performing color-to-k-mer mapping, associating samples with their respective k-mer sets. This enables targeted decompression of any chosen samples k-mer content. At its core, kloe utilizes a new sequence construct called "monochromatigs," drawing on concepts from simplitigs and monotigs to achieve both significant space savings and efficient retrieval. Finally, a central aim of this work is to highlight this novel problem area, which we argue is critically understudied compared to colored de Bruijn graphs. The associated tool is available as an open source project at github.com/TimRouze/KLOE