Species Trees from Gene Trees Despite a High Rate of Lateral Genetic Transfer: A Tight Bound

摘要

Reconstructing the tree of life from molecular sequences is a fundamental problem in computational biology. Modern data sets often contain a large number of genes which can complicate the reconstruction problem due to the fact that different genes may undergo different evolutionary histories. This is the case in particular in the presence of lateral genetic transfer (LGT), whereby a gene is inherited from a distant species rather than an immediate ancestor. Such an event produces a gene tree which is distinct from (but related to) the species phylogeny. In previous work, a stochastic model of LGT was introduced and it was shown that the species phylogeny can be reconstructed from gene trees despite surprisingly high rates of LGT. Both lower and upper bounds on this rate were obtained, but a large gap remained. Here we close this gap, up to a constant. Specifically, we show that the species phylogeny can be reconstructed perfectly even when each edge of the tree has a constant probability of being the location of an LGT event. Our new reconstruction algorithm builds the tree recursively from the leaves. We also provide a matching bound in the negative direction (up to a constant).