Adaptive Fast Convergence - Towards Optimal Reconstruction Guarantees for Phylogenetic Trees
Speaker: Ilan Gronau, CS Department Technion Israel Institute of Technology
Date: Wednesday, October 1 2008
Time: 11:30AM to 1:00AM
Refreshments: 11:00AM
Location: Stata Center 32-G575
Host: Bonnie Berger & Peter Clote, MIT - BC
Contact: Patrice Macaluso, 617.253.3037, macaluso@csail.mit.edu
Relevant URL: http://www-math.mit.edu/compbiosem/
Phylogenetic reconstruction is the task of determining the structure (topology) of the evolutionary tree over a given set of species. This is typically done using an alignment of genetic sequences extracted from the species in the set. Reconstruction of evolutionary trees is a central task in comparative genomics which is used as a basic step in many applications. One of the main challenges in this field is to design reconstruction algorithms which provide a good tradeoff between the length of input sequences and the extent of accurate reconstruction.
In the past decade much attention has been focused on studying fast converging reconstruction algorithms, which guarantee correct reconstruction of any tree from sequences of (asymptotically) minimal length. However, when the tree in question contains even a single short edge, the sequence length required by these methods might be too long for any practical purpose. Short edges are prevalent in phylogenies and are notoriously hard to reconstruct. They result from two subsequent speciation events which are separated by little evolutionary change. A famous example is the human-chimp-gorilla separation.
In this talk we present a novel fast converging algorithm which is the first one to guarantee correct reconstruction of every edge in the 'true' tree whose weight exceeds a certain weight threshold. In a sense, giving up on edges which are too short to be reliably reconstructed allows us to reconstruct all sufficiently long edges. This way, as the input sequences grow longer, we are able to reconstruct more edges of the evolutionary tree. This property (which we propose to term adaptive fast convergence), together with the low running time of our algorithm (quadratic in the number of species), make it a natural candidate for dealing with very large and complex phylogenies.
This is joint work with Sagi Snir and my advisor Prof. Shlomo Moran.
See other events that are part of Bioinformatics Seminar Series 2008
See other events happening in October 2008
