Adaptive fast convergence - towards optimal reconstruction guarantees for Phylogenetic trees

22 mins 30 secs, 83.26 MB, iPod Video 480x360, 25.0 fps, 44100 Hz, 505.23 kbits/sec

Share this media item:

Embed this media item:

<iframe width="_width_" height="_height_" src="https://sms.cam.ac.uk/media/488/embed" frameborder="0" scrolling="no" allowfullscreen></iframe>

Choose size:

About this item

Available Formats

About this item

Description:	Gronau, I (Technion) Monday 17 December 2007, 14:20-14:40 PLGw03 - Future Directions in Phylogenetic Methods and Models

Created:

2008-01-10 14:56

Collection:

Phylogenetics

Publisher:

Isaac Newton Institute

Gronau, I

Language:

eng (English)

Credits:

Author:	Gronau, I
Producer:	Steve Greenham


Abstract:	One of the central challenges in phylogenetics is to be able to reliably resolve as much of the topology of the evolutionary tree from short taxon-sequences. In the past decade much attention has been focused on studying fast converging reconstruction algorithms, which guarantee (w.h.p.) correct reconstruction of the entire tree from sequences of near-minimal length (assuming some accepted model of sequence evolution along the tree). The major drawback of these methods is that when the sequences are too short to correctly reconstruct the tree in its entirety, they do not provide any reconstruction guarantee for sufficiently long edges. Specifically, the presence of some very short edges in the model tree may prevent these algorithms from reconstructing even edges of moderate length. In this talk we present a stronger reconstruction guarantee called "adaptive fast convergence", which provides guarantees for the correct reconstruction of all sufficiently long edges of the original tree. We then present a general technique, which (unlike previous reconstruction techniques) employs dynamic edge-contraction during the reconstruction of the tree. We conclude by demonstrating how this technique is used to achieve adaptive fast convergence. Related Links * http://www.cs.technion.ac.il/~ilangr/papers/short_edges_SODA08.pdf - online version of conference paper

Abstract:

One of the central challenges in phylogenetics is to be able to reliably resolve as much of the topology of the evolutionary tree from short taxon-sequences. In the past decade much attention has been focused on studying fast converging reconstruction algorithms, which guarantee (w.h.p.) correct reconstruction of the entire tree from sequences of near-minimal length (assuming some accepted model of sequence evolution along the tree). The major drawback of these methods is that when the sequences are too short to correctly reconstruct the tree in its entirety, they do not provide any reconstruction guarantee for sufficiently long edges. Specifically, the presence of some very short edges in the model tree may prevent these algorithms from reconstructing even edges of moderate length.

In this talk we present a stronger reconstruction guarantee called "adaptive fast convergence", which provides guarantees for the correct reconstruction of all sufficiently long edges of the original tree. We then present a general technique, which (unlike previous reconstruction techniques) employs dynamic edge-contraction during the reconstruction of the tree. We conclude by demonstrating how this technique is used to achieve adaptive fast convergence.

Related Links

* http://www.cs.technion.ac.il/~ilangr/papers/short_edges_SODA08.pdf - online version of conference paper

Available Formats

Format	Quality	Bitrate	Size
MPEG-4 Video	480x360	1.84 Mbits/sec	309.88 MB	View	Download
WebM	480x360	567.78 kbits/sec	93.22 MB	View	Download
Flash Video	480x360	804.31 kbits/sec	132.55 MB	View	Download
iPod Video *	480x360	505.23 kbits/sec	83.26 MB	View	Download
QuickTime	384x288	847.57 kbits/sec	139.68 MB	View	Download
MP3	44100 Hz	125.01 kbits/sec	20.39 MB	Listen	Download
Windows Media Video		477.7 kbits/sec	78.72 MB	View	Download
Auto	(Allows browser to choose a format it supports)