Paper List

期刊: ArXiv Preprint
发布日期: 2026-03-10
BioinformaticsComputational Biology

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

Hebrew University of Jerusalem | Weizmann Institute of Science | Tel Aviv University

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

30秒速读

IN SHORT: This paper addresses the computational bottleneck in reconstructing species trees from thousands of species and multiple genes by introducing a scalable spectral divide-and-conquer framework that maintains accuracy while dramatically reducing runtime.

核心创新

  • Methodology Introduces a spectral graph theory-based partitioning method using the Fiedler eigenvector of averaged gene Laplacian matrices to recursively divide species into biologically meaningful clans.
  • Theory Provides theoretical guarantees of asymptotic consistency under the Multispecies Coalescent (MSC) model and finite-sample bounds for accurate partitioning.
  • Methodology Develops a deterministic merging strategy based on outgroup rooting that avoids NP-hard optimization problems common in supertree methods.

主要结论

  • SDSR combined with CA-ML achieves up to 10-fold faster runtime on 200-species datasets with 100 genes while maintaining comparable accuracy to full-data CA-ML.
  • The algorithm provides O(m²) complexity for partitioning/merging steps and reduces the dominant reconstruction term from O(Km²n) to O(Kτmn), where τ is the threshold size.
  • Theoretical analysis proves SDSR is asymptotically consistent under the MSC model with infinite genes, and partitions species into disjoint clans of the true species tree.
研究空白： Current divide-and-conquer methods for large-scale phylogenetics either lack theoretical guarantees under standard models like MSC, rely on random partitioning that may not reflect biological structure, or require solving NP-hard merging problems that limit scalability and accuracy.

摘要: 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.