Abstract for the talk at 26.02.2013 (15:15 h)
VW-SeminarMaribel Hernandez Rosales (Interdisziplinäres Zentrum für Bioinformatik, Universität Leipzig)
From Orthology Relations through Cographs and Event-labeled Gene Trees to Species Trees
Orthology detection is an important problem in comparative and evolutionary genomics. It is of interest to understand how much information about the gene tree, the species tree, and their reconciliation is already contained in the orthology relation on the underlying set of genes. Building upon Boecker and Dress results on symbolic ultrametrics and on Semple and Steel algorithms on supertrees, I will present here new characterizations for symbolic ultrametrics and how these are related to cographs, graphs that do not contain P4s. As a result we can obtain an event-labeled gene tree, a tree whose internal nodes are labeled as speciation or duplication events. I will also show that a species tree S exists for a event-labeled gene tree T if and only if, S displays all rooted triples of T that have three distinct species as their leaves and are rooted in a speciation event. A valid reconciliation map can be then found in polynomial time.