SDSR: A Spectral Divide-and-Conquer Approach for Species Tree Reconstruction

Ortal Reshef; Ofer Glassman; Or Zuk; Yariv Aizenbud; Boaz Nadler; Ariel Jaffe

q-bio.PEMar 10, 2026

SDSR: A Spectral Divide-and-Conquer Approach for Species Tree Reconstruction

Authors: Ortal Reshef, Ofer Glassman, Or Zuk, Yariv Aizenbud, Boaz Nadler, Ariel Jaffe

Organizations: Hebrew University of Jerusalem · Department of Statistics and Data Science, Hebrew University of Jerusalem · Weizmann Institute of Science · Department of Computer Science and Applied Mathematics, Weizmann Institute of Science ·

Abstract

Recovering a tree that represents the evolutionary history of a group of species is a key task in phylogenetics. Performing this task using sequence data from multiple genetic markers poses two key challenges. The first is the discordance between the evolutionary history of individual genes and that of the species. The second challenge is computational, as contemporary studies involve thousands of species. Here we present SDSR, a scalable divide-and-conquer approach for species tree reconstruction based on spectral graph theory. The algorithm recursively partitions the species into subsets until their sizes are below a given threshold. The trees of these subsets are reconstructed by a user-chosen species tree algorithm. Finally, these subtrees are merged to form the full tree. On the theoretical front, we derive recovery guarantees for SDSR, under the multispecies coalescent (MSC) model. We also perform a runtime complexity analysis. We show that SDSR, when combined with a species tree reconstruction algorithm as a subroutine, yields substantial runtime savings as compared to applying the same algorithm on the full data. Empirically, we evaluate SDSR on synthetic benchmark datasets with incomplete lineage sorting and horizontal gene transfer. In accordance with our theoretical analysis, the simulations show that combining SDSR with common species tree methods, such as CA-ML or ASTRAL, yields up to 10-fold faster runtimes. In addition, SDSR achieves a comparable tree reconstruction accuracy to that obtained by applying these methods on the full data.

Figures & tables

Figure 1: Discordance between a species tree and a gene tree due to one HGT event (orange) and one ILS event (purple). In HGT, a segment of genetic material is transferred horizontally from a donor species $A$ , to a receptor species $C$ [ 25 , 16 ] . In ILS, the divergence event associated with species $E$ occur at an earlier time in the gene tree than in the species tree [ 20 ] .

Figure 2: SDSR workflow: (A) Compute a graph based on the genes’ similarity matrices, where nodes represent species. The nodes are colored according to the partitions $C_{1},C_{2}$ from step 1. (B) Form subsets $\tilde{C}_{1}$ and $\tilde{C}_{2}$ by adding outgroups $O_{2},O_{1}$ to $C_{1}$ and $C_{2}$ , respectively, and reconstruct subtrees $\tilde{\T}_{1}$ and $\tilde{\T}_{2}$ . (C) The roots of the two trees are set to $h_{1}$ and $h_{2}$ , the nodes adjacent to the outgroups $O_{2}$ and $O_{1}$ . The outgroup nodes are removed, and the subtrees are merged by connecting $h_{1}$ to $h_{2}$ .

Figure 3: Example of a species tree (blue) and a realization of a gene tree (black). The vertical line is the time axis starting at $\tau=0$ with the current species. The coalescence times in the species tree are $\tau_{ij}$ and $\tau_{ijk}$ , whereas those in the gene tree are $\tau_{jk}^{g}$ and $\tau_{ijk}^{g}$ . In this example, the gene tree and the species tree have different topologies.

Figure 4: Partition accuracy as a function of the number of genes, on the $10{,}000$ -species datasets. Results shown for the first partition (left) and all partitions (right). The accuracy of the first partition is measured by the Rand Index similarity score to the most similar partition in the ground-truth species tree. For internal partitions, we compared the obtained partition to the most similar partition in the corresponding subtree.

Figure 5: Accuracy and runtime as a function of the number of genes for the $200$ -species datasets. The upper panel presents the nRF distance between the estimated and ground truth species tree of CA-ML and SDSR using CA-ML as a subroutine. The upper right panel presents the runtime. The bottom panels present the accuracy and runtime of ASTRAL and SDSR using ASTRAL as a subroutine.

Figure 6: Comparison to uDance [ 7 ] on the $10{,}000$ -species datasets. The left panel shows the nRF distance between the estimated and ground-truth species tree as a function of the number of genes. Each marker represents the median runtime and nRF distance. The label on each marker denotes the median number of species in the reconstructed trees. The right panel shows the runtime of the two methods.

Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 7: A tree $\T$ and its corresponding similarity matrix $S$ . On the right - the matrix block partitions used in the proof of lemma 1

Panel of Figure 8 — Figure 8: Left: Illustration of a quartet tree. For part (b) of our proof, we show that if $A$ and $B$ are not clans, $S(A,B)$ is not rank 1. Right: key property II: The random variable $\Delta_{i,k}+D(h_{i,j},r)$ stochastically dominates $\Delta_{i,j}$ .

