| Date |
December 10, 2012 |
| Speaker |
Dr. Sylvain Guillemot, MTA SZTAKI, Hungary
|
| Title |
Constructing agreement supertrees
|
| Abstract |
Phylogenetic trees are commonly used by biologists to represent the
evolutionary history of a set of species. In this context, it is often
desirable to merge several phylogenetic trees in a single tree, called
a supertree. The input trees generally come from different phylogenetic
studies, and involve different, but overlapping, set of species. In
this talk, I will focus on a particular notion of supertree, called an
agreement supertree. I will show that this notion, although somewhat
restrictive, has nice algorithmic properties. First, I will present a
polynomial-time algorithm to decide the existence of a rooted agreement
supertree. Second, I will discuss relaxations of the problem, where the
goal is to correct a (small) number of errors in the input trees to
obtain agreement. The results will be tied together by a common theme
of identifying small obstructions in case of disagreement.
|
|
アブストラクト