Combinatorial Algorithms for Constructing Phylogenetic Supertrees

Jesper Jansson (INRIA, Lille, France)

An important objective in phylogenetics is to develop good methods for merging a given collection of phylogenetic trees on overlapping sets of taxa into a single supertree so that no (or as little as possible) branching information is lost. Ideally, the resulting supertree can then be used to deduce evolutionary relationships between taxa which do not occur together in any one of the input trees. Furthermore, although computationally expensive methods for constructing reliable phylogenetic trees are infeasible for large sets of taxa, they can be applied to obtain highly accurate trees for smaller, overlapping subsets of the taxa which may then be merged using computationally less intense techniques.

In this talk, I will describe some simple combinatorial algorithms for constructing rooted phylogenetic supertrees from so-called rooted triplets (phylogenetic trees with exactly three leaves each), discuss a number of recent extensions of these algorithms, and present a few interesting related open problems.

back to EIDMA Seminar Combinatorial Theory announcements