Indexing genomic diversity with sequence graphs

A linear reference chooses one path through a species’ variation. That simplification made modern genomics possible, but it creates reference bias: divergent sequence can be harder to align, genotype, and interpret. A pangenome represents many genomes together so shared sequence and alternative alleles remain part of the reference.

Graphs are a natural representation for this diversity. Common regions can share nodes and edges; divergent haplotypes can follow different paths. The draft Human Pangenome Reference (Liao et al., 2023) demonstrates why this matters at human scale, while tools such as vg (Garrison et al., 2018) show that graph references can support read mapping and variant analysis.

Representation alone is not enough. A practical pangenome must be searchable without scanning every genome independently. The challenge is to preserve graph diversity while recovering the speed and compactness of string indexes.

Questions that drive my work

The first question is which graph structures admit efficient indexes. For a string, the Burrows–Wheeler Transform and FM-index support compact full-text search (Ferragina and Manzini, 2005). Some graph classes generalize that structure, but arbitrary graphs do not inherit the same guarantees. Biological representation therefore constrains the available search algorithms.

The second is how to recognize useful structure. Wheeler graphs (Gagie et al., 2017) are edge-labeled graphs whose nodes admit an order compatible with edge labels, extending BWT-style indexing to graphs. Recognizing that order is NP-complete and hard to approximate (Gibney and Thankachan, 2019). The class is practical only if we can recognize members, produce an order, and explain failures at realistic sizes.

The third is how to trust a solver-backed algorithm. Heuristics and satisfiability solvers can make hard problems practical, but speed is not correctness. Every accepted graph should have an independently checkable order, and optimizations should preserve decisions.

The fourth is repair rather than diagnosis alone: when a graph lacks an indexable structure, the useful question is whether we can construct a related graph that preserves the biological paths that matter.

Directions I have explored

Making Wheeler graphs usable

I developed the Wheeler Graph Toolkit (WGT) (Chao et al., 2023) so researchers could generate, recognize, and visualize Wheeler graphs. The project addressed a practical gap between theoretical recognition algorithms and a complete workflow for deciding and inspecting an input graph.

WGT’s recognizer, Wheelie, combines a fast renaming heuristic with exact solvers. Incoming labels constrain where a node can appear; propagating those constraints resolves much of the order before search begins. Remaining ambiguity goes to permutation search or an SMT solver. The pattern is simple: use inexpensive structure to shrink the problem, then apply an exact method where uncertainty remains.

Generators provide known examples and counterexamples, while visualization makes the structure behind a solver result inspectable.

Verification, scaling, and graph repair

I have continued this work by separating correctness, capacity, and speed. Current methods compare recognition with an independent brute-force oracle on small graphs, re-validate every emitted order, and use regression tests to ensure faster encodings do not change decisions.

On the algorithmic side, lazy constraint generation avoids materializing the full solver encoding up front. The solver begins with a relaxation, checks candidate orders, and adds only the constraints a counterexample exposes.

Repair is a separate direction: unfolding a non-Wheeler directed acyclic graph into a Wheeler graph while preserving the path strings it represents. A graph that cannot be indexed then becomes a starting point rather than a dead end. These results are documented in the linked technical report, kept separate from the published WGT paper so the original contribution and the ongoing work remain distinguishable.

Future directions

Every fast index buys its speed with an assumption about the shape of the data, and in this corner of genomics that assumption is usually invisible to whoever runs the tool. The direction worth pursuing is the opposite one: recognition that scales and reports why it failed, repair that names which paths it had to change, and node orders a reader can verify without trusting the solver that produced them. A pangenome index should be able to say what it preserved, not only how fast it searched.