De Bruijn Graphs: How DNA Is Reassembled From Billions of Fragments

The core idea: turn reads into k-mers, then into edges

The de Bruijn graph was defined by Nicolaas de Bruijn in 1946 to count cyclic sequences containing every length-k string exactly once. Genome assembly inverts that construction. Given a set of reads over the DNA alphabet Σ = {A, C, G, T}, pick a fixed odd integer k (typically 21–127) and:

• Slide a window of length k across every read to extract all k-mers. A read of length L yields exactly L − k + 1 of them.
• Each k-mer becomes a directed edge. Its tail node is its length-(k−1) prefix; its head node is its length-(k−1) suffix. So the k-mer ACGT (k=4) is an edge from node ACG to node CGT.
• Identical (k−1)-mers from different k-mers are merged into one node. This merge is the whole point: it collapses shared substrings so that overlaps become implicit in the graph topology instead of being computed pairwise.

The governing invariant: consecutive k-mers within any read differ by a one-base shift, so they share a (k−1)-mer and their edges meet at a common node. A correct spelling of the genome is therefore a walk that traverses every observed edge exactly once — an Eulerian path. Because a real chromosome may reuse a k-mer (repeats), an edge can carry multiplicity > 1, which is exactly why we want an Eulerian, not Hamiltonian, walk.

Why Eulerian, not Hamiltonian — the complexity payoff

The older overlap graph puts one node per read and asks for a Hamiltonian path — visit every node exactly once. Hamiltonian path is NP-complete; there is no known polynomial algorithm, and for millions of reads it is hopeless. The de Bruijn formulation is a genuine reframing: by making k-mers the edges, the reconstruction becomes 'visit every edge once,' i.e. an Eulerian path.

Euler's 1736 theorem (Königsberg bridges) gives a clean, checkable condition. A connected directed multigraph has an Eulerian path iff at most one vertex has (outdegree − indegree) = +1, at most one has (indegree − outdegree) = +1, and every other vertex is balanced (indegree = outdegree). Finding the path is Hierholzer's algorithm:

hierholzer(start):
  stack = [start]; path = []
  while stack not empty:
    v = stack.top()
    if out_edges(v) nonempty:
      e = pop one unused out-edge of v
      stack.push(head(e))
    else:
      path.append(stack.pop())
  return reverse(path)

Each edge is consumed once, each vertex pushed/popped O(deg) times, so Hierholzer runs in O(V + E) time and O(V + E) space. That is the headline result: swapping the node/edge roles turns an intractable Hamiltonian problem into a linear-time Eulerian one.

Building the graph: hashing, compaction, and cost

Construction is dominated by k-mer extraction. With N reads of average length L, you emit Θ(N·(L − k + 1)) = O(N·L) k-mers total — linear in the number of sequenced bases. Each k-mer is inserted into a hash table keyed by its 2-bits-per-base packed integer (a k-mer fits in one 64-bit word for k ≤ 32), so expected insertion is O(1) and the whole build is expected O(N·L).

• Space is O(number of distinct k-mers), bounded above by min(4ᵏ, total k-mers). For a human genome at k=31 the distinct-k-mer count is a few billion, and the hash table, not the reads, is the memory bottleneck — real assemblers spend heroic effort here (minimizer bucketing, Bloom-filter prefilters, succinct BOSS/FM-index encodings).
• Compaction: most of the graph is boring — long chains of nodes with indegree = outdegree = 1. These non-branching paths are merged into single edges labeled by a unitig (an unambiguous contiguous stretch). This turns the huge raw graph into a small compacted de Bruijn graph whose vertices are only the branch points, cutting V and E by orders of magnitude.
• Canonical k-mers: DNA is double-stranded, so a k-mer and its reverse complement are the same physical sequence. Assemblers store the lexicographically smaller of the two (the canonical form) to halve memory and unify both strands into one graph.

Choosing k: the bias–variance knob of assembly

