BEGIN:VCALENDAR
VERSION:2.0
X-WR-CALNAME:Bioinformatics Seminar Series 2008 Events
BEGIN:VEVENT
DTSTART;TZID=US/Eastern:20081001T113000
DTEND;TZID=US/Eastern:20081001T010000
URL;VALUE=URI:http://www.csail.mit.edu/events/eventcalendar/calendar.php?show=event&id=1995
SUMMARY:Adaptive Fast Convergence - Towards Optimal Reconstruction Guarantees for Phylogenetic Trees
LOCATION:Stata Center 32-G575
DESCRIPTION:Series: Bioinformatics Seminar Series 2008\nSpeaker:  Ilan Gronau\, CS Department Technion Israel Institute of Technology\nHost: Bonnie Berger & Peter Clote\, MIT -  BC\nContact: Patrice Macaluso\, 617.253.3037\, macaluso@csail.mit.edu\nRefreshment Time: 11:00AM\nRelevant URL: http://www-math.mit.edu/compbiosem/\nPhylogenetic 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.\n\nIn 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. \n\nIn 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.\n\nThis is joint work with Sagi Snir and my advisor Prof. Shlomo Moran.\n
END:VEVENT
END:VCALENDAR