Inferring Phylogenies via LCA-distances

Ilan Gronau
CS, Technion

Inferring the evolutionary history of a given set of species is one of the most fundamental problems in Computational Biology. Our research specifically deals with algorithms which reconstruct phylogenetic trees from pairwise distances. One of the major issues addressed in this approach is the ability to reconstruct the correct tree given noisy distance estimates.
In the first part of the talk, we present a new approach for reconstructing phylogenetic trees using distances to LCAs (Least Common Ancestors). This approach leads to a family of very simple and efficient algorithms called Deepest LCA Neighbor-Joining (DLCA in short). We present a technique which leads to an optimal running time of $O(n^2)$. This technique is also used to speed up the running time of well-known clustering algorithms such as UPGMA. In the second part, we discuss the performance of these algorithms on noisy distance estimates. Specifically, we compare these algorithms to Saitou & Nei's famous neighbor joining algorithm (AKA NJ) both through their performance guarantees and through actual experiments on simulated phylogenetic data.
The talk touches upon core issues in distance-based phylogenetic reconstruction and does not assume any prior biological/mathematical knowledge. It is based on two papers, which can be found at www.cs.technion.ac.il/~ilangr: "Neighbor joining algorithms for inferring phylogenies via LCA-distances" and "Optimal Implementations of UPGMA and Other Common Clustering Algorithms".