goeBURST

MLST / cgMLST Minimum Spanning Tree visualization with goeBURST algorithm

Implements the goeBURST algorithm (Francisco et al., 2009) — a refinement of eBURST (Feil et al., 2004) — to construct a globally-optimized Minimum Spanning Tree from multi-locus sequence typing data. Renders publication-quality figures with pie-chart nodes.

Installation

pip install goeburst

Or from source:

git clone <repo-url> && cd goeburst
pip install .

Dependencies (installed automatically): numpy, matplotlib, networkx.

Quick Start

Command line

goeburst -p profileData.tab -i isolateData.tab -g serotype -o mst.png

Python API

from goeburst import (
    parse_profile_data, parse_isolate_data, build_st_table,
    goeBURST_mst, plot_goeBURST,
)

# 1. Load data
profiles, loci = parse_profile_data("profileData.tab")
isolates, meta_cols = parse_isolate_data("isolateData.tab")

# 2. Build ST-level summary
st_profiles, st_counts, st_meta, all_cats, skipped = build_st_table(
    profiles, isolates, "serotype"
)

# 3. Run goeBURST algorithm
edges = goeBURST_mst(st_profiles)

# 4. Render plot
plot_goeBURST(
    st_profiles, st_counts, st_meta, all_cats, edges,
    group_col="serotype", output_path="mst.png",
)

Input Format

Profile data (-p)

Tab- or comma-separated file where each row is an isolate and each column is a locus:

FILE    aroE    gdh     gki     recP    spi     xpt     ddl
isolate1    1   1   2   2   6   1   6
isolate2    1   1   4   1   6   1   6

• First column: isolate identifier (must match FILE in isolate data)
• Remaining columns: integer allele numbers (0 = missing / unknown)

Isolate data (-i)

FILE    ST  serotype    country
isolate1    1   O157    USA
isolate2    2   O104    DE

• Must contain: FILE (or ID) and ST columns
• Additional columns are available for pie-chart grouping

Algorithm

The goeBURST algorithm produces a complete Minimum Spanning Tree using tiebreak rules that prioritise biologically meaningful links:

1. Lower allelic distance — SLV (1 locus) > DLV (2) > TLV (3) > …
2. More SLV connections — favour STs that are hubs of single-locus variants
3. More DLV / TLV connections — secondary / tertiary tiebreaks
4. Lower ST identifier — deterministic final tiebreak

The MST is built via Kruskal's algorithm on the sorted edge list.

Edge Styles

References

• Francisco AP, Vaz C, Monteiro PT, et al. (2009) Global optimal eBURST analysis of multilocus typing data using a graphic matroid approach. BMC Bioinformatics, 10:152.
• Feil EJ, Li BC, Aanensen DM, et al. (2004) eBURST: inferring patterns of evolutionary descent among clusters of related bacterial genotypes from multilocus sequence typing data. Journal of Bacteriology, 186:1518–1530.

License

MIT