De Bruijn graphs: Comparison with Overlap Graphs
Understand the differences between de Bruijn graphs and overlap graphs in genome assembly. Learn how each graph approaches the String Reconstruction Problem by using Eulerian or Hamiltonian paths, helping you decide which method to apply based on algorithm efficiency and problem complexity.
We'll cover the following...
We'll cover the following...
De Bruijn vs. overlap graphs
We now have two ways of solving the String Reconstruction Problem. We can either find a Hamiltonian path in the overlap graph or find an Eulerian path in the de Bruijn graph (figure below). Your inner voice may have already started complaining: was it really worth my time ...