Scalable Unified Metastatic Migration Inference on Trees (SUMMIT)

A repository for solving finding parsimonious migration histories subject to the Joint Parsimony objective.

We solve the Generalized Parsimonious Migration History Problem as well as a variant with Polytomy resolution.

Data

The PEACE data (SNV/SCNA tables, sample annotations) is not included in this repository; download peace_data from Zenodo: https://zenodo.org/records/19737930. Lines in scripts/ that read these files are commented out and point there.

Dependencies

Python ≥ 3.10 with a licensed Gurobi install, plus:

pip install gurobipy pyomo networkx pandas numpy loguru tqdm

Usage

gpmh.py labels a fixed tree; gpmh_pr.py additionally resolves polytomies.

Joint parsimony on a reconstructed LAML tree (m5k_lg30 from 10.1126/science.abc1944):

mkdir -p results
python gpmh.py fast_machina \
    laml/m5k_lg30/laml_tree_edgelist.tsv \
    laml/m5k_lg30/laml_leaf_labeling.csv \
    -e 1 -o results/m5k_lg30

Inputs: a tab-separated edgelist (parent child [weight]) and a CSV of leaf labels with columns leaf,label. -e 1 enables joint parsimony (migrations + migration graph edges); -e 0 gives plain parsimony.

Polytomy resolution on a clone tree (CRUKP2757 from https://doi.org/10.1038/s41586-026-10428-4):

mkdir -p results/CRUKP2757
python gpmh_pr.py \
    trees/CRUKP2757/CRUKP2757_edgelist.tsv \
    trees/CRUKP2757/CRUKP2757_sites_labeling.tsv \
    -o results/CRUKP2757/CRUKP2757

Inputs: a whitespace-separated edgelist and a labeling file with one vertex per line, <vertex> <site> [<site> ...]. -n N (default 50) enumerates up to N optimal solutions into results/CRUKP2757/solution_<i>/; -n 1 returns only the best.

Output

Each run writes <prefix>_vertex_labeling.csv, <prefix>_migration_graph.csv and <prefix>_results.json. gpmh_pr.py also writes the resolved tree (<prefix>_apr.edgelist) and <prefix>_migration_edge_frequency.csv.