Significance:
This is the algorithmic core of modern short-read genome assemblers — SPAdes, Velvet, ABySS, and essentially every de novo assembler built for Illumina-style short reads uses a de Bruijn graph rather than the older overlap-graph approach (Problem 13), because it scales to millions of reads far more efficiently. Understanding that "genome assembly" reduces to "find an Eulerian path through a graph built from k-mers" is one of the most elegant results in computational biology, connecting 18th-century graph theory (Euler's Bridges of Königsberg) to 21st-century genomics.
Statement
Given a set of DNA k-mers (all of the same length `k`) representing overlapping fragments of an unknown circular-free linear genome, reconstruct the original genome string. Construct the de Bruijn graph where each k-mer becomes a directed edge from its length-`(k-1)` prefix node to its length-`(k-1)` suffix node, then find an **Eulerian path** through this graph (a path using every edge exactly once) using Hierholzer's algorithm. Concatenate the path's node labels (each subsequent node contributing only its last character) to reconstruct the genome.
You may assume the input k-mer set is guaranteed to be derived from a real underlying genome and admits at least one valid Eulerian path (i.e., the graph is guaranteed "nice" — no need to detect or reject Eulerian-path-free graphs).
Constraints
- `2 ≤ number of k-mers ≤ 500` - `2 ≤ k ≤ 50` - If multiple valid reconstructions exist (multiple valid Eulerian paths), any one is accepted, as long as it uses every given k-mer exactly once and is internally consistent (each consecutive `k`-length window of the output must appear in the input multiset)
My Notes
Log in to save personal notes.
Console output will appear here when you click Run Code or Submit...