🌳 phylo

---

A fast, extensible, WebAssembly-ready phylogenetics library for Rust.

phylo provides memory-efficient data structures and algorithms for phylogenetic analysis and inference — from tree manipulation (SPR, NNI, rerooting) to tree statistics (phylogenetic diversity, RF distance, cophenetic distance) to maximum-likelihood modelling (GTR+I+G substitution models, Felsenstein pruning, ancestral reconstruction). It leans on Rust's memory safety, speed, and native WebAssembly support to stay both fast and portable.

Tree traversals and operations are exposed as derivable traits, so you get DFS/BFS/pre-/post-order, Euler tours, LCA queries, and distance metrics for free on your own types — and a ready-made PhyloTree when you don't want to implement one.

Highlights

• Trait-first design — compose narrow traits (RootedTree, RootedMetaTree, EulerWalk, DFS, Clusters, …) onto any type, or use the batteries-included PhyloTree.
• Arena-allocated trees — cache-friendly Vec-backed storage with usize node IDs.
• Constant-time LCA — an LcaOracle borrows the tree immutably and answers LCA queries in O(1) via an Euler tour + RMQ.
• Tree comparison — Robinson-Foulds, weighted RF, cluster affinity, and cophenetic distance, with distance-matrix builders.
• Maximum-likelihood modelling — GTR+I+G substitution models (JC69 through GTR), Felsenstein-pruning log-likelihood, and marginal/joint ancestral sequence reconstruction.
• I/O — Newick and Nexus parsing and serialization.
• Simulation — random trees (Yule, uniform).
• Optional parallelism — opt into rayon-backed computation with the parallel feature.
• Fallible by default — operations that a caller can misuse return Result with a typed error::TreeError; the library does not panic on bad input.

Installation

cargo add phylo

Feature flags

Feature	Default	Description
simple_rooted_tree	Yes	The concrete SimpleRootedTree / PhyloTree implementation.
non_crypto_hash	Yes	Use fxhash maps/sets instead of std for speed.
parallel		rayon-based parallel computation for the heavy metrics.
serde		Serialize/Deserialize for trees.

Quick start

Everything you need is in the prelude:

use phylo::prelude::*;

Build a tree

Create an empty tree, then attach children to node IDs:

use phylo::prelude::*;

let mut tree = PhyloTree::new(1);

tree.add_child(tree.get_root_id(), PhyloNode::new(2));
tree.add_child(tree.get_root_id(), PhyloNode::new(3));
tree.add_child(2, PhyloNode::new(4));
tree.add_child(2, PhyloNode::new(5));

Read and write Newick

use phylo::prelude::*;

let tree = PhyloTree::from_newick("((A:0.1,B:0.2),C:0.6);".as_bytes()).unwrap();
let newick = tree.to_newick();

Traverse

Traversals return an Iterator of nodes or node IDs in visiting order:

use phylo::prelude::*;

let tree = PhyloTree::from_newick("((A:0.1,B:0.2),C:0.6);".as_bytes()).unwrap();

let dfs = tree.dfs(tree.get_root_id()).unwrap();
let bfs = tree.bfs_ids(tree.get_root_id()).unwrap();
let postorder = tree.postord_ids(tree.get_root_id()).unwrap();

Constant-time LCA

Build an LcaOracle with tree.lca(); it borrows the tree immutably (so staleness is a compile error, not a runtime bug) and answers queries in O(1):

use phylo::prelude::*;

let tree = PhyloTree::from_newick("((A,B),(C,D));".as_bytes()).unwrap();

let a = tree.get_taxa_node_id(&"A".to_string()).unwrap();
let b = tree.get_taxa_node_id(&"B".to_string()).unwrap();

let lca = tree.lca();
let ancestor = lca.get_lca_id(&[a, b]);

Compare trees

Metrics account for both topology and branch lengths:

use phylo::prelude::*;

fn depth(tree: &PhyloTree, node_id: usize) -> f32 {
    tree.depth(node_id) as f32
}

let mut tree_1 = PhyloTree::from_newick("((A:0.1,B:0.2):0.6,(C:0.3,D:0.4):0.5);".as_bytes()).unwrap();
let mut tree_2 = PhyloTree::from_newick("((D:0.3,C:0.4):0.5,(B:0.2,A:0.1):0.6);".as_bytes()).unwrap();

tree_1.set_zeta(depth).unwrap();
tree_2.set_zeta(depth).unwrap();

let cluster_affinity = tree_1.ca(&tree_2);
let cophenetic = tree_1.cophen_dist(&tree_2, 2).unwrap();

Likelihood and ancestral reconstruction

