Orienting undirected phylogenetic networks

Katharina T. Huber, Leo van Iersel*, Remie Janssen, Mark Jones, Vincent Moulton, Yukihiro Murakami, Charles Semple

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

1 Citation (Scopus)
53 Downloads (Pure)

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.

Original languageEnglish
Article number103480
JournalJournal of Computer and System Sciences
Volume140
DOIs
Publication statusPublished - 2024

Keywords

  • Characterization
  • Computational biology
  • Fixed-parameter tractability
  • Graph algorithm
  • Graph orientation
  • Phylogenetic network
  • Phylogenetics
  • Polynomial-time algorithm

Fingerprint

Dive into the research topics of 'Orienting undirected phylogenetic networks'. Together they form a unique fingerprint.

Cite this