CSAIL Event Calendar

Using Computational Tools for Piecing Together Small Trees into the Large Tree of Life

The reconstruction of evolutionary trees is a fundamental task in Biology. The increasing amount of available genomic sequences over thousands of taxa, gave rise to the task of large scale phylogenetic reconstruction. Since accurate reconstruction is limited to few dozens of taxa, the supertree approach, aims at accurately reconstructing small trees over overlapping taxa sets and subsequently amalgamate these trees into a tree over the full taxa set. Perhaps the simplest version of this task that is still widely applicable, yet quite challenging, is quartet based reconstruction. This problem lies at the root of many tree reconstruction methods and theoretical as well as experimental results have been reported. Nevertheless, fundamental problems such as dealing with conflicting quartet trees or even with arbitrary congruent quartet trees remain problematic.

In a series of works we have developed a graph theoretically based approach for the supertree task. Our approach is based on a divide and conquer algorithm where our divide step uses a semi- definite programming (SDP) formulation of MaxCut in a graph representing relationships between the organisms. We devised an extremely fast SDP-like heuristic that allows us to extend the input data from several thousands of quartet trees over few dozens of species to tens of millions of quartet trees over thousands of species. These results are promising in the realm of large scale phylogenetic reconstruction.

Based on works with Satish Rao and Raphy Yuster. The talk is self-contained and requires no prior knowledge in Biology.

See other events happening in August 2012