Evolution is a stochastic process which operates on the DNA of
species. The evolutionary process leaves tell-tale signs in the DNA
which can be used to construct phylogenies, or evolutionary trees, for
a set of species. So called Maximum Likelyhood Estimations (MLE)
methods seek the evolutionary tree which is most likely to have
produced the DNA under consideration. While these methods are widely
accepted and intellectually satisfying, they are computationally
intractable. We offer a simple polynomial time algorithm for finding
a tree which approaches the most likely tree, complementing our result
with a lower bound on how well any algorithm can do, no matter its
computational complexity. We thus show that our simple approach is
close to optimal in terms of the amount of DNA needed to find a "good"
tree.
Joint work with Sampath Kannan.