Pangenome Graphs

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.

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.

<!-- {{c_html_intro}} -->
<p class="hint">{{hint_para}}</p>
<div class="controls" id="controls">
  <div class="variant-row" id="v1-row">
    <span class="variant-label">V1</span>
    <span class="variant-desc">{{v1_desc}}</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">{{v2_desc}}</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">{{v3_desc}}</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">{{btn_reset}}</button>
</div>

/* {{c_css_intro}} */
* { 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; }

// Code not found

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.

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

• Linear alignment is easy. Aligning a read of length $m$ to a linear reference of length $n$ costs $O(mn)$ with dynamic programming (Smith-Waterman / Needleman-Wunsch).
• Graph alignment is harder. When the reference is a directed graph with $N$ nodes and $E$ edges, the naive DP table has $O(mN)$ cells but each cell may look back at multiple predecessors — cost $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.

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.

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.