odgi_notes.md

Reply to Arun — odgi subcommands for JBrowse

Hi Arun,

Great to hear about the odgi clone. I'll share some of my efforts to integrate odgi and pangenomes into jbrowse. Big caveat up front: we're still pretty naive about graph/pangenome methods, and the approach we were exploring was frankly a bit weird and specific to shoehorning a graph into a linear genome browser. So please read the below as "here's what we poked at and where we got stuck," not a considered spec — and weight the parts we flag as broadly useful over the parts that are just our own oddball need.

What we're trying to do (which may itself be the wrong framing)

For JBrowse we were mostly trying to linearize a pangenome onto a reference coordinate system so we could draw stacked haplotypes in a normal left-to-right genome browser, plus pull small subgraphs on demand for the region a user is looking at. We're not sure this is even the right way to think about it — it's possible the whole "flatten it to a reference" instinct is fighting the data — so take our specific asks with a grain of salt.

Note that one of the things we were trying to design was a 'tabix-indexed GFA-like format' so we could query small segments of the graph from client side js without a complex database. I am still unsure if this is a fools errand of not

The subcommands we were using

In rough priority order:

1. odgi untangle — by far the most valuable to us. We used it to project haplotype paths onto reference paths and emit PAF:

   odgi untangle -i graph.og -R <ref-paths> -Q <query-paths> -n 1 -p \
     | sort | bgzip > <ref>.synteny.paf.gz
   tabix <ref>.synteny.paf.gz
   

   This gives a "star topology" (one reference, N alignments) that stacks nicely. On chr20 (919 paths) it was ~1m39s / 2.1 GB peak. We ran two coarseness tiers, -j 0.5 -m 1000 for macro blocks and -j 0 -m 0 for full detail.

   Two things hurt here, and these feel like they'd help anyone consuming untangle output, not just us:

   • Strand column reflects graph-internal orientation, not biology. ~51% of chr20 positions came out minus-strand even after grooming. That was unusable for us, and I'd guess it's confusing for anyone treating untangle output as an alignment.
   • We wanted to actually show variants with CIGAR or cs tag, but these were not outputted. Since there was no per-base alignment in the untangle output we tried to project variants separately with vg deconstruct, and the snarl boundaries didn't line up with untangle's block boundaries — we ended up discarding ~282k variants on chr20 just to keep a monotonic cs string. Native CIGAR/cs from untangle would remove that whole lossy step, and PAF with cs is a pretty universally-consumable output. (This one we feel more confident is broadly useful.)

2. odgi extract + odgi view — for interactive on-demand subgraphs:

   odgi extract -i graph.og -r <path:start-end> -c <context> -t <threads> -o sub.og
   odgi view -i sub.og -g
   

   The blocker was a fixed ~6s deserialization cost per query regardless of region size (a 1 bp query cost the same as a 1 Mb query). Threading helped (47s → 8s at 16 cores) but the resident-process assumption made it unusable for a stateless browser backend. vg's xg was ~9x faster on small regions. Cheap random region access without loading the whole graph would be the single biggest win for us — though I'll admit "stateless per-request subgraph extraction" is a browser-specific need, so this may be lower value for typical batch/CLI users than it is for us.

3. odgi build — prerequisite, but load-bearing in ways that weren't obvious:

   odgi build -g source.gfa -O -s -o graph.og
   

   -O (node-id compaction) and -s (topological sort) were mandatory — extract failed silently-ish without them, and this wasn't documented. We also hit build silently dropping W-lines and producing an empty graph with no error. unchop crashed reliably with vector allocation errors (v0.9.4-2-g405be8f6). These are just plain robustness bugs / doc gaps — no JBrowse-specific angle, they'd bite anyone, so probably worth fixing regardless of what we're doing.

4. odgi groom, odgi paths, odgi bin — used incidentally around the above.

Where we were probably misguided

• The "tabix a GFA" / enumerate-snarls-from-every-reference idea. We flirted with indexing graph structure directly and enumerating snarls (bubbles) against all possible reference paths in the graph, so any haplotype could serve as the coordinate system. In hindsight this seems combinatorially wasteful and conceptually muddled — untangle blocks and vg deconstruct snarls "decompose the graph differently and don't line up at boundaries," so trying to reconcile every-reference snarl sets was probably a dead end. We may have been solving the wrong problem.

• Writing our own linearizer. Slower and heavier than untangle; not worth it.

Potential future directions for jbrowse pangenome visualization

After MemPanG and talking to Scott (PangyPlot), we suspect BubbleGun-style bubble/superbubble decomposition is a better framing than linearization — decompose the graph into a chain of bubbles and render that structure directly, rather than forcing everything onto one linear reference. Scott said this was absolutely essential for getting his Pangyplot working https://pangyplot.research.sickkids.ca/. I haven't actually investigated this post-MemPanG though, so it's just a hunch. I am unsure if odgi or your work has any overlap with this

One thing we'd be curious about — storage/query backend

Since a big chunk of our pain was the serving layer (the ~6s whole-graph deserialization on every extract), we're curious what you're planning for storage and random access. If you end up leaning on something columnar like DuckDB/Parquet/Arrow, our naive take is that the split matters a lot:

• Great fit for the tabular/index side. Coordinate lookups, interval range-queries, the linearized untangle PAF blocks — a read-only columnar file range-queried per request would solve our stateless-backend problem more cleanly than tabix does.
• Poor fit for the graph-traversal core. extract (BFS + context expansion), path walking, topological sort, snarl/bubble decomposition are pointer-chasing algorithms. Expressing those as SQL / recursive CTEs tends to be slow and memory-heavy — the "magnitudes faster" win almost certainly comes from an in-memory succinct graph representation (like odgi/xg already are), with the columnar store used as an index beside it rather than as the traversal engine.

Not prescribing anything — just flagging the distinction since the serving layer is where a browser integration lives or dies. (If you're distributing prebuilt files, on-disk format stability across versions is also worth pinning down early.)

TL;DR for your prioritization

Split by how confident we are it helps beyond just us:

Probably useful to lots of people (not JBrowse-specific):

1. untangle with CIGAR/cs output and a biologically meaningful strand — makes the output a first-class alignment anyone can consume.
2. build robustness — clear errors instead of silent W-line dropping / empty graphs, and documenting the -O -s requirement; fix the unchop crash.

Mostly our own oddball need (lower priority unless it's easy): 3. extract with cheap per-request random region access (no fixed whole-graph deserialization) — great for our stateless browser backend, less obviously valuable for batch/CLI workflows.

And genuinely, if you think our linearize-to-a-reference framing is misguided, we'd love to hear it — you'll have a much better sense than we do of what a pangenome tool should expose to a viewer.

Happy to share graphs/test data or jump on a call. Really looking forward to the benchmarks.

Thanks, Colin