#graph #bioinformatics #tree #algorithm #cactus #ultrabubbles #biedged

saboten

Provides biedged graphs, cactus graphs and trees, and an algorithm for finding ultrabubbles in variation graphs

9 releases

0.1.2-alpha.3 Jun 29, 2021
0.1.2-alpha.2 Feb 9, 2021
0.1.0 Nov 24, 2020
0.0.3 Oct 17, 2020

#270 in Biology


Used in gfautil

MIT license

720KB
3K SLoC

Saboten - cactus graphs and ultrabubbles in Rust

A Rust implementation of the algorithm described in Superbubbles, Ultrabubbles and Cacti paper.

Supports transforming a GFA graph into a biedged graph, and further into cactus graphs, cactus trees, and bridge forests.

These structures can then be used to find the ultrabubbles in the graph (see the paper for more details).

For use of this library in a command line application, see gfautil.

Limitations

Input graphs must have all segment names as unsigned integers, and tightly packed, e.g. from 0 to N-1, if there are N segments, however the numbering does not have to start from zero.

Dependencies

~8–18MB
~208K SLoC