Phylogenetic trees, also known as evolutionary trees, model the evolution of biological species or genes from a common ancestor. Reconstructing evolutionary trees is a fundamental research problem in biology, with applications to protein structure and function prediction, pathway detection, sequence alignment, drug design, etc. However, the reconstruction of very large evolutionary trees is exceedingly difficult; not only are the major optimization problems NP-hard, but large real datasets of interest to the biological community can take years of analysis without being solved exactly. Furthermore, while polynomial time methods for phylogeny reconstruction exist, our research shows that the standard approaches (including the popular Neighbor Joining method) may have "large sequence length requirements".

In this talk I will present a new algorithmic approach, called the "Disk-Covering Method (DCM)", for reconstructing phylogenies. DCM is designed to be used in conjunction with a base phylogenetic method. Our simulation studies show that DCM, combined with the popular polynomial time method Neighbor Joining, produces much more accurate trees than Neighbor Joining by itself. Furthermore, we can prove that DCM-NJ requires only polynomial length sequences for accurate reconstruction of the true tree with high probability.