k is the single most consequential parameter, and it trades two failure modes against each other:

• Small k maximizes overlap and connectivity (good for low coverage or high error rates) but any repeat longer than k−1 collapses into the same node, creating tangles the walk cannot resolve. In the limit, the graph becomes a hairball and contigs shatter.
• Large k spans more repeats and disambiguates the graph, but requires reads long enough and coverage high enough that most k-mers still appear. Since a single sequencing error corrupts up to k distinct k-mers, larger k amplifies error and thins coverage, breaking the graph into disconnected pieces.

The k-mer coverage after error is c·(L − k + 1)/L for read coverage c — it drops as k grows. Because no single k is optimal genome-wide, SPAdes (Bankevich et al., 2012) builds a multi-sized de Bruijn graph across several k values (e.g. 21, 33, 55) and merges them, using small k for connectivity and large k for repeat resolution. Picking k is genuinely the assembly analogue of a bias–variance tradeoff.

Cleaning the graph: errors, tips, bubbles, and coverage

Real reads are noisy, so the raw graph is never cleanly Eulerian. Assemblers spend most of their code on error correction on the graph itself, exploiting that true k-mers appear at roughly Poisson(λ = coverage) frequency while error k-mers appear once or twice:

• Tips: a short dead-end path caused by an error near a read's end. Detected as a node with a single low-coverage edge leading nowhere; clipped if shorter than ~2k.
• Bubbles: two parallel paths between the same pair of nodes, created by a single mismatch (SNP or sequencing error) that forks the graph and rejoins. Resolved by keeping the higher-coverage path (or reporting both, for heterozygous variants).
• Chimeric / low-coverage edges: pruned by a coverage threshold derived from the k-mer count histogram, whose first peak is error k-mers and second peak is the true coverage λ.

After cleaning, the balanced-vertex condition is (approximately) restored and the compacted graph is traversed. Where the Eulerian path is ambiguous — a vertex with multiple valid continuations, i.e. an unresolved repeat — the assembler stops and emits the unambiguous stretch as a contig rather than guessing. Paired-end and long-read information is then layered on to order and orient contigs into scaffolds.

Where it runs at scale — and its limits

De Bruijn assemblers are the default for high-throughput short-read data (Illumina), where per-read length is small but coverage is enormous — precisely the regime that kills OLC's near-quadratic overlap step. Production systems built on this idea include:

• Velvet (Zerbino & Birney, 2008) — the first widely used short-read DBG assembler.
• SPAdes — multi-k, the standard for bacterial and single-cell genomes.
• ABySS and MEGAHIT — distributed / succinct (BOSS) implementations for human-scale and metagenomic data, keeping the graph in tens of GB instead of terabytes.
• Beyond assembly, the compacted DBG underlies pangenome graphs and k-mer-based tools like Kraken (taxonomic classification) and Cortex (variant calling).

The fundamental limitation is that chopping reads into k-mers discards long-range linkage: two k-mers that came from the same read are, after the merge, indistinguishable from k-mers that merely happen to share a (k−1)-mer. Any repeat longer than k becomes unresolvable from the graph alone. This is why the field is shifting toward long reads (PacBio HiFi, Oxford Nanopore) reassembled with OLC-style methods — when reads span whole repeats, the Hamiltonian tangle largely disappears and the k-mer approximation is no longer worth its blind spots.

De Bruijn graph vs. overlap-layout-consensus (OLC) for short-read assembly

Property	De Bruijn (DBG)	Overlap-Layout-Consensus
Graph nodes	(k−1)-mers	Whole reads
Graph edges	k-mers (fixed length)	Pairwise read overlaps
Build cost	O(N·L) — linear in total bases	≈O(n²) or O(n·k) with an index
Traversal	Eulerian path, O(V + E)	Hamiltonian path, NP-hard
Best regime	Millions of short, high-coverage reads	Fewer long reads (PacBio, ONT)
Weakness	Loses long-range read linkage	Overlap computation dominates