Elucidating Transitions of <i>k</i> -mer-Based Objects Across <i>k</i> -mer Sizes

The widespread adoption of <i>k</i>-mers in computational biology has enabled efficient methods for utilizing genomic sequences in a variety of biological tasks. However, understanding the influence of <i>k</i>-mer sizes within these methods remains a persistent challenge. Slicing sequences into a fixed size lacks grounding in biological insight, and complex bioinformatics pipelines obscure the effect of the parameter <i>k</i> due to various noisy factors. The choice of <i>k</i>-mer size is typically arbitrary, with justification omitted in both the literature and method tutorials. Furthermore, the lack of theoretical understanding has caused recent multi-<i>k</i>-mer approaches to face significant computational challenges. Nevertheless, most methods are built on well-defined objects related to <i>k</i>-mers, such as de Bruijn graphs, Jaccard similarity, Bray-Curtis dissimilarity, and <i>k</i>-mer spectra. The role of <i>k</i>-mer sizes within these objects is more intuitive and can be described by numerous quantities and metrics. Therefore, exploring these objects across <i>k</i>-mer sizes opens opportunities for robust analyses and new applications. However, the evolution of <i>k</i>-mer objects with respect to <i>k</i>-mer sizes is surprisingly elusive. We introduce a novel substring index, the Pro<i>k</i>rustean graph, that elucidates the transformation of <i>k</i>-mer sets across <i>k</i>-mer sizes. Our framework built upon this index rapidly computes <i>k</i>-mer-based quantities for all <i>k</i>-mer sizes, with computational complexity independent of the size range and dependent only on maximal repeats. For example, counting unitigs (maximal simple paths) in de Bruijn graphs for <i>k</i> = 1, …, 100 is achieved in seconds using our index on a gigabase-scale dataset. We present a variety of algorithms for applications relevant to pangenomics and metagenomics. The Pro<i>k</i>rustean graph is directly derived from the affix tree and can be constructed space-efficiently from the Burrows-Wheeler transform. This derivation grounded in modern substring indexes that are all theoretically based on longest common prefixes reveals that such extension-based substring representations inherently struggle to explore <i>k</i>-mer objects across different sizes, which motivated our data structure. Our implementation is available at: https://github.com/KoslickiLab/prokrustean.