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

Area of Science:

• Computational Biology
• Bioinformatics
• Genomics

Background:

• K-mers are fundamental in computational biology for genomic sequence analysis.
• The influence of k-mer size is often poorly understood and arbitrarily chosen.
• Existing methods struggle with multi-k-mer approaches due to computational challenges.

Purpose of the Study:

• To elucidate the transformation of k-mer sets across different k-mer sizes.
• To develop a computational framework for rapid, size-independent k-mer analysis.
• To enable robust genomic analyses in pangenomics and metagenomics.

Main Methods:

• Introduction of the Prokrustean graph, a novel substring index.
• Development of a framework for computing k-mer-based quantities across all k-mer sizes.
• Leveraging the affix tree and Burrows-Wheeler transform for efficient index construction.

Main Results:

• The Prokrustean graph enables rapid computation of k-mer quantities, independent of size range.
• Unitig counting in de Bruijn graphs for k=1-100 achieved in seconds on large datasets.
• Demonstration of algorithms applicable to pangenomics and metagenomics.

Conclusions:

• The Prokrustean graph provides a theoretical and practical solution for analyzing k-mer objects across sizes.
• This approach overcomes limitations of existing substring representations for exploring k-mer evolution.
• The framework facilitates more robust and efficient genomic sequence analysis.