Score an alignment against a tree under a substitution model, or reconstruct ancestral sequences at the internal nodes. The log-likelihood path (TreeLikelihood) runs Felsenstein's pruning algorithm alone — no reconstruction — while marginal/joint ASR (MarginalAsr / JointAsr) build on the same pruning core:

use phylo::prelude::*;

let tree =
    PhyloTree::from_newick("((A:0.1,B:0.2):0.15,(C:0.3,D:0.1):0.05);".as_bytes()).unwrap();

// A nucleotide alignment in FASTA — one sequence per leaf taxon.
let fasta = b">A\nACGTACGT\n>B\nACGTATGT\n>C\nACGAACGT\n>D\nTCGTACGA\n";
let aln = Alignment::from_fasta_bytes(fasta).unwrap();

// HKY85 with gamma-distributed rate heterogeneity (+G, 4 categories).
let model = GtrModel::<Nucleotide>::hky85([0.25, 0.25, 0.25, 0.25], 2.0)
    .unwrap()
    .with_gamma(0.5, 4)
    .unwrap();

// Log-likelihood of the alignment given the tree and model (pruning only).
let log_lik = tree.log_likelihood::<Nucleotide>(&model, &aln).unwrap();
assert!(log_lik.is_finite());

// Marginal ancestral sequence reconstruction fills the internal nodes.
let recon = tree.marginal_asr::<Nucleotide>(&model, &aln, false).unwrap();
let root_sequence = recon.sequence_string(tree.get_root_id());

Module map

Module	What it does
tree::simple_rtree	Core tree traits and SimpleRootedTree.
tree::ops	Mutating operations: SPR, NNI, reroot, contraction, subtree extraction.
tree::distances	RF, weighted RF, cluster affinity, cophenetic distance, distance matrices.
tree::io	Newick and Nexus reading/writing.
tree::simulation	Random tree generation.
iter	Traversals, Euler walks, and the LCA oracle.
models	GTR+I+G substitution models and their named special cases.
tree::likelihood	Felsenstein-pruning log-likelihood.
tree::asr	Marginal and joint ancestral sequence reconstruction.
error	error::TreeError and the parsing/model error types.

Examples

Runnable analyses live in the examples/ directory. To visualize their output, install the Python requirements first:

pip install -r examples/visualization/requirements.txt

Quantifying phylogenetic diversity — the Faith index across a set of trees. Run it, then plot with examples/visualization/pd.py:

cargo run --example phylogenetic-diversity

Visualizing tree space — all pairwise distances across a set of trees. Run it, then plot with examples/visualization/tree-space.py:

cargo run --example pairwise-distances

Benchmarks

Benchmarks use criterion and are split into four targets by what they measure:

Target	Covers
lca	LcaOracle construction, O(1) queries, and the uncached walk.
traversal	Post-order traversal, bipartitions, median node.
construction	Yule simulation, SPR, tree contraction.
distances	RF, cluster matching, cluster affinity, cophenetic distance.

cargo bench                      # everything
cargo bench --bench lca          # one target
cargo bench -- lca_oracle_query  # one group, by regex
cargo bench --features parallel  # adds the parallel cophenetic group

Each sweep reports throughput in elements (taxa) per second alongside wall time. That is the number to read: a linear routine holds its throughput flat across the sweep, while a quadratic one loses roughly a factor of four per fourfold jump in taxa. Reading the raw times alone hides which is which.

Some groups come in pairs that are only meaningful read together. contract_tree builds a throwaway LcaOracle per call, while contract_tree_with_oracle reuses one the caller hoisted; the gap between them at a given taxa count is what the O(n) index build costs, and it is the difference between the two that tells you whether a change touched the build or the contraction.

Criterion compares every run against the previous one automatically. To pin an explicit reference point:

git checkout main && cargo bench -- --save-baseline main
git checkout my-branch && cargo bench -- --baseline main

An HTML report with plots lands in target/criterion/report/index.html.

The quadratic groups (distances, and bipartitions in traversal) run at criterion's minimum sample count so they finish in minutes; their confidence intervals are wide by design. Read them for scaling behaviour, not for single-digit-percent regressions.

WebAssembly

phylo builds for wasm32 targets out of the box, making it suitable for in-browser phylogenetics — use your usual wasm toolchain (e.g. wasm-pack, or cargo build --target wasm32-unknown-unknown).

Citation

If you use phylo in your work, please cite this paper:

@article{vijendran2025phylo,
  title={Phylo-rs: an extensible phylogenetic analysis library in rust},
  author={Vijendran, Sriram and Anderson, Tavis and Markin, Alexey and Eulenstein, Oliver},
  journal={BMC bioinformatics},
  volume={26},
  pages={197},
  year={2025}
}

License

Licensed under the MIT License.