De Bruijn Graph

A de Bruijn graph is a directed graph within computation and algorithms that represents suffix-to-prefix overlaps between sequences of symbols drawn from a finite alphabet Σ. Independently discovered in combinatorics by French mathematician Camille Flye Sainte-Marie in 1894 and Dutch mathematician Nicolaas Govert de Bruijn in 1946 (together with I. J. Good), the k-dimensional de Bruijn graph over an m-symbol alphabet originally solved the problem of constructing a shortest circular de Bruijn sequence of length m^k containing every possible substring of length k (a k-mer) once.

In 1989 and 1995, Pavel Pevzner, Michael Waterman, and Ramana Idury adapted subgraph restrictions of the de Bruijn graph to DNA sequencing by hybridization, and in 2001 Pavel Pevzner, Haixiang Tang, and Michael Waterman demonstrated that formulating shotgun de novo sequence assembly over a de Bruijn graph reduces genome reconstruction from an NP-complete Hamiltonian path problem in computational complexity theory to a linear-time O(|E|) Eulerian path traversal. Today, de Bruijn graphs form the foundational data structure of short-read and hybrid genome assemblers (Velvet, ALLPATHS-LG, SPAdes, MEGAHIT), transcriptomic assemblers (Trinity), and multi-genome colored de Bruijn pangenome graphs (Cortex, Bifrost, Cuttlefish) in bioinformatics.

Full k-Dimensional De Bruijn Graphs B(m, k)

Given a finite alphabet Σ of size m = |Σ| (for DNA, Σ = {A, C, G, T} and m = 4) and an integer word length k ≥ 2, the full k-dimensional de Bruijn graph B(Σ, k) is a directed graph G = (V, E) constructed as follows:

• Vertex Set (V): The set Σ^k−1 of all m^k−1 possible strings of length k − 1 over Σ.
• Directed Edge Set (E): The set Σ^k of all m^k possible strings of length k over Σ. Each k-mer w = s₁s₂...s_k defines a directed edge from its (k − 1)-length prefix vertex prefix(w) = s₁s₂...s_k−1 to its (k − 1)-length suffix vertex suffix(w) = s₂s₃...s_k.

Every vertex u ∈ V in the full de Bruijn graph has in-degree deg⁻(u) = m (one incoming edge for each symbol prepended to u) and out-degree deg⁺(u) = m (one outgoing edge for each symbol appended to u). Because B(Σ, k) is strongly connected and balanced (deg⁻(u) = deg⁺(u) for all u ∈ V), Leonhard Euler's 1736 theorem proves that B(Σ, k) possesses an Eulerian cycle—a closed directed walk that traverses every k-mer edge in E once. Moreover, the line graph of B(Σ, k − 1) (formed by promoting each edge to a vertex and connecting edges that share a head-to-tail vertex) is isomorphic to B(Σ, k), meaning an Eulerian cycle in B(Σ, k) is simultaneously a Hamiltonian cycle in B(Σ, k + 1). By the BEST theorem (de Bruijn, van Aardenne-Ehrenfest, Smith, and Tutte, 1951), the number of distinct de Bruijn sequences of order k over an alphabet of size m is ((m!)^mk−1) / m^k.

Node-Centric Versus Edge-Centric Bioinformatic Representations

In genome assembly, only the small subset of k-mers actually observed in sequencing reads is instantiated—forming a sparse induced de Bruijn subgraph where |V| ≪ 4^k−1. Bioinformaticians implement two algebraically related conventions:

1. Edge-Centric De Bruijn Graph (Pevzner–Tang–Waterman): Vertices represent observed (k − 1)-mers, and directed edges represent observed k-mers connecting their (k − 1)-mer prefix to their (k − 1)-mer suffix. Each k-mer in the read dataset corresponds to an edge.
2. Node-Centric De Bruijn Graph: Vertices represent observed k-mers directly, and a directed edge connects vertex u to vertex v whenever the (k − 1)-suffix of u matches the (k − 1)-prefix of v (corresponding to a (k + 1)-mer spanning the transition). Maximal non-branching linear chains of vertices (where deg⁺(u) = deg⁻(v) = 1) are compacted into contiguous single strings called unitigs.

Why Overlap-Layout-Consensus (OLC) Is NP-Hard

