Invited Session Mon.2.H 2033

Monday, 13:15 - 14:45 h, Room: H 2033

Cluster 12: Life sciences & healthcare [...]

Evolution and phylogenetics


Chair: Leo van Iersel



Monday, 13:15 - 13:40 h, Room: H 2033, Talk 1

Mareike Fischer
When sets of species make an evolutionary tree unique


In a recent study, Sanderson and Steel defined and characterized so-called phylogenetically decisive sets of species sets. A set is called phylogenetically decisive if regardless of the evolutionary trees chosen for each of its species sets, as long as these trees are compatible with one another, their supertree is always unique. It remained unknown whether the decision if a set of species sets is phylogenetically decisive can always be made in polynomial time. This question was one of the "Penny Ante'' questions of the Annual New Zealand Phylogenetics Meeting 2012. In my talk, I will explain phylogenetic decisiveness and demonstrate a new mathematical characterization, which then leads to a polynomial time algorithm - both for the (simpler) case of rooted trees as well as for the (more complicated) unrooted case.



Monday, 13:45 - 14:10 h, Room: H 2033, Talk 2

Steven Kelk
Cycle killer … {} qu'est-ce que c'est? On the comparative approximability of hybridization number and directed feedback vertex set

Coauthors: Nela Lekic, Simone Linz, Celine Scornavacca, Leen Stougie, Leo van Iersel


We show that the problem of computing the hybridization number of two rooted binary phylogenetic
trees on the same set of taxa X has a constant factor polynomial-time approximation if and only if the problem of
computing a minimum-size feedback vertex set in a directed graph (DFVS) has a constant factor polynomial-time
approximation. The latter problem, which asks for a minimum number of vertices to be removed from a directed
graph to transform it into a directed acyclic graph, is one of the problems in Karp's seminal 1972 list of 21 NP-complete
problems. Despite considerable attention from the combinatorial optimization community, it remains to
this day unknown whether a constant factor polynomial-time approximation exists for DFVS. Our result thus places
the (in)approximability of hybridization number in a much broader complexity context. On the positive side, we use results from the DFVS literature to give an O({log}  r {log  log}  r) approximation for the hybridization number where r is the
correct value.



Monday, 14:15 - 14:40 h, Room: H 2033, Talk 3

Celine Scornavacca
Constructing minimal phylogenetic networks from softwired clusters is fixed parameter tractable

Coauthor: Steven Kelk


Here we show that, given a set of clusters C on a set of taxa X, where |X|=n, it is possible to determine in
time f(k) · poly(n) whether there exists a level- ≤ k network (i.e. a network where each biconnected component has reticulation number at most k) that represents all the clusters in C in the softwired sense, and if so to construct such a network. This extends a polynomial time result from Kelk et al (On the elusiveness of clusters, IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2012).
By generalizing the concept of "level-k generator'' to general networks, we then extend this fixed parameter tractability result to the problem where k refers not to the level but to the reticulation number of the whole network.


  There are three major facts that should be watched out for in all payday loans in the United States. But at the same time, it acts only with sexual arousal. Viagra has a number of advantages in comparison with injections in the sexual organ or other procedures aimed at treatment of impotency.