Graphs
2 problems from Rosalind — Bioinformatics Stronghold. Press Run on any block to execute it in your browser.
GRPH — Overlap Graphs
solved Problem statement
Overlap graphs make reads the nodes, which makes assembly a Hamiltonian path — NP-hard. DBRU makes reads the edges instead and gets an Eulerian path, solvable in linear time. Same data, different graph, and the whole reason modern assemblers use de Bruijn graphs.
DBRU — Constructing a De Bruijn Graph
solved Problem statement
Reads become edges rather than nodes, which turns assembly from a Hamiltonian path problem into an Eulerian one. GRPH shows the alternative; this is the construction real assemblers are built on.