Introduction

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 kk (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.

Build the Graph

Enter a few short DNA reads below (or use the examples), choose a k-mer length kk, and watch the assembler build a de Bruijn graph. Each (k−1)(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.

<!-- De Bruijn assembly demo — reads go in, k-mer graph + contigs come out -->
<div class="controls">
  <label class="ctrl-label">DNA Reads (one per line):</label>
  <textarea id="reads-input" rows="4" placeholder="Enter reads, e.g. ATGCGT">ATGCGT
GCGTAC
CGTACG</textarea>
  <div class="row">
    <label class="ctrl-label" for="k-input">k-mer length 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">Assemble</button>
    <button id="btn-example1" type="button" class="ghost">Load example</button>
    <button id="btn-reset" type="button" class="ghost">Clear</button>
  </div>
</div>
<div id="status" class="status"></div>
<div id="graph-section" style="display:none">
  <div class="section-title">De Bruijn Graph (nodes = (k-1)-mers, edges = k-mers)</div>
  <canvas id="graph-canvas" width="480" height="220"></canvas>
  <div class="section-title mt">Assembled Contigs</div>
  <div id="contigs-out" class="contigs-out"></div>
</div>

/* Styles for the de Bruijn assembly demo */
* { 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; }

/* De Bruijn graph assembly demo — vanilla JS, no imports */
const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));

/* Example read sets */
const EXAMPLE1 = 'ATGCGT\nGCGTAC\nCGTACG';

/* Build de Bruijn graph: for each read extract all k-mers as edges (prefix->suffix) */
function buildDeBruijn(reads, k) {
  /* collect unique k-mer edges and node names — dedup so overlapping reads share edges */
  const seenKmers = new Set();
  const edges = [];
  const nodeSet = new Set();
  for (const read of reads) {
    const r = read.trim().toUpperCase().replace(/[^ACGT]/g, '');
    if (r.length < k) continue;
    for (let i = 0; i <= r.length - k; i++) {
      const kmer = r.slice(i, i + k);
      if (seenKmers.has(kmer)) continue;
      seenKmers.add(kmer);
      const pre = kmer.slice(0, k - 1);
      const suf = kmer.slice(1);
      edges.push({ from: pre, to: suf, kmer });
      nodeSet.add(pre);
      nodeSet.add(suf);
    }
  }
  return { edges, nodes: [...nodeSet] };
}

/* Find Eulerian paths using Hierholzer's algorithm */
function eulerianPaths(nodes, edges) {
  /* build adjacency list and degree counts */
  const adj = {};
  const inDeg = {};
  const outDeg = {};
  for (const n of nodes) { adj[n] = []; inDeg[n] = 0; outDeg[n] = 0; }
  for (const e of edges) {
    adj[e.from] = adj[e.from] || [];
    adj[e.from].push({ to: e.to, kmer: e.kmer, used: false });
    outDeg[e.from] = (outDeg[e.from] || 0) + 1;
    inDeg[e.to] = (inDeg[e.to] || 0) + 1;
  }
  /* nodes with surplus out-degree are Eulerian path starts */
  const starts = nodes.filter(n => (outDeg[n] || 0) > (inDeg[n] || 0));
  const sources = starts.length ? starts : nodes.filter(n => (outDeg[n] || 0) > 0).slice(0, 1);
  /* Hierholzer's algorithm for each unbalanced source */
  const paths = [];
  for (const src of sources) {
    const stack = [src];
    const path = [];
    const localAdj = {};
    for (const n of nodes) {
      localAdj[n] = (adj[n] || []).map(e => ({ ...e }));
    }
    while (stack.length) {
      const v = stack[stack.length - 1];
      const nbrs = localAdj[v] || [];
      const next = nbrs.find(e => !e.used);
      if (next) { next.used = true; stack.push(next.to); }
      else { path.push(stack.pop()); }
    }
    if (path.length > 1) paths.push(path.reverse());
  }
  return paths;
}

/* Convert a node path to a contig string (overlap by k-1) */
function pathToContig(path, k) {
  if (!path.length) return '';
  let s = path[0];
  for (let i = 1; i < path.length; i++) s += path[i][path[i].length - 1];
  return s;
}

/* Arrange nodes in a circle for drawing */
function layoutNodes(nodes) {
  const pos = {};
  const n = nodes.length;
  const cx = 240, cy = 110, rx = 180, ry = 85;
  nodes.forEach((node, i) => {
    const angle = (2 * Math.PI * i) / n - Math.PI / 2;
    pos[node] = { x: cx + rx * Math.cos(angle), y: cy + ry * Math.sin(angle) };
  });
  return pos;
}

