Huber, Katharina T., van Iersel, Leo, Janssen, Remie, Jones, Mark, Moulton, Vincent ORCID: https://orcid.org/0000-0001-9371-6435, Murakami, Yuki and Semple, Charles (2024) Orienting undirected phylogenetic networks. Journal of Computer and System Sciences, 140. ISSN 0022-0000
Preview |
PDF (1-s2.0-S0022000023000855-main)
- Published Version
Available under License Creative Commons Attribution. Download (868kB) | Preview |
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.
Item Type: | Article |
---|---|
Uncontrolled Keywords: | phylogenetic network,graph orientation,graph algorithm,fixed-parameter tractability,polynomial-time algorithm,characterization,computational biology,phylogenetics |
Faculty \ School: | Faculty of Science > School of Computing Sciences |
UEA Research Groups: | Faculty of Science > Research Groups > Computational Biology Faculty of Science > Research Groups > Norwich Epidemiology Centre Faculty of Medicine and Health Sciences > Research Groups > Norwich Epidemiology Centre |
Depositing User: | LivePure Connector |
Date Deposited: | 28 Sep 2023 09:30 |
Last Modified: | 17 Oct 2023 00:43 |
URI: | https://ueaeprints.uea.ac.uk/id/eprint/93120 |
DOI: | 10.1016/j.jcss.2023.103480 |
Downloads
Downloads per month over past year
Actions (login required)
View Item |