During the Sanger sequencing era (and in modern long-read assembly), shotgun genome assemblers used the Overlap-Layout-Consensus (OLC) paradigm. In an OLC string graph, each sequencing read R_i of length 500–20,000 bp is represented as a distinct vertex, and a directed edge connects R_i to R_j if a suffix of R_i aligns to a prefix of R_j. Constructing this overlap graph requires pairwise alignments across N reads, and finding a layout that visits every read vertex once corresponds to the Hamiltonian path problem (or minimum-weight Shortest Common Superstring problem), which is NP-complete.

When second-generation sequencing technologies (Illumina sequencing by synthesis) increased read counts N from 10⁵ Sanger reads to 10⁸–10⁹ short reads (100–300 bp), both the O(N²) all-against-all overlap computation and the Hamiltonian path layout became intractable.

The Pevzner–Tang–Waterman Eulerian Reduction (2001)

In 1995, Ramana Idury and Michael Waterman proposed shredding each read of length L into its L − k + 1 overlapping k-mers, and in 2001 Pavel Pevzner, Haixiang Tang, and Michael Waterman introduced the Eulerian path approach to DNA fragment assembly (implemented in the EULER assembler). Instead of treating each read as a vertex:

1. Every read is decomposed into overlapping k-mers via a single linear O(N · L) pass using a hash table or Bloom filter—eliminating pairwise O(N²) sequence alignments altogether. Identical k-mers originating from 50× or 100× coverage of the same genomic locus collapse into a single edge annotated with its integer multiplicity (coverage depth).
2. Reconstructing the genome corresponds to finding an Eulerian path that traverses every k-mer edge in the de Bruijn graph according to its copy-number multiplicity. Because a directed connected multigraph admits an Eulerian path if and only if at most one vertex has deg⁺(u) − deg⁻(u) = 1 (the start node), at most one vertex has deg⁻(v) − deg⁺(v) = 1 (the end node), and all other vertices satisfy deg⁻(w) = deg⁺(w), Carl Hierholzer's 1873 algorithm finds an Eulerian path in linear O(|E|) time.

Choosing k-mer Length and Managing Reverse Complements

Because DNA is double-stranded and shotgun reads are sampled arbitrarily from either the forward (5′→3′) or reverse-complement strand, genomic de Bruijn graphs treat each k-mer and its reverse complement as a bidirected edge (or map every k-mer to its lexicographically smaller canonical k-mer). Moreover, k is chosen as an odd integer (for example, k = 31, 55, or 77) so that no k-mer can equal its own reverse complement (a palindromic k-mer of even length would induce a self-inverting hairpin loop in the bidirected graph).

Selecting the word size k involves a fundamental trade-off between coverage connectivity and repeat resolution:

• Small k (k = 21–31): Maximizes the number of overlapping k-mers per read (L − k + 1) and maintains connectivity across low-coverage genomic regions, according to the Lander–Waterman Poisson coverage model. However, any genomic repeat longer than k − 1 bp collapses into a shared vertex with multiple incoming and outgoing edges, tangling the Eulerian traversal.
• Large k (k = 77–127): Bridges across short interspersed repeats shorter than k, untangling repeat branches into unique paths. However, larger k values require higher sequencing depth and are more sensitive to sequencing errors, since a single base-call error corrupts up to k consecutive k-mers.

To obtain the benefits of both regimes simultaneously, IDBA-UD (Peng et al., 2012) and SPAdes (Bankevich et al., 2012) construct iterative multi-k de Bruijn graphs: they assemble unitigs at a small initial value (k₁ = 21) to close low-coverage gaps, feed those assembled contigs together with the raw reads into progressively larger graphs (k₂ = 33, k₃ = 55, k₄ = 77, k₅ = 99), and use paired-end insert-size distances to resolve remaining repeat bifurcations.

Sequencing Errors, Topological Graph Simplification, and Colored Pangenomes

Real sequencing reads contain base-call substitutions and indels quantified by the logarithmic Phred quality score (Q = −10 log₁₀ P_err). Even a 0.1% (Q30) error rate across 10⁹ reads generates hundreds of millions of erroneous singleton k-mers that distort the ideal de Bruijn graph into characteristic topological artifacts, which assemblers such as Velvet (Daniel Zerbino and Ewan Birney, 2008) and SPAdes remove via four graph-simplification passes:

1. Pre-Assembly k-mer Spectrum Error Correction (Hammer / BayesHammer): Before or during graph construction, rare k-mers with coverage multiplicity 1–2 that differ by 1 Hamming substitution from a high-coverage (e.g., 50×) solid k-mer are corrected to the consensus sequence.
2. Tip Clipping (Dead-End Spurs): A sequencing error near the 3′ or 5′ end of a read creates a short dead-end branch (a tip) of length < 2k and low coverage diverging from a high-coverage main path. Tip-clipping algorithms prune disconnected dead-end chains shorter than 2k.
3. Bubble Popping (Bulges): A single-base substitution error in the middle of a read—or a true heterozygous SNP allele in a diploid organism—creates two parallel paths of length ≈ k that diverge from a common source vertex u and reconverge at a sink vertex v (a bubble). Velvet's Tour Bus (Dijkstra-like breadth-first search) identifies parallel paths with high sequence similarity and merges the lower-coverage path into the higher-coverage consensus path.
4. Chimeric Connection & Coverage Cutoff Filtering: Low-coverage chimeric edges connecting unrelated contigs are removed by statistical coverage thresholds.

Succinct (BOSS) and Colored De Bruijn Graphs for Pangenomics

In 2012, Zamin Iqbal et al. introduced the colored de Bruijn graph (implemented in Cortex), which overlays the de Bruijn graphs of C distinct individuals, strains, or species into a single unified vertex/edge set while tagging each k-mer with a bit-vector of colors indicating which samples contain that k-mer. In a colored de Bruijn graph, SNPs, indels, and structural rearrangements appear directly as multi-colored bubbles without needing a single linear reference genome—enabling reference-free variant calling and bacterial pan-genome wide association studies (GWAS).

To store de Bruijn graphs of terabase-scale metagenomes and pangenomes in minimal RAM, Alexander Bowe, Taku Onodera, Kunihiko Sadakane, and Tetsuo Shibuya (2012) developed the BOSS representation, which applies the Burrows–Wheeler transform to the sorted (k − 1)-mer node labels to encode an entire de Bruijn graph in ~4 bits per k-mer edge, while Bloom filter tries and Bifrost (Holley and Melsted, 2020) support dynamic compacted colored de Bruijn indexing across hundreds of thousands of genomes.

Why can a de Bruijn graph not resolve genomic repeats that are longer than the read length?

When a genomic repeat element (such as a 6-kilobase LINE-1 retrotransposon or bacterial ribosomal RNA operon) is longer than both the k-mer size k and the paired-end fragment insert size, all k-mers internal to the repeat copies are identical and collapse into a single shared central unitig with m incoming edges and m outgoing edges. Without long reads or mate-pair links spanning from a unique flanking sequence on the left to a unique flanking sequence on the right, multiple distinct Eulerian pairings of incoming and outgoing branches are mathematically valid, so the assembler must terminate the contig at the repeat boundary to avoid misassembly.

How does a compacted de Bruijn graph reduce memory and traversal cost?

In an uncompacted de Bruijn graph, a unique 10,000-bp exon is represented as a chain of ~10,000 consecutive vertices of in-degree 1 and out-degree 1. A compacted de Bruijn graph collapses every maximal non-branching linear path into a single unitig vertex storing one contiguous string, reducing vertex and edge counts by 1–2 orders of magnitude while preserving the exact same branching topology and Eulerian paths.

1. de Bruijn, N. G. (1946). A combinatorial problem. Proceedings of the Section of Sciences of the Koninklijke Nederlandse Akademie van Wetenschappen te Amsterdam, 49(7), 758–764. https://doi.org/10.1016/S1385-7258(56)50010-850010-8)
2. Pevzner, P. A., Tang, H., & Waterman, M. S. (2001). An Eulerian path approach to DNA fragment assembly. Proceedings of the National Academy of Sciences, 98(17), 9748–9753. https://doi.org/10.1073/pnas.171285098
3. Zerbino, D. R., & Birney, E. (2008). Velvet: Algorithms for de novo short read assembly using de Bruijn graphs. Genome Research, 18(5), 821–829. https://doi.org/10.1101/gr.074492.107
4. Bankevich, A., Nurk, S., Antipov, D., Gurevich, A. A., Dvorkin, M., Kulikov, A. S., ... & Pevzner, P. A. (2012). SPAdes: A new genome assembly algorithm and its applications to single-cell sequencing. Journal of Computational Biology, 19(5), 455–477. https://doi.org/10.1089/cmb.2012.0021
5. Iqbal, Z., Caccamo, M., Turner, I., Flicek, P., & McVean, G. (2012). De novo assembly and genotyping of variants using colored de Bruijn graphs. Nature Genetics, 44(2), 226–232. https://doi.org/10.1038/ng.1028