TU Berlin

Research Group Algorithmics and Computational ComplexityTalk 29.09.2014

isti-logo

Page Content

to Navigation

Getting Real With Hybridization Networks (But Not Too Much)

Prof. Norbert Zeh (Dalhousie University)

Hybridization networks can be used to represent the evolutionary history of a set of species if this history includes ancestor species that are hybrids of more than one parent.  Such hybridization events are common in the evolution of plants and can occur even for mammals.  The clues to detect such events can be found in the discrepancies between gene trees: phylogenetic trees constructed by analyzing different genes of extant species.  Following the common assumption that hybridization events, while possible, are rare, the goal is to construct a network with the minimum number of hybridization events that is consistent with all the gene trees, that is, contains each of these trees as a subgraph.  This problem is NP-hard even for two binary gene trees and is known to be fixed-parameter tractable for an arbitrary but fixed number of trees.  For two trees, Whidden, Beiko, and Zeh (SICOMP 2013) developed an algorithm with running time O(3.18^k * n), where k is the number of hybridization events, while even for three trees, the best known running time was O(f(k) * poly(n)), where f(k) = (k!)^2 * 50^k (Kelk and Scornavacca, Algorithmica 2012).  This raised the question whether a running time of O(c^k * poly(n)), for some constant c, is achievable for more than two trees.  The result in this talk answers this question in the affirmative for three trees using a novel approach to guess the structure of the network without using too many guesses.  The techniques used to obtain this result for three trees extend to more than three trees with the exception of a single key lemma.  The talk includes a brief discussion of how it might be possible to extend the result to more than three trees by using an alternate strategy that does not rely on this particular lemma.

This is joint work with Leo van Iersel (CWI Amsterdam), Nela Lekic and Steven Kelk (Maastricht University), and Chris Whidden (Fred Hutchinson Cancer Research Center, Seattle).

Date
Speaker
Location
Language
29.09.2014
11:00
Norbert Zeh
TEL 512
english

Back to the research colloquium site.

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe