From k-mers to Graphs

The de Bruijn Graph

A de Bruijn graph turns k-mer overlaps into directed edges.

highlighted = computed this step

Nodes are overlaps

The 4 graph nodes are the distinct prefix or suffix strings. The diagram is recomputed from the read and k; no node list is trusted from the lesson.

∣V∣=4|V|=4
A de Bruijn graphEach edge is a k-mer from the source read.de Bruijn graphATGTGCGCGATstartTGGCCGend

Edges are the observed k-mers

Each k-mer becomes one directed edge from its prefix to its suffix. Here there are 3 edges, one for each observed k-mer.

∣E∣=3|E|=3
A de Bruijn graphEach edge is a k-mer from the source read.de Bruijn graphATGTGCGCGATstartTGGCCGend