The Spectral Partition

Reconstructing the tree of species from gene sequences hits two walls. First, gene trees disagree with the species tree — different genes follow different histories because of incomplete lineage sorting. Second, the algorithms don’t scale — exact methods are exponential in the number of species.

Reshef et al. solve the scaling problem with a spectral divide-and-conquer. Instead of building the entire tree at once, the algorithm recursively partitions species into smaller groups using spectral methods — eigendecomposition of a distance matrix derived from gene trees. Each partition splits the species where the spectral gap is largest, which corresponds to the deepest separation in evolutionary history. Build subtrees for each group, then merge.

The through-claim: the spectral gap identifies the most informative split. The eigenstructure of the pairwise distance matrix encodes the hierarchical clustering structure of the tree. The largest spectral gap corresponds to the deepest divergence — the split that separates the most anciently diverged groups. By recursing on this structure, the algorithm processes the easiest (most signal-rich) splits first and pushes the hardest (most noise-contaminated) splits to smaller subproblems where they’re tractable.

The method is provably correct under the multispecies coalescent model and achieves 10x speedups combined with standard methods, without sacrificing accuracy. The speedup comes from reducing the problem size at each recursion level — spectral partitioning costs O(n²) per level, and the number of levels is logarithmic in the number of species.

Split where the signal is strongest. Recurse where it’s weakest.