Genome Assembly & Graph Traversals
De Bruijn Graph & Eulerian Path Assembly
Interactive exploration of De Bruijn graph construction, Hierholzer's Eulerian path reconstruction, tip clipping, bubble popping, and unitig compaction.
In a De Bruijn graph, an Eulerian Path (visiting every directed k-mer edge exactly once) exists if:
- At most one start node has
out-deg - in-deg = 1 - At most one end node has
in-deg - out-deg = 1 - All other internal nodes are balanced:
in-deg = out-deg
Hierholzer's Algorithm traverses the graph in linear O(E) time, solving assembly polynomial-time.
Eulerian vs Hamiltonian Assembly
Overlap-Layout-Consensus (OLC) finds a Hamiltonian path (visiting each read node once), which is NP-hard. By transforming reads into (k-1)-mer nodes and k-mer edges, De Bruijn graphs reduce assembly to finding an Eulerian walk in O(E) linear time.
Graph Cleaning Heuristics
Sequencing errors create spurs (tips) and SNP divergence creates parallel paths (bubbles). Modern assemblers (SPAdes, MEGAHIT) apply tip-clipping, bubble-popping, and coverage thresholding to restore Eulerian topology.
Unitigs & Assembly N50
When biological repeats prevent unambiguous Eulerian traversal, assemblers output Unitigs (maximal non-branching contigs). The N50 metric represents the minimum contig length covering 50% of the assembled genome.