Walking in the de Bruijn Graph

Eulerian paths

Even though we’ve glued together nodes to form the de Bruijn graph, we haven’t changed its edges, and so the path from TA to TT reconstructing the genome is still hiding in DeBruijn$_{3}$(TAATGCCATGGGATGTT) (figure below), although this path has become “tangled” after gluing. Therefore, solving the String Reconstruction Problem reduces to finding a path in the de Bruijn graph that visits every edge exactly once. Such a path is called an Eulerian Path in honor of the great mathematician Leonhard Euler (pronounced “oiler”).