Print Email Facebook Twitter On Unrooted and Root-Uncertain Variants of Several Well-Known Phylogenetic Network Problems Title On Unrooted and Root-Uncertain Variants of Several Well-Known Phylogenetic Network Problems Author van Iersel, L.J.J. (TU Delft Discrete Mathematics and Optimization) Kelk, Steven (Universiteit Maastricht) Stamoulis, G. (Universiteit Maastricht) Stougie, Leen (Vrije Universiteit Amsterdam) Boes, Olivier (Universiteit Maastricht) Date 2017 Abstract The hybridization number problem requires us to embed a set of binary rooted phylogenetic trees into a binary rooted phylogenetic network such that the number of nodes with indegree two is minimized. However, from a biological point of view accurately inferring the root location in a phylogenetic tree is notoriously difficult and poor root placement can artificially inflate the hybridization number. To this end we study a number of relaxed variants of this problem. We start by showing that the fundamental problem of determining whether an unrooted phylogenetic network displays (i.e. embeds) an unrooted phylogenetic tree, is NP-hard. On the positive side we show that this problem is FPT in reticulation number. In the rooted case the corresponding FPT result is trivial, but here we require more subtle argumentation. Next we show that the hybridization number problem for unrooted networks (when given two unrooted trees) is equivalent to the problem of computing the tree bisection and reconnect distance of the two unrooted trees. In the third part of the paper we consider the “root uncertain” variant of hybridization number. Here we are free to choose the root location in each of a set of unrooted input trees such that the hybridization number of the resulting rooted trees is minimized. On the negative side we show that this problem is APX-hard. On the positive side, we show that the problem is FPT in the hybridization number, via kernelization, for any number of input trees. Subject APX-hardnessBinary treesFixed parameter tractabilityKernelizationNP-completenessPhylogenetic networks To reference this document use: http://resolver.tudelft.nl/uuid:9e861e55-5b1a-4032-bb78-b49b747ad7a3 DOI https://doi.org/10.1007/s00453-017-0366-5 ISSN 0178-4617 Source Algorithmica, 1-30 Bibliographical note Accepted Author Manuscript Part of collection Institutional Repository Document type journal article Rights © 2017 L.J.J. van Iersel, Steven Kelk, G. Stamoulis, Leen Stougie, Olivier Boes Files PDF 10.1007_s00453_017_0366_5.pdf 881.05 KB Close viewer /islandora/object/uuid:9e861e55-5b1a-4032-bb78-b49b747ad7a3/datastream/OBJ/view