The Taub Faculty of Computer Science Events and Talks

The reconstruction of evolutionary trees is a fundamental task in Biology. The exponentially increasing amount of available genomic date over thousands of genes and species, gave rise to the task of combining all this data for the sake of constructing a phylogeny (evolutionary tree) depicting the evolution of life on earth along several billions of years.

Since accurate reconstruction is limited to few dozens of species, the supertree approach, aims at accurately reconstructing small trees over overlapping species sets and subsequently amalgamate these trees into a single tree over the full set of species.

A quartet tree, a tree over four species, is the simplest piece of phylogenetic information. Hence, the supertree problem when all input trees are quartet trees, is the simplest version of this task that is still widely applicable, yet quite challenging. This problem lies at the root of many tree reconstruction methods and theoretical as well as experimental results have been reported. Nevertheless, the problem of dealing with conflicting quartet set or even with arbitrary congruent set remained open where the best known approximation ratio is $\frac{1}{3}$, obtained naively by a random tree.

In a series of works we have developed a graph theoretically based approach for the quartet 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 species. We could show several approximation bounds using this approach for a wide variety of inputs, that improves substantially the $\frac{1}{3}$ bound for general inputs. We also derived negative results regarding the information encompassed in quartet subsets, over the full quartet set.

Based on joint works with Satish Rao, Raphy Yuster, and Noga Alon.

The talk is self-contained and requires no prior knowledge in Biology.