Billi: Accurate and Scalable Bubble Detection in Pangenome Graphs

Billi accurately detects cyclic and nested genomic variants in pangenome graphs with an O(|V|^2(|V| + |E|)) algorithm, outperforming existing methods on complex structures.

• Why it matters: Capturing complex genomic variations like inversions requires representing cyclic structures and their hierarchical nesting, which current formalizations often fail to do, limiting variant characterization.
• What they did: The authors introduced two formalizations, panbubble and hairpin, that satisfy the strict nesting property and accommodate cycles, along with an exact and a heuristic algorithm implemented in the Billi tool, tested on human pangenome data.
• The result: Billi successfully recovers nested inversions and complex variants, such as at the human Y chromosome locus, outperforming existing methods by correctly representing variant nesting and capturing all variation.