Reconstruction of DNA Sequences Through Eulerian Traversal of De Bruijn Graphs
Mathematics · 2026-02-28 · 14 (5) · 832
DOI: 10.3390/math14050832 ↗At a glance
Journal article in Mathematics, published online on 2026-02-28. Written by Baining Zhu and 2 co-authors. 23 references. The full text is freely available (open access, CC BY 4.0).
Abstract (original language)
Reconstructing a genome from collections of short DNA fragments is a fundamental problem in modern sequencing. Although genome assembly algorithms are widely used in practice, the mathematical conditions that allow exact reconstruction are not always clear. This study develops a graph-theoretic framework for genome reconstruction using De Bruijn graphs and Eulerian paths in an idealized, error-free setting. Each k-mer is represented as a directed edge connecting its (k−1)-length prefix and suffix. The resulting overlap graph is constructed using a balanced search tree and traversed with a stack-based Eulerian algorithm. Numerical experiments over a broad range of genome lengths and fragment lengths reveal a sharp transition in reconstruction accuracy. This transition is explained by a probabilistic model for prefix collisions in the directed graph. The theoretical predictions agree with simulation results and provide conditions on the fragment length required for reliable reconstruction. These results show that the difficulty of genome assembly is governed primarily by the combinatorial structure of the underlying graph rather than by algorithmic heuristics.
Cite
APA
Zhu, B., Liu, S., & Liu, S. (2026). Reconstruction of DNA Sequences Through Eulerian Traversal of De Bruijn Graphs. Mathematics, 14(5), 832. https://doi.org/10.3390/math14050832
Vancouver
Zhu B, Liu S, Liu S. Reconstruction of DNA Sequences Through Eulerian Traversal of De Bruijn Graphs. Mathematics. 2026;14(5):832. doi:10.3390/math14050832
BibTeX
@article{Zhu2026,
author = {Zhu, Baining and Liu, Siqi and Liu, Suwei},
title = {Reconstruction of DNA Sequences Through Eulerian Traversal of De Bruijn Graphs},
journal = {Mathematics},
year = {2026},
volume = {14},
number = {5},
pages = {832},
doi = {10.3390/math14050832}
}
EUVIMED