De Bruijn Graphs: Another Way of Construction
Explore the process of constructing De Bruijn graphs from genome k-mer compositions to understand genome assembly. This lesson guides you through graph transformations from isolated edges to connected graphs, highlighting their importance in representing DNA sequences and applications in bioinformatics.
We'll cover the following...
The figure below (top) represents the 3-mer composition of TAATGCCATGGGATGTT as a composition graph CompositionGraph(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 CompositionGraph(Text). How does the resulting graph differ from DeBruijn ...