cucapra / cucapra/pollen

Implement bubble finding in FlatGFA

Open
#223 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

Let's add functionality to FlatGFA to find _bubbles_ and _superbubbles_. The end goal is to create a drop-in replacement for [the BubbleGun library][bg], or at least its `find_bubbles`, `connect_bubbles`, and `find_parents` functions.

As a brief reminder, a "bubble" is a pattern in a variation graph where there are multiple distinct paths between two vertices (segments). For more background on how bubbles are defined, see [the BubbleGun paper][bg paper] and [the flubble paper][flubble paper].

* [ ] Gather some background:
* Read the two papers above, including [the supplemental material for the BubbleGun paper][bg sup]'s Algorithm 1, to understand the definitions and algorithms involved.
* Download and try out [the BubbleGun tool][bg] so you understand how its various commands work.
* [ ] Implement the BubbleGun algorithm. Add a subcommand `fgfa bubbles` that uses the graph-traversal algorithm specified in the supplemental material.
* [ ] Add _differential testing_. The idea is to check that BubbleGun and `fgfa bubbles` produce the same answers on a few example graphs.
* [ ] Measure performance. Using a collection of larger graphs, compare the performance of BubbleGun with our implementation. Hopefully, we'll be faster! If not, we'll need to do some optimization at this stage.
* [ ] Add Python bindings. We would like to be able to call the above functionality from Python so that we can provide more of a drop-in replacement for the BubbleGun Python library.
* [ ] Explore the alternative definitions and algorithms in [the flubble paper][flubble paper] and [its implementation in the povu tool][povu]. Consider implementing these alternatives and comparing (correctness and performance) against povu.

At some point in this process, we will also approach the authors of [PangyPlot][] to see if our drop-in replacement could help them.

[bg]: https://github.com/fawaz-dabbaghieh/bubble_gun
[bg paper]: https://academic.oup.com/bioinformatics/article/38/17/4217/6633304
[flubble paper]: https://arxiv.org/abs/2410.20932
[bg sup]: https://oup.silverchair-cdn.com/oup/backfile/Content_public/Journal/bioinformatics/38/17/10.1093_bioinformatics_btac448/2/btac448_supplementary_data.pdf?Expires=1763701898&Signature=cW0PPb2cIaSp7FIQ3oLJxL9curPdXXM~oyq2QJ2IlnCEOd~G747s6ZwK3-SwDhLuiGBt-W-XYTHS4Ug4v2GZNJ6ZLsapagN9twfsxabAfP0uJdKGG5WY9VjZhCZExd6Do-XKWlY9PbP3HkwP-ve1JL~HcI5QrlI3Ccf2qnZLZ3-E4SCBG19KTGy~ESQvC4fn7y-ih00VUUyZdQ5eajbw23rCSC9yRTkiezoImxxqFIr7WY77Ve-donAT~0YcXpr0wbfwxJeysRasDeWk82t-vH-c5MaJtW0mpYLw4rhGeEQy1L~8pFm2BUVYLJr6NuC8nKqDc1Nu-Jcpwl1Q7iJIaw__&Key-Pair-Id=APKAIE5G5CRDK6RD3PGA
[povu]: https://github.com/urbanslug/povu/
[pangyplot]: https://github.com/ScottMastro/pangyplot

Contributor guide

No contributing guide indexed for this repository

Research direction

Start by reading the BubbleGun paper and supplemental Algorithm 1, then try the BubbleGun tool to understand find_bubbles, connect_bubbles, and find_parents. The issue names no repository files or tests; a complete effort would define the fgfa bubbles subcommand, differential tests, performance comparisons, Python bindings, and any selected flubble or povu alternatives.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
bioinformatics
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
20/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.