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
view more