Orienting undirected phylogenetic networks
Katharina T Huber (University of East Anglia)
Leo van Iersel (TU Delft - Discrete Mathematics and Optimization)
Remie Janssen (TU Delft - Discrete Mathematics and Optimization)
Mark Jones (TU Delft - Discrete Mathematics and Optimization)
V.L. Moulton (University of East Anglia, TU Delft - Discrete Mathematics and Optimization)
Yukihiro Murakami (TU Delft - Discrete Mathematics and Optimization)
Charles Semple (University of Canterbury)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
This paper studies the relationship between undirected (unrooted) and directed (rooted) phylogenetic networks. We describe a polynomial-time algorithm for deciding whether an undirected nonbinary phylogenetic network, given the locations of the root and reticulation vertices, can be oriented as a directed nonbinary phylogenetic network. Moreover, we characterize when this is possible and show that, in such instances, the resulting directed nonbinary phylogenetic network is unique. In addition, without being given the location of the root and the reticulation vertices, we describe an algorithm for deciding whether an undirected binary phylogenetic network N can be oriented as a directed binary phylogenetic network of a certain class. The algorithm is fixed-parameter tractable (FPT) when the parameter is the level of N and is applicable to classes of directed phylogenetic networks that satisfy certain conditions. As an example, we show that the well-studied class of binary tree-child networks satisfies these conditions.
help_outline