Microbiome studies that sequence the 16S rRNA gene, a roughly 1,500-base marker present in every bacterium, routinely compare samples with UniFrac. UniFrac is a distance that counts how much of the branch length on an evolutionary tree is unique to one sample rather than shared with another. Every such analysis takes a single tree as given. That tree is an estimate, sometimes a crude one, and nobody checks whether the headline result changes when the tree changes. Typical results of this kind are "diarrheic deer cluster apart from healthy deer" or "fertilizer shifts the soil community". The reason nobody checks is cost. Recomputing UniFrac over hundreds of alternative trees, each built and parsed from scratch, multiplies an already heavy computation.
We propose to make that check cheap. The plan is to put UniFrac on top of Phylo2Vec, which encodes a binary tree as a short integer vector. A small edit to that vector changes the tree in a local, predictable way. Because UniFrac is a sum of per-branch terms, a local tree edit should only require updating the few branches it touches, not recomputing everything. We would build this as an incremental UniFrac engine in Rust, called from Python and R. We would then use it to answer a question the field has not asked quantitatively: how often do published-style beta-diversity conclusions survive plausible alternative trees?
Core Claim
The claim has two parts. The first is algorithmic. On trees stored as Phylo2Vec vectors, UniFrac distance matrices can be updated under single-coordinate vector edits at a cost proportional to the number of branches whose descendant leaf set changes, rather than the full tree size. This makes UniFrac over an ensemble of trees, such as bootstrap trees or the visited states of a tree search, far cheaper than independent recomputation.
The second part is scientific. With that cost removed, tree uncertainty becomes something an analyst can measure and report for every result. Examples are the spread of each pairwise distance, the stability of ordination plots, and the fraction of trees under which a group difference test stays significant. We expect this to change conclusions mainly in fine-grained regimes: exact sequence variants and full-length reads, where trees are large and poorly resolved. Coarse clusters should be less affected.
The algorithmic part is only worth doing if the scientific part turns out true. The experiments are ordered so that we learn this early.
Where This Sits
The method we reuse is Phylo2Vec. Phylo2Vec: A vector representation of binary trees introduced the one-to-one map between binary tree shapes and integer vectors with $v_i \in \{0,\dots,2(i-1)\}$. It showed that hill-climbing in vector space finds near-optimal maximum-likelihood trees, for example in about 105 steps on the 29-taxon M501 dataset. The library paper, phylo2vec: a library for vector-based phylogenetic tree manipulation, moved the core to Rust with Python bindings through PyO3 and R bindings through Rcpp. It reports converting a 100,000-leaf tree in "roughly 10ms", against "over 1,000ms" for the earlier Numba version. It also adds branch lengths, leaf pruning and placement, and distance matrices between leaves.
Neither paper touches 16S data, sample abundance tables, or UniFrac. We build directly on this code and add the missing layer: sample-weighted, per-branch accumulators that are kept up to date as the vector changes.
The work that constrains our design is FrackyFrac: A Standalone UniFrac Calculator. It is a dependency-free compiled command-line UniFrac tool that reads tab-separated tables and Newick tree strings from disk. It reproduces host clustering on Earth Microbiome Project data. It is still "approximately 2x slower than SSU" on one core and "1.4x slower on eight cores". SSU is the compiled UniFrac core used inside QIIME2.
The lesson we take from FrackyFrac is that another fast single-tree UniFrac would not be a contribution. SSU already fills that role. We therefore do not compete on single-tree speed. We compete on cost per additional tree in an ensemble, which neither FrackyFrac nor SSU is designed to exploit.
The broader hybrid-architecture pattern provides the engineering template. That pattern is a high-level language for control flow over a compiled core that receives shared memory buffers rather than files, as described for Terra in deep learning and PySR in symbolic regression. Terra in particular warns about the costs of fine-grained crossings between the two layers. That warning shapes our interface: Python requests a whole batch of tree edits per call, never one branch at a time.
Two 16S papers motivate the scientific question. Alignment and clustering of phylogenetic markers - implications for microbial diversity studies shows how fragile upstream choices are. The choice of alignment tool alone explains 33% of the variance in clustering quality, and the distance threshold explains 56%. The paper studies clustering rather than trees. Still, it establishes that upstream choices in 16S pipelines move downstream conclusions, and the tree is exactly such a choice that no one varies.
Evaluation of 16S rRNA gene sequencing for species and strain-level microbiome analysis shows that the V4 sub-region "failed to classify 56% of sequences at the species level", while full-length reads resolve nearly all of them. It also shows that genomes carry several non-identical 16S copies. Both findings push studies toward more, finer leaves, which means larger and less certain trees.
Improved detection of disease-associated gut microbes using 16S sequence-based biomarkers points the other way: one can drop trees and group sequences by alignment variants. We treat that paper as a competing hypothesis that our experiments must take seriously, not as background.
The Mechanism
We use two definitions throughout. Let $l_b$ be the length of branch $b$. Let $p_A(b)$ be the fraction of sample $A$'s reads that fall in leaves below $b$. Weighted UniFrac between samples $A$ and $B$ is then
$$ W(A,B) = \frac{\sum_b l_b \,\lvert p_A(b) - p_B(b)\rvert}{\sum_b l_b \,(p_A(b) + p_B(b))}. $$
Unweighted UniFrac has the same form, with $p$ replaced by the 0/1 indicator of whether sample $A$ has any read below $b$.
Changing one coordinate $v_i$ detaches the clade that sequential construction hangs on leaf $i$ and reattaches it elsewhere. Only branches whose descendant set changes have their $p$ values altered. These are the branches on the path between the old and new attachment points, plus any branches whose topology the edit rewrites. The engine therefore keeps two things: per-branch per-sample abundance vectors, and per-pair numerator and denominator sums. For each changed branch it subtracts the old contribution and adds the new one.
The cost of one edit is roughly the number of changed branches times the number of sample pairs. A full recompute costs roughly the number of leaves times the number of sample pairs.
How local Phylo2Vec edits really are is not established. Changing an early coordinate can move a large clade, and the papers report no edit-locality statistics. We will measure the distribution of changed branches per edit on real 16S trees. For non-local edits we will fall back to a partial rebuild.
Two 16S-specific adaptations are needed. First, multifurcations and identical intragenomic copies are represented as binary splits with zero-length branches, since Phylo2Vec handles only binary trees. These branches contribute nothing to UniFrac, so the representation is exact. Second, abundance tables arrive from Python or R as contiguous arrays that the Rust side reads directly, with no tab-separated files in between.
Research Program
The program has three stages.
The first stage builds the engine and verifies its numbers. Single-tree UniFrac must match SSU to floating-point tolerance on Earth Microbiome Project subsets. Every incremental update must match a from-scratch recompute on the edited tree.
The second stage produces tree ensembles for real 16S datasets. These come from bootstrap resampling of alignment columns, from alternative aligners (motivated by the 33% alignment effect reported by Schloss and colleagues), and from the visited states of Phylo2Vec hill-climbing. Ensembles are ordered as walks of single-coordinate edits, so consecutive trees differ locally.
The third stage is the scientific analysis. For each dataset and design question we compute the ensemble distribution of three quantities. The first is the group-difference permutation test result (PERMANOVA, a permutation test of group separation in a distance matrix). The second is the first two principal coordinates. The third is the nearest-neighbor accuracy of host or phenotype labels.
The analysis will be run at three resolutions: 97% clusters, exact sequence variants, and full-length variants where available. This tests whether uncertainty matters mainly at fine resolution.
Baselines
The naive reference point is current practice. That means one tree, either from a reference database or built from scratch, with UniFrac computed once and its conclusions reported without any uncertainty. Every uncertainty statistic we report is measured against the answer this single tree gives. The proposal fails scientifically if that single-tree answer almost always falls inside a tight ensemble distribution.
The strongest existing method for computation is SSU, the compiled UniFrac core inside QIIME2. The file's only quantitative evidence is relative: FrackyFrac reports being about 2x slower than SSU single-core and 1.4x slower on eight cores (FrackyFrac). No absolute SSU runtime is reported on Lacuna for EMP.
We will run SSU on the same machine, thread count, and ensemble. Each tree will be a pre-written Newick file, and SSU will be called in a loop. File writing will be timed separately so that I/O is not charged unfairly against it. FrackyFrac is run the same way as a second compiled reference.
Beating SSU means lower total wall-clock time for an ensemble of $K$ trees at identical numerical output. We will also report the crossover $K$ below which SSU is simply faster. We expect SSU to win for $K=1$ and do not claim otherwise.
The strongest tree-free competitor for biological signal is sequence-based biomarkers. On the autism sibling-pair and obese/lean twin datasets, they report ROC-AUC of 0.64 and 0.84 respectively (Improved detection of disease-associated gut microbes using 16S sequence-based biomarkers). The area under the ROC curve measures how well a score separates two classes.
We will rerun these biomarkers with the same cross-validation folds, and we will feed classifiers from tree-based distances the same folds and tuning budget. Bray-Curtis dissimilarity, which ignores the tree, serves as the simplest tree-free comparison. Here we do not need to beat the AUC of 0.84. The claim is about whether tree-based conclusions are stable, and SBB results tell us whether tree-based features are worth stabilizing at all.
Two ablations isolate the key ingredient. The first ablation tests incrementality. It runs our engine in full-recompute mode on every tree, keeping the shared memory and Rust core. Any speed gain over this ablation comes from incremental updating alone.
The second ablation tests the vector encoding. It runs incremental updates on an ordinary pointer-based tree, with edits expressed as standard subtree prune-and-regraft moves. This tells us whether Phylo2Vec is needed, or whether any incremental UniFrac would do.
Why not just…?
Why not just run SSU on each bootstrap tree in parallel? This is the most serious threat. The ensemble is embarrassingly parallel, and a cluster can absorb a large multiplier. Our answer is empirical rather than rhetorical. If edits change few branches, incremental cost per tree should be a small fraction of a full recompute, and the advantage grows with the number of samples and leaves. If edits are mostly non-local, SSU-in-a-loop is the right tool.
The edit-locality measurement and the crossover-$K$ curve in the first experiment settle this. If SSU-in-a-loop wins at realistic $K$, we keep the scientific study and drop the engine as a contribution.
Why not just use Bray-Curtis and avoid trees entirely? If tree-free distances support the same conclusions as UniFrac, tree uncertainty is moot. FrackyFrac argues that Bray-Curtis ignores evolutionary relatedness. The SBB results show that tree-free sequence groupings can be strong predictors. So this is an open empirical question, not a settled one.
We compare Bray-Curtis, SBB, single-tree UniFrac, and ensemble UniFrac on the same tasks. If Bray-Curtis matches UniFrac everywhere, that is a useful negative result, and it reduces the case for trees in 16S studies.
Why not just write it in Python with Numba? The phylo2vec developers already did, and they report the Numba version at "over 1,000ms" against "roughly 10ms" for Rust on 100,000-leaf conversions (phylo2vec library). Incremental updating is branchy, pointer-heavy code of the kind where that gap appeared. We will not repeat that comparison beyond a sanity check.
Why not just cluster into 97% units so trees are small and stable? That hides the uncertainty rather than measuring it. Clustering itself is unstable: thresholds explain 56% of clustering variation, and 49 true species were inflated to 56 units (Alignment and clustering of phylogenetic markers). Clustering also discards species-level resolution (Evaluation of 16S rRNA gene sequencing for species and strain-level microbiome analysis). The cross-resolution analysis shows directly whether coarse clustering buys stability, and at what cost in signal.
Proposed Experiments
The first decisive check is edit locality and speed. We build trees for Earth Microbiome Project subsets at the scale FrackyFrac benchmarked, up to 2,000 samples. We record the distribution of changed branches per Phylo2Vec edit and plot total ensemble time against $K$ for our engine, both ablations, SSU, and FrackyFrac.
The success threshold is a sizeable per-tree saving over the full-recompute ablation at $K$ in the hundreds. Every incremental distance matrix must also match SSU.
The second check is ground truth. We use the 36-species mock community from Johnson and colleagues and the simulated 1,677-sequence, 49-species set from Schloss and colleagues, where true relationships are known. On these we test whether ensemble UniFrac intervals contain the UniFrac computed on the true tree more reliably than single estimated trees do. We compare V4 against full-length reads.
The third check, which decides the scientific contribution, applies the ensemble analysis to real phenotype datasets. These are the autism and obesity cohorts, American Gut body-site data, and Earth Microbiome Project host types.
For each dataset we report the fraction of ensemble trees under which the group-difference test stays significant, and how far ordination plots move across trees. We also report nearest-neighbor phenotype accuracy, which we set against Bray-Curtis and against SBB's reported AUCs of 0.64 and 0.84.
The proposal's scientific claim holds if a non-trivial share of conclusions at sequence-variant or full-length resolution change across plausible trees, while conclusions at 97% resolution do not. It fails if all conclusions are tree-stable. In that case the honest output is a published stability audit stating that single-tree UniFrac is safe, which would still be worth knowing.
References
- Phylo2Vec: A vector representation of binary trees
- phylo2vec: a library for vector-based phylogenetic tree manipulation
- FrackyFrac: A Standalone UniFrac Calculator
- Terra: Imperative-Symbolic Co-Execution of Imperative Deep Learning Programs
- Review of PySR: high-performance symbolic regression in Python and Julia
- Alignment and clustering of phylogenetic markers - implications for microbial diversity studies
- Evaluation of 16S rRNA gene sequencing for species and strain-level microbiome analysis
- Improved detection of disease-associated gut microbes using 16S sequence-based biomarkers