TY - JOUR
T1 - Orienting undirected phylogenetic networks
AU - Huber, Katharina T.
AU - van Iersel, Leo
AU - Janssen, Remie
AU - Jones, Mark
AU - Moulton, Vincent
AU - Murakami, Yukihiro
AU - Semple, Charles
PY - 2024
Y1 - 2024
N2 - 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.
AB - 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.
KW - Characterization
KW - Computational biology
KW - Fixed-parameter tractability
KW - Graph algorithm
KW - Graph orientation
KW - Phylogenetic network
KW - Phylogenetics
KW - Polynomial-time algorithm
UR - http://www.scopus.com/inward/record.url?scp=85173580438&partnerID=8YFLogxK
U2 - 10.1016/j.jcss.2023.103480
DO - 10.1016/j.jcss.2023.103480
M3 - Article
AN - SCOPUS:85173580438
SN - 0022-0000
VL - 140
JO - Journal of Computer and System Sciences
JF - Journal of Computer and System Sciences
M1 - 103480
ER -