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


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

#245 in Biology

Used in gfautil

MIT license


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.


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.


~208K SLoC