cucapra / cucapra/pollen

Tracker: FlatGFA benchmarks

Open
#185 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
Rust
Stars
45
Forks
3
PR merge metrics
No merged PRs in 30d

Description

It's high time that we start measuring FlatGFA performance on "realistic" tasks against external baselines. I bootstrapped some really simple benchmarking infrastructure a while back, and it can only do two really basic things:

* [x] Compare parsing/conversion time: FlatGFA vs. odgi.
* [x] Compare a trivial "list the names of the paths" thing: FlatGFA vs. odgi vs. slow-odgi.

I think we need to look for workloads that are somehow representative of what people actually want to do, interactively, with these GFA analysis tools. These could be things that odgi does already, or it could be represented in other open-source tools that (by virtue of implementing that functionality) seem to be saying that the task is important. Here are some ideas… surely further googling could reveal more:

* [ ] `odgi extract`-like functionality. This is one of 3 benchmarks in [the odgi paper](https://doi.org/10.1093/bioinformatics/btac308), and the only one that is a pure-ish "GFA operator." The paper compares against `vg chunk`, so perhaps we should too. We could even reuse commands from [the script](https://github.com/pangenome/odgi-paper/blob/main/scripts/extract_time.sh). I have actually started an implementation, but it is not yet correct because I don't understand the spec for `odgi extract`.
* [ ] `odgi viz`-like visualization. This is the other non-parsing benchmark in the the odgi paper. I am skeptical of this one… it just seems pretty un-fun to do the drawing stuff, and maybe not that computationally intensive. And it's hard to divine the spec for what the visualization should even look like? Anyway, maybe this can be salvaged in a useful way. Perhaps it wants to be implemented in Python instead of in Rust?
* [ ] [Panacus](https://github.com/marschall-lab/panacus) histograms and growth statistics. This tool is written in Rust, so maybe it's a competitive baseline. Let's find out!
* [ ] Bubble detection, like [bubble_gun](https://github.com/fawaz-dabbaghieh/bubble_gun). AFAICT this is the only tool that does it? The algorithm doesn't seem _too_ hard to re-implement; there's a paper about it that explains it pretty clearly.
* [ ] Some [pancat](https://github.com/Tharos-ux/pancat) commands, such as `pancat stats`. Perhaps `pancat edit` would be a more interesting benchmark too?
* [ ] Relatedly, comparing *parsing* performance only against pancat's [gfagraphs](https://github.com/Tharos-ux/gfagraphs) library could be instructive. It's pure Python, however, so I'm guessing it can't be much faster than slow-odgi's parser?
* [ ] [gfatools](https://github.com/lh3/gfatools) is a C tool. It's not documented, but it seems to at least have `odgi extract`-like functionality and conversion to FASTA (like `odgi flatten`).
* [ ] [gretl](https://github.com/MoinSebi/gretl) contains a bunch of statistics calculations that we could try to re-implement. This one maybe seems like a good place to start since the specs may be clear? It's also implemented in Rust, so it may be a competitive baseline.
* [ ] [GFAffix](https://github.com/marschall-lab/GFAffix) is a special-purpose analysis that I honestly do not yet understand. But it seems like it may be computationally intensive?

Before all that, maybe it would also make sense to focus on the 3 specific pipelines that Andrea graciously showed off on Slack:

```
odgi build -g LPA.gfa -o - | odgi extract -i - -o - -r chm13__LPA__tig00000001:0-100 | odgi paths -i - -L | wc -l
odgi build -g LPA.gfa -o - | odgi extract -i - -o - -r chm13__LPA__tig00000001:0-100 | odgi stats -i - -S
odgi build -g LPA.gfa -o - | odgi extract -i - -o - -r chm13__LPA__tig00000001:0-100 | odgi sort -i - -o - -O -p gYs | odgi viz -i - -o x.png
```

…which would entail:

* [ ] Make `extract` actually work.
* [ ] Implement `sort`.
* [ ] Do *something* about visualization?
* [ ] Expose enough through the Python API to allow this type of composition while keeping data structures in memory.

On a very different level, we could consider something like sequence-to-graph alignment. The bottleneck there is unlikely to be the GFA representation, but who knows?

And finally: [smoothxg](https://github.com/pangenome/smoothxg), one of the steps in pggb, apparently composes the functionality from `odgi chop` and `odgi sort`. Maybe we can extract a sensible pipeline from that. For example, [the CLI help strings](https://github.com/pangenome/smoothxg/blob/986b11fd33b95200f476769df50d2e1cd4c070d8/src/main.cpp#L64) state that:

> prep is equivalent to odgi chop followed by odgi sort -p sYgs

…so that lays out a pretty specific pipeline in particular.

Contributor guide

No contributing guide indexed for this repository

Research direction

Start by reviewing the existing benchmarking infrastructure and the odgi-paper scripts/extract_time.sh. Compare the listed pipelines and candidate baselines, especially odgi extract, sort, stats, and viz, before choosing one workload with a clear specification. Done means a reproducible benchmark and an agreed comparison against the selected external tool.

Written by the indexing model from the issue text.

Assessment

Tech stack
c, python, rust, shell
Domain
bioinformatics, performance, testing, tooling
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.