Orienting undirected phylogenetic networks

DOI10.1016/J.JCSS.2023.103480MaRDI QIDQ6142597zbMATH OpenFDO

Authors

Publication date 4 January 2024

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1906.07430

zbMATH Keywords

characterizationcomputational biologyfixed-parameter tractabilitygraph algorithmgraph orientationphylogenetic networkphylogeneticspolynomial-time algorithm

Mathematics Subject Classification ID

Computer science (68-XX)

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.

Cites work

• A class of phylogenetic networks reconstructable from ancestral profiles
• Colorings and orientations of graphs
• Degree-constrained graph orientation: maximum satisfaction and minimum violation
• Exploring the tiers of rooted phylogenetic network space using tail moves
• On cherry-picking and network containment
• On unrooted and root-uncertain variants of several well-known phylogenetic network problems
• Phylogenetic networks with every embedded phylogenetic tree a base tree
• Reconstructing tree-child networks from reticulate-edge-deleted subnetworks
• Research in Computational Molecular Biology
• Tree-based unrooted phylogenetic networks
• Uprooted phylogenetic networks

Cited in

(3)

• On the existence of funneled orientations for classes of rooted phylogenetic networks
• Arboreal networks and their underlying trees
• Orientability of undirected phylogenetic networks to a desired class: practical algorithms and application to tree-child orientation

This page was built for publication: Orienting undirected phylogenetic networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6142597)