String Reconstruction with Overlap Graph: Hamiltonian Paths
Understand how to reconstruct DNA strings by finding Hamiltonian paths in overlap graphs. Learn about k-universal strings, de Bruijn graphs, and their role in genome assembly to grasp fundamental bioinformatics algorithms.
We'll cover the following...
We'll cover the following...
We now know that to solve the String Reconstruction Problem, we’re looking for a path in the overlap graph that visits every node exactly once.
A path in a graph visiting every node once is called a Hamiltonian path, in honor of the Irish mathematician William Hamilton (see DETOUR: The Icosian Game).
As this
...