  Lateral gene transfer (LGT) is a common mechanism of non-vertical evolution
where genetic material is transferred between two more or less distantly
related organisms. It is particularly common in bacteria where it contributes
to adaptive evolution with important medical implications. In evolutionary
studies, LGT has been shown to create widespread discordance between gene trees
as genomes become mosaics of gene histories. In particular, the Tree of Life
has been questioned as an appropriate representation of bacterial evolutionary
history. Nevertheless a common hypothesis is that prokaryotic evolution is
primarily tree-like, but that the underlying trend is obscured by LGT.
Extensive empirical work has sought to extract a common tree-like signal from
conflicting gene trees. Here we give a probabilistic perspective on the problem
of recovering the tree-like trend despite LGT. Under a model of randomly
distributed LGT, we show that the species phylogeny can be reconstructed even
in the presence of surprisingly many (almost linear number of) LGT events per
gene tree. Our results, which are optimal up to logarithmic factors, are based
on the analysis of a robust, computationally efficient reconstruction method
and provides insight into the design of such methods. Finally we show that our
results have implications for the discovery of highways of gene sharing.
