Repeats and Limits

Repeats and Branches

A repeated overlap creates a branch in the exact graph.

highlighted = computed this step

Repeats create branches

In ATGTGC, the overlap TG appears in the middle of two k-mers. The graph marks it as a branch because it has more than 1 outgoing edge.

branch if outdegree>1\text{branch if outdegree}>1
A branch from a repeated overlapThe branch is recomputed from the repeated overlap.de Bruijn graphATGTGTGTGTGCATstartTGbranchGTGCend

A path can still be deterministic here

This small graph still has a deterministic Eulerian path with 5 path nodes. The repeated overlap is visited again before the final node.

path nodes=5\text{path nodes}=5
A branch from a repeated overlapThe branch is recomputed from the repeated overlap.de Bruijn graphATGTGTGTGTGCATstartTGbranchGTGCend