EUVIMEDOpdag EUVIMED
Open access · CC BY 4.0

Reconstruction of DNA Sequences Through Eulerian Traversal of De Bruijn Graphs

Baining Zhu, Siqi Liu, Suwei Liu

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).

AbstractBibliografiske oplysningerCiteRelated studies

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}
}
Start for free →