Introduction

For decades, biologists worked with one human reference genome: a consensus sequence assembled from a handful of donors and treated as the universal template. Every new genome we sequenced was compared against it — variants were whatever deviated from this single standard.

The problem is that no two humans are identical. Millions of short substitutions, hundreds of thousands of insertions, deletions, and structural rearrangements separate any two people. The reference captures the most common version at each position, but that means the reference is wrong for everyone in slightly different ways. Reads that span a region absent from the reference simply fail to map — a phenomenon called reference bias.

A pangenome graph replaces the linear reference with a directed graph. Sequence that is shared across all genomes becomes shared nodes; places where individuals differ branch into parallel bubbles — one path per variant. Every genome in the collection is represented as a walk through this graph. Nothing is discarded, nothing is privileged as the canonical sequence.

The Human Pangenome Reference Consortium published the first draft human pangenome in 2023, encoding 47 diverse genomes and capturing over 119 million base pairs of sequence not present in the original GRCh38 reference. The field is active and open — see related work on genome assembly and sequence alignment.

Try It: Build a Variation Graph

Below is a tiny population: five individuals, each carrying some combination of three variants (V1, V2, V3) relative to a shared backbone. Toggle which individuals carry each variant and watch the graph rebuild in real time.

<!-- Pangenome graph demo — variation graph with bubbles for each variant -->
<p class="hint">Five individuals, three variants. Toggle which individuals carry each variant (V1/V2/V3) — the graph rebuilds in real time. Bubbles form where some individuals differ; they collapse when everyone agrees.</p>
<div class="controls" id="controls">
  <div class="variant-row" id="v1-row">
    <span class="variant-label">V1</span>
    <span class="variant-desc">SNP — single nucleotide change</span>
    <div class="checkboxes" id="v1-checks"></div>
  </div>
  <div class="variant-row" id="v2-row">
    <span class="variant-label">V2</span>
    <span class="variant-desc">Insertion — extra sequence present</span>
    <div class="checkboxes" id="v2-checks"></div>
  </div>
  <div class="variant-row" id="v3-row">
    <span class="variant-label">V3</span>
    <span class="variant-desc">Deletion — sequence removed</span>
    <div class="checkboxes" id="v3-checks"></div>
  </div>
</div>
<div class="canvas-wrap">
  <canvas id="graph" width="560" height="240"></canvas>
</div>
<div class="legend" id="legend"></div>
<div class="status" id="status"></div>
<div class="btns">
  <button id="reset-btn" type="button" class="ghost">Reset</button>
</div>

/* Styles for the pangenome variation graph demo */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; background: transparent; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .8rem; line-height: 1.5; }
.controls { display: flex; flex-direction: column; gap: .4rem; margin-bottom: .9rem; }
.variant-row { display: flex; align-items: center; gap: .5rem; flex-wrap: wrap; }
.variant-label { font: 700 13px ui-monospace, monospace; background: #1d3557; color: #fff;
                 padding: 1px 7px; border-radius: 4px; min-width: 28px; text-align: center; }
