### Inhalt des Dokuments

## 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. [1]

_14/