De Bruijn Graphs: Another Way of Construction

Let’s dig into another approach for de Bruijn graph construction with the help of edges.

We'll cover the following

The figure below (top) represents the 3-mer composition of TAATGCCATGGGATGTT as a composition graph CompositionGraph3_{3}(TAATGCCATGGGATGTT). As with the de Bruijn graph, each 3-mer is assigned to a directed edge, with its prefix labeling the first node of the edge and its suffix labeling the second node of the edge. However, the edges of this graph are isolated, meaning that no two edges share a node.

STOP and Think: Given Text = TAATGCCATGGGATGTT, glue identically labeled nodes in CompositionGraph3_{3}(Text). How does the resulting graph differ from DeBruijn3_{3}(Text) obtained by gluing the identically labeled nodes in PathGraph3_{3}(Text)?

Get hands-on with 1200+ tech skills courses.