Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2506.22172 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913918903910400 |
|---|---|
| author | He, Haoze Kari, Lila Arias, Pablo Millan |
| author_facet | He, Haoze Kari, Lila Arias, Pablo Millan |
| contents | This paper establishes formal mathematical foundations linking Chaos Game Representations (CGR) of DNA sequences to their underlying $k$-mer frequencies. We prove that the Frequency CGR (FCGR) of order $k$ is mathematically equivalent to a discretization of CGR at resolution $2^k \times 2^k$, and its vectorization corresponds to the $k$-mer frequencies of the sequence. Additionally, we characterize how symmetry transformations of CGR images correspond to specific nucleotide permutations in the originating sequences. Leveraging these insights, we introduce an algorithm that generates synthetic DNA sequences from prescribed $k$-mer distributions by constructing Eulerian paths on De Bruijn multigraphs. This enables reconstruction of sequences matching target $k$-mer profiles with arbitrarily high precision, facilitating the creation of synthetic CGR images for applications such as data augmentation for machine learning-based taxonomic classification of DNA sequences. Numerical experiments validate the effectiveness of our method across both real genomic data and artificially sampled distributions. To our knowledge, this is the first comprehensive framework that unifies CGR geometry, $k$-mer statistics, and sequence reconstruction, offering new tools for genomic analysis and visualization. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_22172 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Bridging Chaos Game Representations and $k$-mer Frequencies of DNA Sequences He, Haoze Kari, Lila Arias, Pablo Millan Formal Languages and Automata Theory D.3.1 This paper establishes formal mathematical foundations linking Chaos Game Representations (CGR) of DNA sequences to their underlying $k$-mer frequencies. We prove that the Frequency CGR (FCGR) of order $k$ is mathematically equivalent to a discretization of CGR at resolution $2^k \times 2^k$, and its vectorization corresponds to the $k$-mer frequencies of the sequence. Additionally, we characterize how symmetry transformations of CGR images correspond to specific nucleotide permutations in the originating sequences. Leveraging these insights, we introduce an algorithm that generates synthetic DNA sequences from prescribed $k$-mer distributions by constructing Eulerian paths on De Bruijn multigraphs. This enables reconstruction of sequences matching target $k$-mer profiles with arbitrarily high precision, facilitating the creation of synthetic CGR images for applications such as data augmentation for machine learning-based taxonomic classification of DNA sequences. Numerical experiments validate the effectiveness of our method across both real genomic data and artificially sampled distributions. To our knowledge, this is the first comprehensive framework that unifies CGR geometry, $k$-mer statistics, and sequence reconstruction, offering new tools for genomic analysis and visualization. |
| title | Bridging Chaos Game Representations and $k$-mer Frequencies of DNA Sequences |
| topic | Formal Languages and Automata Theory D.3.1 |
| url | https://arxiv.org/abs/2506.22172 |