Indexing genomic diversity with sequence graphs

A linear reference picks one path through a species’ variation, and reads from other paths align worse. A pangenome graph stores shared sequence once and lets alternative alleles branch, as in vg (Garrison et al., 2018) and the Human Pangenome Reference (Liao et al., 2023). The cost is search. For a string, the Burrows–Wheeler transform and FM-index give compact, fast full-text search (Ferragina and Manzini, 2005); an arbitrary graph comes with no such guarantee.

I worked on the boundary between graphs that can be indexed this way and graphs that cannot, and on making that boundary something a user can check.

Questions that shaped this work

Which graphs admit BWT-style indexes? Wheeler graphs (Gagie et al., 2017) are edge-labeled graphs whose nodes admit an order compatible with their edge labels, and that order is what lets an FM-index generalize from strings to graphs. Deciding whether such an order exists is NP-complete for alphabets of two or more letters, even for acyclic graphs (Gibney and Thankachan, 2019).

Can the decision be made in practice? A class defined by an NP-complete property is useful only if real graphs can be checked at realistic sizes. My bet was that cheap structural reasoning could do most of the work before any search began.

Can a solver’s answer be trusted? Heuristics and SMT solvers make hard problems tractable, but a faster wrong answer helps no one. Every accepted graph should come with an order that can be checked independently.

What I built

WGT: the Wheeler Graph Toolkit

With Pei-Wei Chen, Sanjit Seshia, and Ben Langmead, I built WGT (Chao et al., 2023) to generate, recognize, and visualize Wheeler graphs. Its recognizer, Wheelie, first propagates label constraints: nodes are grouped and renamed by their incoming edges until each is confined to a narrow range of positions, or until a contradiction proves the graph is not Wheeler. Only the remaining ambiguity goes to permutation search or the Z3 SMT solver. With a 30-second limit, the earlier exponential algorithm timed out on 8,461 benchmark graphs and Wheelie’s permutation search on 784, all random; on de Bruijn and reverse-deterministic graphs, the renaming step cut SMT time by two to three orders of magnitude. Generators supply known Wheeler and non-Wheeler graphs, and the visualizer shows the order behind each answer.

Making the answer verifiable

After the paper, I tested the recognizer against a brute-force oracle on small graphs, re-checked every emitted order against the Wheeler axioms, and made the solver add its within-label ordering constraints lazily, only where a candidate order violated them. I also unfolded non-Wheeler acyclic graphs into Wheeler graphs that spell exactly the same set of strings, so a graph that fails recognition becomes a starting point rather than a dead end.

What remains open

An index buys its speed with an assumption about the shape of the data, and that assumption is usually invisible to whoever runs it. The useful direction is to make it visible: graph construction that aims for indexable structure from the start, repair that preserves what a graph spells without inflating it, and node orders that can be checked without trusting the solver that produced them.