SplitAligner, end to end
Turn a species tree and a set of gene trees into a branch-coordinate matrix in which each branch carries a numeric value or an explicit missingness state — structural, fusion-related, topology-induced, or residual. This walkthrough uses the bundled toy example, so you can reproduce every output on your own machine.
SplitAligner.pl. The commands below mirror the steps in examples/run.sh.A branch is the split it makes
SplitAligner identifies a branch not by its drawn position or by node order, but by the bipartition (split) it induces on the taxa. For a gene g that samples only some taxa Tg, each species-tree branch b is projected onto the taxa actually present:
On the topology-congruent species-tree restriction, two non-deleted primitive branches map to the same reduced-tree edge exactly when their projected splits coincide. They do not become the same original branch: they become indistinguishable for that gene's taxon set, which is a fusion. If a projected side is empty, the branch instead has a structural absence. For an empirical free-topology gene tree, SplitAligner separately asks whether each independently observable projected split is recovered.
The display root is not the coordinate. SplitAligner's biological coordinate is the canonical unrooted split, not the displayed root position, internal-node number, traversal position, or child order. If two Newick representations encode the same weighted unrooted split object, changing only the display root or serialization does not change the underlying biological split identity.
The human-readable B aliases are serialization-local and may change between independently serialized species trees. When comparing independent representations, the canonical split key — not the B number alone — is the authoritative identity.
Rooting can still carry biological meaning in analyses that require direction or ancestry; it simply does not define SplitAligner's branch-coordinate identity.
The workflow has two modes: matrix builds the coordinate system and projects every gene onto it; finalize then classifies the resulting missingness where the paired evidence permits.
Install
You need Perl 5 (already present on macOS and most Linux systems). SplitAligner uses only core modules — no CPAN packages to install.
# clone the repository git clone https://github.com/wujiaqi06/SplitAligner cd SplitAligner # check it runs (prints the usage banner) perl SplitAligner.pl
That is the entire installation. The main controller is SplitAligner.pl; the per-step helpers live in scripts/ and are called for you.
Prepare your inputs
Species tree — one Newick tree. Branch lengths and support values are allowed and simply ignored during split-based mapping.
((A:0.1,B:0.2):0.2,(C:0.1,D:0.1):0.1):0.1;
Gene trees — Newick, one record per line, each line starting with a gene identifier immediately followed by its tree. Taxon names must match the species tree.
GeneA((A:0.1,B:0.2):0.2,(C:0.1,D:0.1):0.1):0.1; GeneB((A:0.2,C:0.1):0.1,(B:0.1,D:0.2):0.1):0.1;
SplitAligner distinguishes two kinds of gene-tree input, and you typically supply both:
- free — each gene tree inferred independently (its topology may disagree with the species tree);
- fix — each gene tree inferred under the species-tree topology (branch lengths only).
Comparing the two is what later separates coverage-driven absence from discordance-driven absence.
Quick start: the toy example
The repository ships a small example under examples/302mammal/ (a subset of free and fixed gene trees) for a fast end-to-end smoke test. From the repository root:
bash examples/run.sh toyThis runs the three program calls below in order. The rest of the tutorial unpacks what each one does and produces.
matrix mode — build the coordinate system
Run matrix once per gene-tree set. It labels the species-tree branches, projects every gene onto them, and writes a gene × branch matrix.
# from the repository root cd examples/302mammal perl ../../SplitAligner.pl --mode matrix \ --species input/speciesTree302.nwk \ --gene input/free_tree.examples.nwk \ --label free perl ../../SplitAligner.pl --mode matrix \ --species input/speciesTree302.nwk \ --gene input/fix_tree.examples.nwk \ --label fix
Key outputs (prefixed by --label):
species_tree.splits.txt— the canonical branch coordinate system (B1,B2, … on the species-tree backbone). This is the shared axis every gene is measured against.<label>.matrix_no_fuse.txt— primitive branches only.<label>.matrix_with_fuse.txt— the same, plus explicit fused-branch columns such asB12|B47for branches that merge under taxon pruning.<label>_splits/and<label>_split_branch_label/— per-gene split representations and their mapping onto the backbone.
A cell holds a numeric branch length where the branch's projected split was recovered, or NA where it was not — yet. Naming those NAs is the next step.
gene B1 B2 B3 B4 ... A1BG 0.1809315089 NA 0.0047384154 0.0057110032 ... A1CF 0.0376651404 0.0583312140 0.0032591533 ...
finalize mode — name every absence
Give finalize both matrices. It first identifies primitive NAs represented by a numeric fused coordinate (NA_fuse), then compares the free and fixed matrices on shared genes to separate structural absence (NA_struct) from topology-induced absence (NA_topo). If fixed-side numeric evidence is unavailable, a residual generic NA is retained. Passing --species_tree also computes branch-wise support.
perl ../../SplitAligner.pl --mode finalize \ --free free.matrix_with_fuse.txt \ --fix fix.matrix_with_fuse.txt \ --final_label final \ --species_tree species_tree.forSplit.nwk
Outputs:
final.free.na_classified.txt/final.fix.na_classified.txt— classified matrices, with residual genericNAretained when the fixed side lacks numeric evidence;<input>.na_fuse.txt— the intermediate fusion-rescue tables;final.support_b.txtandspecies_tree.support_b.nwk— branch-wise support (see step 7).
The comparison is defined only for genes present in both inputs; if there are no shared genes, SplitAligner stops with an error rather than guessing.
gene B1 B2 B3 ... A1BG 0.1809315089 NA_struct 0.0047384154 ...
Reading the states
Every gene × branch cell ends up as exactly one of the values below. A residual generic NA is an intentional bookkeeping state: it is not promoted to NA_topo without fixed-side numeric evidence.
| Cell value | Meaning |
|---|---|
| numeric | Mapped. The branch's projected split was observed in this gene; the value is its branch length. |
| NA_fuse | The primitive branch is not independently observable after taxon pruning; a fused coordinate may carry a numeric edge length, but that value is not an independent estimate for the primitive branch. |
| NA_struct | A projected side is empty, so the branch has no projected identity for this gene and is not evaluable (a coverage effect). |
| NA_topo | The branch has numeric primitive evidence on the fixed side, but its projected split is not recovered in the inferred free-topology tree — consistent with topology-induced discordance. |
| NA | Residual: retained when there is no fixed-side numeric evidence to decide otherwise. |
The categories partition the axis — they add up to the whole ledger:
Once NA is split into why, downstream rate or selection analyses can handle, filter, and audit the states explicitly instead of treating every absence as the same opaque value.
Branch-wise support
When you pass --species_tree, finalize writes final.support_b.txt: for each backbone branch, how much numeric evidence it retains in the free trees relative to the fixed trees, on shared genes.
branch_id branch_type n_shared_genes n_fix_non_na n_free_non_na support_percent discordance_percent B1 terminal 5 5 5 100.0000000000 0.0000000000 B2 terminal 5 4 4 100.0000000000 0.0000000000 B3 terminal 5 4 4 100.0000000000 0.0000000000
The companion species_tree.support_b.nwk is a standard Newick tree with each internal branch's Support written in the bootstrap position, so you can open it in any tree viewer (e.g. FigTree) and see concordance mapped straight onto the topology.
Scaling up
The same two modes run at full scale. The bundled preprint example uses 2,275 free-topology and 2,275 fixed-topology gene trees across 302 mammals:
bash examples/run.sh preprintOn the shared concordance subproblem, SplitAligner's Support(b) closely matches PhyParts (Pearson r = 0.99997 across 299 internal branches). On the reported single-machine benchmark, the full SplitAligner workflow took 9 min 52 s versus 1 h 50 min 53 s for PhyParts in its quick concordance setting — about 11× faster on this dataset. This is a calibration and runtime comparison, not a claim of functional equivalence.
Explore Catnip10
Let taxon pruning act alone, with no gene-tree discordance. The full B1–B17 axis stays frozen while each deletion updates the graph-determined ledger: observed, NA_fuse, or NA_struct. In this experiment NA_topo is always zero.