Figure 9: Accuracy of the first partition as a function of the number of genes, on the $50$ -species datasets (left) and the $200$ - species datasets (right). The accuracy is measured by the Rand Index similarity score between the partition obtained by the Fiedler vector and the most similar partition in the ground-truth species tree.

Figure 10: Accuracy of the first partition, based on distance matrices, as a function of the number of genes. (left) $50$ - species dataset; (right) $200$ - species dataset. The accuracy is measured by the Rand Index similarity score between the partition obtained by the Fiedler vector and the most similar partition in the ground-truth species tree.

Figure 11: Results for the $50$ species datasets with a single SDSR iteration: The left panels show the nRF distance between the estimated and ground-truth species trees as a function of the number of genes, for the dataset with only ILS (upper panel) and ILS+HGT (bottom panel). The right panels show the runtime in minutes.

Figure 12: Results for the $200$ species datasets with a single SDSR iteration: (left panel) nRF distance between the estimated and ground-truth species trees as a function of the number of genes; (right panel) runtime in minutes.

Figure 13: Results for the $200$ species datasets - multiple SDSR iterations on a single CPU: (left panel) nRF distance between the estimated and ground-truth species trees as a function of the number of genes; (right panel) runtime in minutes.

Phylogenetic Inference

Phylogenetic inference reconstructs evolutionary relationships and divergence histories from genetic, morphological, linguistic, or other inherited traits.

See all 12 papers

Approximating SPR Distance Between Phylogenetic Trees with Graph Neural Networks
Jul 17, 2026Renata Martins Castanheira, Miguel Bugalho, Cátia VazGraph Neural Networks Phylogenetic Inference
ISEL – Instituto Superior de Engenharia de Lisboa, Instituto Politécnico de Lisboa, Portugal · ALGORITMI Research Center/CCPM, Portugal · INESC-ID Lisboa, Portugal
Deep Generative Models for Phylogenetic Inference with Complex Evolutionary Processes
Oct 13, 2026Ethan Baron, Alan N. Amin, Andrew Gordon WilsonPhylogenetic Inference Generative Modeling
New York University
Tree-Conditioned Edit Flows for Ancestral Sequence Reconstruction
May 5, 2026Emil Sharafutdinov, Ingemar AndréFlow Matching Phylogenetic Inference
Center for Molecular Protein Science Lund University Box 124, 221 00 Lund

Jul 17, 2026J/K move · Enter open · S save

Approximating SPR Distance Between Phylogenetic Trees with Graph Neural Networks

Renata Martins Castanheira, Miguel Bugalho, Cátia Vaz

ISEL – Instituto Superior de Engenharia de Lisboa, Instituto Politécnico de Lisboa, Portugal · ALGORITMI Research Center/CCPM, Portugal · INESC-ID Lisboa, Portugal

Graph Neural Networks Phylogenetic Inference

Open paper AskPDF arXiv

Comparing phylogenetic tree topologies is essential for understanding epidemic dynamics, yet biologically meaningful distances such as the Subtree Prune and Regraft (SPR) distance are NP-hard to compute and intractable on large datasets. We investigate whether a Graph Neural Network (GNN) can approximate SPR distances in near-constant time per comparison after training. Our contributions are fourfold. First, we build and publicly release a dataset of 864 phylogenetic trees inferred with UPGMA and Neighbor-Joining over four bacterial species, spanning up to 9{,}500 isolates, together with 388 labelled tree pairs. Second, we establish a reproducible pre-processing pipeline including midpoint re-rooting, which reduces tree depth and supplies the rooting required for exact distance computation and for the model's root-based features. Third, we validate the supervision target: on small trees, where exact SPR is tractable, the unrooted phangorn::SPR.dist heuristic correlates almost perfectly with the exact rooted distance computed by rspr (Pearson

0.98

0.99

), making it an excellent monotonic surrogate. Lastly, we train a Siamese Graph Isomorphism Network (GIN) regressor. In-distribution, i.e., held-out trees from the same species and size range as training, it explains roughly 87--90% of the variance (

R^2 \approx 0.87

on a held-out split;

0.90 \pm 0.19

under stratified cross-validation), with about four times lower error than a mean-predictor baseline, and shows partial transfer to unseen species (

R^2 \approx 0.37

). Its main limitation is extrapolation to trees larger than those seen in training, where accuracy collapses. The released dataset and the validated heuristic versus exact relationship provide a reproducible basis for scaling learned SPR approximation.

Abstract

Phylogenetic Inference

Explore similar work

Approximating SPR Distance Between Phylogenetic Trees with Graph Neural Networks

Deep Generative Models for Phylogenetic Inference with Complex Evolutionary Processes

Tree-Conditioned Edit Flows for Ancestral Sequence Reconstruction