Print Email Facebook Twitter Orienting undirected phylogenetic networks Title Orienting undirected phylogenetic networks Author Huber, Katharina T. (University of East Anglia) van Iersel, L.J.J. (TU Delft Discrete Mathematics and Optimization) Janssen, R. (TU Delft Discrete Mathematics and Optimization) Jones, M.E.L. (TU Delft Discrete Mathematics and Optimization) Moulton, V.L. (TU Delft Discrete Mathematics and Optimization; University of East Anglia) Murakami, Yukihiro (TU Delft Discrete Mathematics and Optimization) Semple, Charles (University of Canterbury) Date 2024 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. Subject CharacterizationComputational biologyFixed-parameter tractabilityGraph algorithmGraph orientationPhylogenetic networkPhylogeneticsPolynomial-time algorithm To reference this document use: http://resolver.tudelft.nl/uuid:c7ecc30c-ae74-427f-a26d-628a78fc092c DOI https://doi.org/10.1016/j.jcss.2023.103480 ISSN 0022-0000 Source Journal of Computer and System Sciences, 140 Part of collection Institutional Repository Document type journal article Rights © 2024 Katharina T. Huber, L.J.J. van Iersel, R. Janssen, M.E.L. Jones, V.L. Moulton, Yukihiro Murakami, Charles Semple Files PDF 1_s2.0_S0022000023000855_main.pdf 966.78 KB Close viewer /islandora/object/uuid:c7ecc30c-ae74-427f-a26d-628a78fc092c/datastream/OBJ/view