Optimal Phylogenetic Reconstruction from Sampled Quartets

Quartet Reconstruction, the task of recovering a single phylogenetic tree from smaller trees on four species called quartets, is a well-studied problem in theoretical computer science with farreaching connections to statistics, graph theory and biology. Given a random sample containing m noisy quartets, labeled according to an unknown ground-truth tree T on n taxa, we want to learn the tree structure of T with small generalization error, i.e., to output a tree T that is close to T in terms of quartet distance and can predict the classification of unseen quartets. Unfortunately, the empirical risk minimizer corresponds to the NP-hard problem of finding a tree that maximizes agreements with the sampled quartets, and earlier works in approximation algorithms gave (1 -ϵ)-approximation schemes (PTAS) for dense instances with m = Θ(n 4 ) quartets, or for m = Θ(n 2 log n) quartets randomly sampled from T .

Prior to our work, it was unknown how many samples are information-theoretically required to learn the tree, and whether there is an efficient reconstruction algorithm. We present optimal results for reconstructing an unknown phylogenetic tree T from a random sample of m = Θ(n) quartets, potentially corrupted under the standard Random Classification Noise (RCN) model. This matches the Ω(n) lower bound required for any meaningful tree reconstruction, as for m = o(n), large parts of T cannot be recovered, and exact tree reconstruction (ϵ = 0) requires Ω(n 3 ) quartets. Our contribution is twofold: first, we give a tree reconstruction algorithm that, not only achieves a (1 -ϵ)-approximation for Quartet Reconstruction, but most importantly recovers a tree close to T in quartet distance; second, we show a new Θ(n) bound on the Natarajan dimension of phylogenies (an analog of VC dimension in multiclass classification), which may be of independent interest. Coupled together, these imply that our reconstructed tree T will generalize well to unseen quartets. Our analysis relies on a new Quartet-based Embedding and Detection (QED) procedure, that repeatedly identifies and removes well-clustered subtrees from the (unknown) ground-truth T via semidefinite programming.