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

arXiv: https://arxiv.org/abs/2603.10215 · HTML: https://mlsanity.com/paper/2603.10215/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 72 references that are in the map.
- First posted on arXiv 10 Mar 2026.

## Builds on (most cited first, 5 of 5)

- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Unsupervised Ensemble Learning with Dependent Classifiers](https://mlsanity.com/paper/1510.05830/) (2015)
- [Estimating the Accuracies of Multiple Classifiers Without Labeled Data](https://mlsanity.com/paper/1407.7644/) (2014)
- [Spectral neighbor joining for reconstruction of latent tree models](https://mlsanity.com/paper/2002.12547/) (2020)
- [Spectral Top-Down Recovery of Latent Tree Models](https://mlsanity.com/paper/2102.13276/) (2021)

## Abstract (arXiv)

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.