What do Eulerian and Hamiltonian cycles have to do with genome assembly?

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Genome assembly is a fundamental problem in bioinformatics.
• Students often learn about genome assembly through the lens of Eulerian and Hamiltonian cycles.
• De Bruijn graphs are commonly used in practical genome assembly algorithms.

Purpose of the Study:

• To clarify the role of de Bruijn graphs in genome assembly.
• To debunk the misconception that de Bruijn graphs are used due to the complexity of Hamiltonian and Eulerian cycles.
• To explain the actual reasons for the utility of de Bruijn graphs in practice.

Main Methods:

• Theoretical analysis of graph cycle problems in the context of genome assembly.
• Examination of the uniqueness of genome reconstruction.
• Evaluation of the computational complexity of assembly algorithms.

Main Results:

• The complexity of finding Eulerian and Hamiltonian cycles is not the reason for de Bruijn graph utility in genome assembly.
• Genome reconstruction is inherently non-unique, making direct cycle-finding algorithms impractical.
• Linear-time algorithms exist for genome reconstruction within both Eulerian and Hamiltonian paradigms, even for arbitrary reconstructions.

Conclusions:

• The practical utility of de Bruijn graphs in genome assembly stems from factors other than cycle problem complexity.
• Understanding the non-uniqueness of genome reconstruction is crucial for practical assembly.
• Efficient linear-time algorithms are available for genome reconstruction, irrespective of the chosen graph paradigm.