K2R: Tinted de Bruijn graphs implementation for efficient read extraction from sequencing datasets

Biological sequence analysis often relies on reference genomes, but producing accurate assemblies remains a challenge. As a result, de novo analysis directly from raw reads, without preprocessing, is frequently more practical. A common task across many applications is to identify reads containing a given k-mer in a dataset-essential for genotyping, profiling, compression, error correction, and assembly. While this resembles the well-studied colored de Bruijn graph problem, solving it at the read level is typically too resource-intensive. We show that this challenge becomes tractable by making realistic assumptions about genome sequencing datasets. To address it, we introduce Tinted de Bruijn graphs, a variation of the colored de Bruijn graph in which each read is treated as a unique source. We developed K2R, a scalable index implementing this model efficiently. We benchmark K2R's performance (index size, memory usage, throughput, and construction time) against leading methods, including hashing techniques (Short Read Connector, Fulgor) and full-text indexing tools (Movi, Themisto). K2R successfully indexed two human datasets (T2T), handling up to 126X ONT coverage in under 9 hours with a peak of 61 GB RAM.

Developed in C++, K2R is open source and available at http://github.com/LeaVandamme/K2R.