Fast Algorithms for Analyzing Large Collections of Evolutionary Trees
November 4, 2010
2:30 p.m.
Tiffani Williams
Abstract
Phylogenetic trees are family trees that represent the relationships between a group of organisms, or taxa. The most popular techniques for reconstructing phylogenetic trees intelligently navigate an exponentially-sized tree space by solving NP-hard optimization problems that best hypothesize the evolutionary history for a given set of taxa (or organisms). Instead of reconstructing a single tree, these heuristics often return tens of thousands to hundreds of thousands of trees that represent equally-plausible hypotheses for how the taxa of interest evolved from a common ancestor.
In this talk, I will present a variety of techniques for analyzing these large tree collections returned from a phylogenetic analysis. First, I will discuss Phlash, the fastest algorithm for computing distances between sets of phylogenetic trees. Afterward, I will discuss how to use these tree distances to study properties of phylogenetic heuristics such as convergence.