.variant-desc { font-size: .82rem; color: #555; flex: 1; min-width: 120px; }
.checkboxes { display: flex; gap: .35rem; }
.ind-btn { font: 600 12px system-ui; padding: 2px 9px; border: 1.5px solid #9baab5;
           background: #fff; color: #666; border-radius: 5px; cursor: pointer; transition: all .12s; }
.ind-btn.on { background: #1d3557; border-color: #1d3557; color: #fff; }
.canvas-wrap { overflow-x: auto; }
canvas { display: block; max-width: 100%; }
.legend { display: flex; flex-wrap: wrap; gap: .35rem .7rem; margin-top: .5rem; font-size: .8rem; }
.legend-item { display: flex; align-items: center; gap: 4px; }
.legend-swatch { width: 18px; height: 4px; border-radius: 2px; }
.status { font-size: .9rem; font-weight: 600; min-height: 1.3em; margin-top: .4rem; color: #1d3557; }
.btns { margin-top: .6rem; }
button { font: 600 13px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Pangenome variation graph demo: toggle which individuals carry each variant,
// then redraw the graph showing bubbles (parallel paths) where variation exists.

const INDIVIDUALS = ['I1','I2','I3','I4','I5'];
const COLORS = ['#e63946','#2a9d8f','#e9c46a','#a8dadc','#f4a261'];
// Three variants in the population (V1=SNP, V2=insertion, V3=deletion)
const VARIANTS = ['V1','V2','V3'];

// Which individuals currently carry each variant (user-adjustable)
const state = {
  V1: new Set(['I1','I2','I3']),
  V2: new Set(['I2','I4']),
  V3: new Set(['I1','I3','I5'])
};

// Shared backbone nodes (reference sequence segments)
const BACKBONE = ['A','B','C','D','E'];

function buildControls() {
  // Build toggle buttons for each individual per variant
  VARIANTS.forEach(vname => {
    const container = document.getElementById(vname.toLowerCase() + '-checks');
    INDIVIDUALS.forEach((ind, i) => {
      const btn = document.createElement('button');
      btn.type = 'button';
      btn.className = 'ind-btn' + (state[vname].has(ind) ? ' on' : '');
      btn.textContent = ind;
      btn.title = ind;
      btn.addEventListener('click', () => {
        state[vname].has(ind) ? state[vname].delete(ind) : state[vname].add(ind);
        btn.classList.toggle('on', state[vname].has(ind));
        draw();
      });
      container.appendChild(btn);
    });
  });
}

function draw() {
  const canvas = document.getElementById('graph');
  const ctx = canvas.getContext('2d');
  const W = canvas.width, H = canvas.height;
  ctx.clearRect(0, 0, W, H);

  // Graph layout — 8 columns across the canvas
  const cols = BACKBONE.length + VARIANTS.length;
  const colW = W / (cols + 1);

  // Node positions on canvas
  // Layout: A -> [V1 bubble] -> B -> [V2 bubble] -> C -> [V3 bubble] -> D -> E
  const refY = H / 2;
  const bubbleH = 52;

  const nodes = {
    A: { x: colW * 1, y: refY },
    // V1 bubble nodes (REF=lower path, ALT=upper path)
    V1_REF: { x: colW * 2, y: refY + bubbleH },
    V1_ALT: { x: colW * 2, y: refY - bubbleH },
    B: { x: colW * 3, y: refY },
    // V2 bubble nodes
    V2_REF: { x: colW * 4, y: refY + bubbleH },
    V2_ALT: { x: colW * 4, y: refY - bubbleH },
    C: { x: colW * 5, y: refY },
    // V3 bubble nodes
    V3_REF: { x: colW * 6, y: refY + bubbleH },
    V3_ALT: { x: colW * 6, y: refY - bubbleH },
    D: { x: colW * 7, y: refY },
    E: { x: colW * 8, y: refY }
  };

  // Determine bubble state for each variant
  const v1active = state.V1.size > 0 && state.V1.size < INDIVIDUALS.length;
  const v1all = state.V1.size === INDIVIDUALS.length;
  const v1none = state.V1.size === 0;
  const v2active = state.V2.size > 0 && state.V2.size < INDIVIDUALS.length;
  const v2all = state.V2.size === INDIVIDUALS.length;
  const v2none = state.V2.size === 0;
  const v3active = state.V3.size > 0 && state.V3.size < INDIVIDUALS.length;
  const v3all = state.V3.size === INDIVIDUALS.length;
  const v3none = state.V3.size === 0;

  // Draw structural edges (reference backbone + bubble paths)
  ctx.lineCap = 'round';
  ctx.lineJoin = 'round';

  function drawEdge(from, to, color, dashed) {
    const f = nodes[from], t = nodes[to];
    ctx.beginPath();
    if (dashed) ctx.setLineDash([5, 4]); else ctx.setLineDash([]);
    ctx.strokeStyle = color;
    ctx.lineWidth = 2.2;
    ctx.moveTo(f.x, f.y);
    ctx.lineTo(t.x, t.y);
    ctx.stroke();
    ctx.setLineDash([]);
  }

  // Reference paths use light gray; alternate paths use dark blue
  const refColor = '#b0bec5';
  const altColor = '#1d3557';

  // V1 bubble
  if (v1none) {
    drawEdge('A', 'B', refColor, false);
  } else if (v1all) {
    drawEdge('A', 'V1_ALT', altColor, false);
    drawEdge('V1_ALT', 'B', altColor, false);
  } else {
    drawEdge('A', 'V1_REF', refColor, false);
    drawEdge('V1_REF', 'B', refColor, false);
    drawEdge('A', 'V1_ALT', altColor, false);
    drawEdge('V1_ALT', 'B', altColor, false);
  }

  // V2 bubble
  if (v2none) {
    drawEdge('B', 'C', refColor, false);
  } else if (v2all) {
    drawEdge('B', 'V2_ALT', altColor, false);
    drawEdge('V2_ALT', 'C', altColor, false);
  } else {
    drawEdge('B', 'V2_REF', refColor, false);
    drawEdge('V2_REF', 'C', refColor, false);
    drawEdge('B', 'V2_ALT', altColor, false);
    drawEdge('V2_ALT', 'C', altColor, false);
  }

  // V3 bubble
  if (v3none) {
    drawEdge('C', 'D', refColor, false);
  } else if (v3all) {
    drawEdge('C', 'V3_ALT', altColor, false);
    drawEdge('V3_ALT', 'D', altColor, false);
  } else {
    drawEdge('C', 'V3_REF', refColor, false);
    drawEdge('V3_REF', 'D', refColor, false);
    drawEdge('C', 'V3_ALT', altColor, false);
    drawEdge('V3_ALT', 'D', altColor, false);
  }
  drawEdge('D', 'E', refColor, false);

  // Draw each individual's path through the graph (colored, semi-transparent)
  INDIVIDUALS.forEach((ind, idx) => {
    const col = COLORS[idx];
    ctx.globalAlpha = 0.55;
    ctx.lineWidth = 2.8;
    ctx.strokeStyle = col;
    ctx.setLineDash([]);

    function seg(from, to) {
      const f = nodes[from], t = nodes[to];
      ctx.beginPath();
      ctx.moveTo(f.x, f.y);
      ctx.lineTo(t.x, t.y);
      ctx.stroke();
    }

    // V1 segment
    if (v1none || (!state.V1.has(ind) && !v1all)) {
      seg('A', 'B');
    } else if (v1all) {
      seg('A', 'V1_ALT'); seg('V1_ALT', 'B');
    } else {
      if (state.V1.has(ind)) { seg('A', 'V1_ALT'); seg('V1_ALT', 'B'); }
      else { seg('A', 'V1_REF'); seg('V1_REF', 'B'); }
    }
    // V2 segment
    if (v2none || (!state.V2.has(ind) && !v2all)) {
      seg('B', 'C');
    } else if (v2all) {
      seg('B', 'V2_ALT'); seg('V2_ALT', 'C');
    } else {
      if (state.V2.has(ind)) { seg('B', 'V2_ALT'); seg('V2_ALT', 'C'); }
      else { seg('B', 'V2_REF'); seg('V2_REF', 'C'); }
    }
    // V3 segment
    if (v3none || (!state.V3.has(ind) && !v3all)) {
      seg('C', 'D');
    } else if (v3all) {
      seg('C', 'V3_ALT'); seg('V3_ALT', 'D');
    } else {
      if (state.V3.has(ind)) { seg('C', 'V3_ALT'); seg('V3_ALT', 'D'); }
      else { seg('C', 'V3_REF'); seg('V3_REF', 'D'); }
    }
    seg('D', 'E');
    ctx.globalAlpha = 1;
  });

  // Draw nodes on top of edges
  Object.entries(nodes).forEach(([name, pos]) => {
    const isVariant = name.includes('_');
    const isRef = name.endsWith('_REF');
    const isAlt = name.endsWith('_ALT');
    const vname = isVariant ? name.split('_')[0] : null;

    // Skip bubble nodes that are not visible in this configuration
    if (isVariant) {
      const vcount = vname ? state[vname].size : 0;
      const allCount = INDIVIDUALS.length;
      if (isRef && (vcount === 0 || vcount === allCount)) return;
      if (isAlt && vcount === 0) return;
    }

    ctx.beginPath();
    ctx.arc(pos.x, pos.y, 9, 0, Math.PI * 2);
    ctx.fillStyle = isAlt ? '#1d3557' : (isRef ? '#90a4ae' : '#e8eef3');
    ctx.strokeStyle = isAlt ? '#1d3557' : '#78909c';
    ctx.lineWidth = 1.8;
    ctx.fill(); ctx.stroke();

    // Node label (backbone = letter, ALT = variant name, REF = variant + degree sign)
    ctx.fillStyle = isAlt ? '#fff' : '#1d3557';
    ctx.font = '700 9px ui-monospace, monospace';
    ctx.textAlign = 'center';
    ctx.textBaseline = 'middle';
    const label = isVariant ? (isAlt ? vname : vname + '°') : name;
    ctx.fillText(label, pos.x, pos.y);
  });

  // Update status bar and legend
  const bubbleCount = [v1active, v2active, v3active].filter(Boolean).length;
  document.getElementById('status').textContent =
    i18nFmt('Graph has %n% active bubble(s).', { n: bubbleCount });
  updateLegend();
}

function updateLegend() {
  // Rebuild legend showing each individual's carried variants
  const leg = document.getElementById('legend');
  leg.innerHTML = '';
  INDIVIDUALS.forEach((ind, i) => {
    const item = document.createElement('div');
    item.className = 'legend-item';
    const swatch = document.createElement('div');
    swatch.className = 'legend-swatch';
    swatch.style.background = COLORS[i];
    const label = document.createElement('span');
    const variantsCarried = VARIANTS.filter(v => state[v].has(ind)).join(', ');
    label.textContent = variantsCarried
      ? i18nFmt('%ind%: carries %variants%', { ind: ind, variants: variantsCarried })
      : i18nFmt('%ind%: reference only', { ind: ind });
    item.appendChild(swatch);
    item.appendChild(label);
    leg.appendChild(item);
  });
}

document.getElementById('reset-btn').addEventListener('click', () => {
  // Reset state to default configuration
  state.V1 = new Set(['I1','I2','I3']);
  state.V2 = new Set(['I2','I4']);
  state.V3 = new Set(['I1','I3','I5']);
  document.querySelectorAll('.ind-btn').forEach(btn => btn.classList.remove('on'));
  VARIANTS.forEach(vname => {
    const container = document.getElementById(vname.toLowerCase() + '-checks');
    const buttons = container.querySelectorAll('.ind-btn');
    buttons.forEach(btn => {
      btn.classList.toggle('on', state[vname].has(btn.textContent));
    });
  });
  draw();
});

buildControls();
draw();
Result
Console

When nobody carries a variant the bubble collapses and the graph is just a straight line. When everyone carries it the reference path disappears. In between you get a bubble — the defining structure of a pangenome graph. Each colored path through the graph is one individual's genome.

The Real Complexity

Pangenome graphs solve the bias problem but introduce new algorithmic challenges:

  • Linear alignment is easy. Aligning a read of length mm to a linear reference of length nn costs O(mn)O(mn) with dynamic programming (Smith-Waterman / Needleman-Wunsch).
  • Graph alignment is harder. When the reference is a directed graph with NN nodes and EE edges, the naive DP table has O(mN)O(mN) cells but each cell may look back at multiple predecessors — cost O(m(N+E))O(m(N + E)). On a DAG (directed acyclic graph) this is still polynomial; on a general graph with cycles it becomes NP-hard in the worst case.
  • Practical graphs are near-DAGs. Real pangenome graphs are almost acyclic (most variation is a simple bubble), so tools like vg and GraphAligner achieve near-linear performance by topological ordering and banded DP. The hard cases arise with large, complex structural variants or tandem repeats that create many-layered bubbles.
  • Haplotype threading — asking which paths through the graph best explain a set of reads — reduces to a kind of sequence alignment on an exponential set of candidate strings, related in complexity to problems studied in genome assembly.

The take-away: pangenome graphs trade a solved alignment problem for a harder one, but careful graph construction keeps the hard cases rare and the practical tools fast.

Where It Matters

Eliminating reference bias has immediate consequences across genomics:

  • Variant calling: reads that previously failed to map near insertions or structural variants now align correctly, exposing millions of variants that were effectively invisible to linear-reference pipelines.
  • HLA typing: the hyper-variable HLA region encodes immune response genes. Its variants are so numerous and divergent that linear-reference alignment fails badly here; graph-based HLA typing is dramatically more accurate.
  • Population genetics: a pangenome built from globally diverse donors treats all ancestral backgrounds equally. Studies built on the old reference systematically underrepresent non-European populations.
  • Personalized medicine: in principle, a patient's reads can be aligned to a pangenome that already contains their likely haplotype, making variant interpretation more precise.
  • Graph genome formats: the field converged on GFA (Graphical Fragment Assembly) as the standard interchange format, and the vg toolkit as the reference implementation — open tools that connect pangenomics to the broader bioinformatics ecosystem.

The same variation-graph idea appears in genome assembly, where overlapping reads are assembled into a graph before being resolved into a linear sequence.

Conclusion

The single reference genome was a powerful simplification, but every simplification has a cost: millions of variants hidden, entire populations underrepresented, reads silently discarded. The pangenome graph pays back that debt by making every genome a first-class citizen — a path through a shared structure rather than a deviation from a chosen template.

The algorithmic price is real: graph alignment is harder than string alignment, and the hardest cases are genuinely intractable. But in practice, the graphs that biology produces are well-structured enough that efficient algorithms exist, and the gains in completeness and fairness are enormous.

Explore further: genome assembly shows how the graph structure first appears when assembling reads, and sequence alignment covers the dynamic-programming foundations that graph alignment generalizes.

Share this article

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

Comments

Loading comments...

https://www.kipuhub.com/en/article/pangenome-graphs/Content licensed under CC BY-NC 4.0.