De Bruijn Graph Assembly

Every time a biologist sequences a genome, a machine reads millions of short DNA snippets — reads — each only 100–300 nucleotides long. The full genome can be billions of nucleotides. No sequencer reads it in one pass.

The challenge is a puzzle without a picture on the box: given millions of overlapping fragments, reconstruct the original sequence. For two decades the standard approach was to compare every pair of reads for overlap — a quadratic bottleneck that choked on large genomes.

In 2001 Pavel Pevzner, Haixu Tang, and Michael Waterman showed the way out: break each read into all its overlapping substrings of length $k$ (called k-mers), build a graph where each k-mer is an edge, and the assembly problem becomes finding an Eulerian path — a walk that uses every edge exactly once. Finding that path takes linear time, not quadratic. The same idea had been anticipated by Nicole El-Mabrouk and others, and the underlying combinatorial structure goes back to work on de Bruijn sequences by Nicolaas de Bruijn in 1946.

Today every major short-read assembler — Velvet, SPAdes, SOAPdenovo — is built on this insight.

Enter a few short DNA reads below (or use the examples), choose a k-mer length $k$, and watch the assembler build a de Bruijn graph. Each $(k-1)$-mer becomes a node; each k-mer becomes a directed edge from its prefix to its suffix. When every node has equal in- and out-degree, an Eulerian circuit exists; otherwise the path starts at an unbalanced node.

<!-- {{c_html_intro}} -->
<div class="controls">
  <label class="ctrl-label">{{lbl_reads}}</label>
  <textarea id="reads-input" rows="4" placeholder="{{placeholder_reads}}">ATGCGT
GCGTAC
CGTACG</textarea>
  <div class="row">
    <label class="ctrl-label" for="k-input">{{lbl_k}} <span id="k-val">3</span></label>
    <input type="range" id="k-input" min="2" max="6" value="3" />
  </div>
  <div class="btns">
    <button id="btn-assemble" type="button">{{btn_assemble}}</button>
    <button id="btn-example1" type="button" class="ghost">{{btn_ex1}}</button>
    <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
  </div>
</div>
<div id="status" class="status"></div>
<div id="graph-section" style="display:none">
  <div class="section-title">{{lbl_graph_title}}</div>
  <canvas id="graph-canvas" width="480" height="220"></canvas>
  <div class="section-title mt">{{lbl_contigs_title}}</div>
  <div id="contigs-out" class="contigs-out"></div>
</div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.controls { display: flex; flex-direction: column; gap: .5rem; }
.ctrl-label { font-weight: 600; font-size: .85rem; color: #555; }
textarea { width: 100%; border: 1px solid #cdd9e3; border-radius: 6px; padding: .4rem .5rem;
           font-family: ui-monospace, monospace; font-size: .9rem; resize: vertical; }
.row { display: flex; align-items: center; gap: .6rem; }
input[type=range] { flex: 1; }
.btns { display: flex; gap: .4rem; flex-wrap: wrap; }
button { font: 600 13px system-ui, sans-serif; padding: .4rem .8rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 6px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.status { font-size: .9rem; font-weight: 600; min-height: 1.4em; margin: .3rem 0; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.status.info { color: #1d3557; }
.section-title { font-weight: 700; font-size: .85rem; color: #1d3557; margin: .4rem 0 .15rem; }
.section-title.mt { margin-top: .7rem; }
#graph-canvas { border: 1px solid #cdd9e3; border-radius: 6px; width: 100%; max-width: 480px; background: #f7f9fb; }
.contigs-out { display: flex; flex-wrap: wrap; gap: .35rem; }
.contig-chip { font-family: ui-monospace, monospace; font-size: .85rem; background: #e8eef3;
               border: 1px solid #b0c0d0; border-radius: 4px; padding: .15rem .4rem; color: #1d3557; }

// Code not found

Notice what happens as you change $k$: small values merge distinct regions and create ambiguous edges; large values may break the graph into disconnected pieces. Real assemblers tune $k$ — or use multiple values — to balance connectivity against uniqueness.

The elegant part — finding an Eulerian path through the k-mer graph — is solved in linear time by Hierholzer's algorithm (1873). That is genuinely easy.

The hard parts are what the model leaves out:

• Repeat resolution. If the same k-mer appears in two distinct locations, its edges merge in the graph, creating a bubble or tangle. Resolving which copy belongs where is equivalent to a sequence of local disambiguation steps that, in the worst case, are NP-hard.
• Sequencing errors. A single wrong nucleotide spawns a spurious k-mer and adds a dead-end branch (a "tip") to the graph. Trimming tips without removing real sequence is heuristic.
• Coverage gaps. Low-coverage regions may have zero reads spanning them, breaking the graph into contigs (contiguous assembled stretches) that must be linked by additional data into scaffolds.
• Ploidy and heterozygosity. Diploid organisms have two copies of each chromosome with small differences — the graph forks at every heterozygous site.

The transition from contigs to a complete chromosome assembly remains an open research problem. Long-read sequencing (PacBio, Oxford Nanopore) sidesteps some issues by spanning repeats directly, but introduces its own high error rate. Assembly is solved enough to be routinely useful, yet hard enough to keep entire research groups busy.

The de Bruijn graph is the workhorse of modern genomics — and its reach extends further:

• Reference genome assembly. Every published genome — human, plant, pathogen — was assembled with tools (Velvet, SPAdes, Canu) that build some variant of the k-mer graph.
• Metagenomics. Sequencing an environmental sample mixes the DNA of thousands of species. Assemblers like MEGAHIT use de Bruijn graphs to untangle them without needing a reference.
• Transcriptome assembly. RNA-seq reads can be assembled into transcripts with Trinity, which builds a de Bruijn graph of cDNA k-mers and reconstructs alternatively spliced isoforms.
• Variant calling. Tools like Cortex and GATK-HaplotypeCaller locally reassemble reads around a candidate variant site to detect insertions and deletions that alignment alone misses.
• Compression and combinatorics. De Bruijn sequences (sequences that contain every possible k-mer exactly once) appear in card tricks, robot motion planning, and cryptographic key generation — the mathematical root that gave the graph its name.

The k-mer graph also connects to deeper theory: the Eulerian vs. Hamiltonian path dichotomy explains exactly why assembly is tractable while related problems (like the travelling salesman) are not.

De Bruijn graph assembly is a beautiful example of a reduction: a hard-looking biological puzzle (reconstruct a genome from millions of fragments) becomes a classical graph problem (find an Eulerian path) that has been solved in linear time for 150 years.

The trick is the right representation. Break reads into k-mers, encode them as edges, and the overlap structure that made pairwise comparison quadratic disappears into graph traversal. What remains — repeat resolution, error correction, scaffolding — is genuinely hard, which is why genome assembly is still an active research frontier.

The next time you read about a newly sequenced organism, behind the announcement is a k-mer graph, an Eulerian walk, and a team of algorithms wrestling with the parts that theory hasn't yet made easy. The graph did most of the heavy lifting — and it all traces back to a 1946 paper about binary sequences.