/* Draw the graph on a canvas element */
function drawGraph(canvas, nodes, edges, k) {
  const ctx = canvas.getContext('2d');
  const W = canvas.width, H = canvas.height;
  ctx.clearRect(0, 0, W, H);
  if (!nodes.length) return;
  const pos = layoutNodes(nodes);
  const R = 22;
  /* draw directed edges with colored arrows */
  const edgeColors = ['#2a9d8f', '#e76f51', '#457b9d', '#e9c46a', '#6a4c93'];
  edges.forEach((e, i) => {
    const p1 = pos[e.from], p2 = pos[e.to];
    if (!p1 || !p2) return;
    const dx = p2.x - p1.x, dy = p2.y - p1.y;
    const dist = Math.sqrt(dx * dx + dy * dy) || 1;
    const sx = p1.x + (dx / dist) * R;
    const sy = p1.y + (dy / dist) * R;
    const ex = p2.x - (dx / dist) * (R + 4);
    const ey = p2.y - (dy / dist) * (R + 4);
    const color = edgeColors[i % edgeColors.length];
    ctx.save();
    /* draw self-loop as small circle above the node */
    if (e.from === e.to) {
      ctx.strokeStyle = color; ctx.lineWidth = 1.8;
      ctx.beginPath();
      ctx.arc(p1.x, p1.y - R - 8, 8, 0, 2 * Math.PI);
      ctx.stroke();
    } else {
      ctx.strokeStyle = color; ctx.lineWidth = 1.8;
      ctx.beginPath(); ctx.moveTo(sx, sy); ctx.lineTo(ex, ey); ctx.stroke();
      /* draw arrowhead at destination */
      const angle = Math.atan2(dy, dx);
      ctx.fillStyle = color;
      ctx.beginPath();
      ctx.moveTo(ex, ey);
      ctx.lineTo(ex - 9 * Math.cos(angle - 0.4), ey - 9 * Math.sin(angle - 0.4));
      ctx.lineTo(ex - 9 * Math.cos(angle + 0.4), ey - 9 * Math.sin(angle + 0.4));
      ctx.closePath(); ctx.fill();
      /* k-mer label above the edge midpoint */
      const mx = (p1.x + p2.x) / 2, my = (p1.y + p2.y) / 2;
      ctx.fillStyle = color; ctx.font = 'bold 9px ui-monospace, monospace';
      ctx.textAlign = 'center'; ctx.textBaseline = 'middle';
      ctx.fillText(e.kmer, mx, my - 7);
    }
    ctx.restore();
  });
  /* draw node circles with (k-1)-mer labels */
  for (const node of nodes) {
    const p = pos[node];
    ctx.save();
    ctx.fillStyle = '#1d3557'; ctx.strokeStyle = '#a0b8cc'; ctx.lineWidth = 1.5;
    ctx.beginPath(); ctx.arc(p.x, p.y, R, 0, 2 * Math.PI);
    ctx.fill(); ctx.stroke();
    ctx.fillStyle = '#fff'; ctx.font = 'bold 10px ui-monospace, monospace';
    ctx.textAlign = 'center'; ctx.textBaseline = 'middle';
    ctx.fillText(node, p.x, p.y);
    ctx.restore();
  }
}

function setStatus(t, cls) {
  const s = document.getElementById('status');
  s.textContent = t; s.className = 'status ' + cls;
}

function assemble() {
  const raw = document.getElementById('reads-input').value;
  const reads = raw.split('\n').map(r => r.trim()).filter(Boolean);
  const k = parseInt(document.getElementById('k-input').value, 10);
  if (!reads.length) { setStatus('Please enter at least one DNA read.', 'bad'); return; }
  const { edges, nodes } = buildDeBruijn(reads, k);
  if (!edges.length) { setStatus(i18nFmt('No k-mers of length %k% found — try shorter k or longer reads.', { k }), 'bad'); return; }
  const canvas = document.getElementById('graph-canvas');
  drawGraph(canvas, nodes, edges, k);
  const paths = eulerianPaths(nodes, edges);
  const contigs = paths.map(p => pathToContig(p, k)).filter(Boolean);
  const contigsOut = document.getElementById('contigs-out');
  contigsOut.innerHTML = '';
  if (contigs.length) {
    contigs.forEach(c => {
      const chip = document.createElement('span');
      chip.className = 'contig-chip'; chip.textContent = c;
      contigsOut.appendChild(chip);
    });
    setStatus(i18nFmt('Assembled %n% contig(s) from %e% k-mer edge(s) (k=%k%).', { n: contigs.length, e: edges.length, k }), 'ok');
  } else {
    setStatus('Graph built but no Eulerian path found — try different k.', 'info');
  }
  document.getElementById('graph-section').style.display = 'block';
}

document.getElementById('btn-assemble').addEventListener('click', assemble);
document.getElementById('btn-reset').addEventListener('click', () => {
  document.getElementById('reads-input').value = '';
  document.getElementById('graph-section').style.display = 'none';
  setStatus('', '');
});
document.getElementById('btn-example1').addEventListener('click', () => {
  document.getElementById('reads-input').value = EXAMPLE1;
  assemble();
});
document.getElementById('k-input').addEventListener('input', function () {
  document.getElementById('k-val').textContent = this.value;
});
Result
Console

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

The Real Complexity

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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/de-bruijn-assembly/Content licensed under CC BY-NC 4.0.