Billi

Billi is a tool designed to identify bubbles in a pangenome graph, represented in GFA format. Billi employs updated definitions of bubbles, termed panbubbles and hairpins. These definitions apply to both cyclic and acyclic subgraphs, enabling broader coverage of variant classes. Panbubbles and hairpins are guaranteed to be mutually non-overlapping except in cases when they follow a nested structure. By definition, they exclude tip vertices (dead ends). Billi is scalable to large pangenome graphs, including the full human pangenome graphs released by the HPRC. These properties make Billi a useful alternative method for analyzing variation sites and alleles in pangenome graphs. See the preprint for further details.

Illustration of nested panbubbles and hairpins. Three panbubbles (red) and one hairpin (blue) are highlighted.

• Installation
• Dependencies
• Usage
  • Decompose
  • Compact
• Example
• Running the test suite
• Limitations
• Citation

git clone https://github.com/at-cg/billi.git
cd billi
make 

• OS: Linux
• Compiler: GCC version 8 or newer
• Build tool: make
• Python: Version 3.8 or above; only needed to run the test suite, not for normal software use

Enumerates all panbubbles and hairpins in the input graph. The graph is first compacted internally before bubble detection is performed.

./billi decompose -i inputgraph.gfa > out.txt 

Merges long non-branching paths in the input graph into single vertices, producing a smaller, equivalent graph in the GFA format.

Visualisation of compaction operation

./billi compact -i inputgraph.gfa -o compactgraph.gfa 

See docs/commands.md for the command-line options.

./billi decompose -i test_files/edge_cases/nested.gfa > outputfile

Bandage visualisation of the nested.gfa test graph

The graph (nested.gfa) contains two bubbles, one completely nested in another.

Expected output:

The output format is similar to pangene.

CC	BB	bbID	bbDpt	parID	side1	side2	#alleles
CC	HP	bbID	side1	side2	#alleles
CC	AL	#hap	walk	hap_id
CC
BB	0	2	BB:1	<s6	<s4	-1
BB	1	1	-1	>s1	>s3	-1

• Every output starts with CC comment lines documenting column layout, followed by one row per panbubble/hairpin found.
• BB rows are panbubbles: bbID (unique ID), bbDpt: Depth of the bubble (1 means top-level),parID: ID of the parent bubble (-1 if top-level, or BB:<id>/HP:<id> if nested inside another panbubble/hairpin), side1/side2 (the two boundary nodes, with </> indicating the strand each is entered on), and #alleles.
• HP rows are hairpins: same fields as BB, minus parID.
• #alleles is -1 when allele walks weren't computed (e.g. the input GFA has no W/P lines). When alleles are available, each one is listed on its own AL row directly under the corresponding BB/HP row, and the block is terminated with a // line.

Other test graphs are available in the test folder. Our benchmark datasets are publicly available at: https://doi.org/10.5281/zenodo.21104719.

python3 src/test_script.py --binary ./billi --test-dir test_files --verbose

This is the same check run on every push/PR (see .github/workflows/test.yml).

• The code accepts only uncompressed GFA format. Other formats (e.g., .gbz, .vg) and compressed GFA files (.gfa.gz) are not supported.

• The algorithm assumes that every connected component of the input graph contains at least one tip vertex; otherwise, execution terminates with an error.

• The default heuristic approach for finding bubbles in Billi is significantly faster than the exact algorithm, but it may produce different output in certain edge cases.

• Printing alleles in every bubble can slow execution on large graphs. Use the -w flag to disable this feature.

• Code is currently compatible only with Linux OS.

If you use Billi, please cite:

Shreeharsha G Bhat, Daanish Mahajan, and Chirag Jain. Billi: Provably Accurate and Scalable Bubble Detection in Pangenome Graphs. bioRxiv (2025). https://doi.org/10.1101/2025.11.21.689636