Efficient detection of genetic variations in graph structures
A rooted tree framework for linear time ultrabubble detection
Data Structures and Algorithms
Summary
Genetic differences between individuals can be represented using complex graphs, where paths correspond to genomes and variations show up as distinct routes. The authors improved a method to quickly find special, simple regions in these graphs called ultrabubbles, which represent important genetic variants without dead ends or loops. They introduced several techniques to speed up the detection process and reduce unnecessary checks, making it faster to identify these key variant patterns. These improvements help handle large genetic datasets more efficiently.
What this means in practice
- •For bioinformatics software developers: Implement faster ultrabubble detection algorithms for genome variation analysis in pangenomic graph tools.
- •For computational biologists: Analyze large pangenome graphs more efficiently by using improved methods to identify variant structures without dead ends or cycles.
Authors
Athanasios E. Zisis, Pål Sætrom
Abstract
Pangenomics uses graphs to show genetic differences within or between species. In these graphs, a path can represent one genome, while regions with different paths show genetic variation. Biedged graphs use black edges for sequences and grey edges for links between them. Snarls are minimal subgraphs of a biedged graph that are separated from the rest of the graph by removing two black edges. Ultrabubbles are minimal acyclic and tip-free snarls and thus are important variant structures because they have finite paths and lack dead ends. In our previous work, we showed that in linear time every bidirected graph can be transformed to a rooted biedged bipartite one, and that in these graphs, ultrabubbles can be enumerated with a lowest common ancestor (LCA)-based method in $O(Kn)$ time, where $n$ and $K$ are the number of nodes and given snarls, respectively, of the graph. Here, we present a series of practical and theoretical improvements to our previous LCA-based approach. First, we present a hybrid method that selects between the LCA-based method and the naive approach for evaluating a snarl, depending on the size of the snarl in relation to the number of tips and cycle-closing nodes in the graph. Second, by using the theoretical framework from our previous paper, we show that all ultrabubbles can be found in $O(n + m + K)$ time, where $m$ is the number of edges, by traversing the breadth-first search (BFS) tree of the biedged bipartite graph. Third, we show that any two snarls that are candidate ultrabubbles and share a frontier node cannot be ultrabubbles; the resulting set of snarls is compatible, bound by $n$, and defines exclusive families of nested snarls. We combine these three results into six methods and present benchmarking results that illustrate how the above improvements affect practical run-times for identifying ultrabubbles.