Elucidating Transitions of k-mer-Based Objects Across k-mer Sizes

The widespread adoption of k-mers in computational biology has enabled efficient methods for utilizing genomic sequences in a variety of biological tasks. However, understanding the influence of k-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 k due to various noisy factors. The choice of k-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-k-mer approaches to face significant computational challenges. Nevertheless, most methods are built on well-defined objects related to k-mers, such as de Bruijn graphs, Jaccard similarity, Bray-Curtis dissimilarity, and k-mer spectra. The role of k-mer sizes within these objects is more intuitive and can be described by numerous quantities and metrics. Therefore, exploring these objects across k-mer sizes opens opportunities for robust analyses and new applications. However, the evolution of k-mer objects with respect to k-mer sizes is surprisingly elusive. We introduce a novel substring index, the Prokrustean graph, that elucidates the transformation of k-mer sets across k-mer sizes. Our framework built upon this index rapidly computes k-mer-based quantities for all k-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 k = 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 Prokrustean 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 k-mer objects across different sizes, which motivated our data structure. Our implementation is available at: https://github.com/KoslickiLab/prokrustean.