Implement bubble finding in FlatGFA
- 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