Planar rooted phylogenetic networks

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)
15 Downloads (Pure)

Abstract

A rooted phylogenetic network is a directed acyclic graph with a single root, whose sinks correspond to a set of species. As such networks are useful for representing the evolution of species that have undergone reticulate evolution, there has been great interest in developing the theory behind and algorithms for constructing them. However, unlike evolutionary trees, these networks can be highly non-planar, which can make them difficult to visualise and interpret. Here we investigate properties of planar rooted phylogenetic networks and algorithms for deciding whether or not rooted networks have certain special planarity properties. In particular, we introduce three natural subclasses of planar rooted phylogenetic networks and show that they form a hierarchy. In addition, for the well-known level-k networks, we show that level-1, -2, -3 networks are always outer, terminal, and upward planar, respectively, and that level-4 networks are not necessarily planar. Finally, we show that a regular network is terminal planar if and only if it is pyramidal. Our results make use of the highly developed field of planar digraphs, and we believe that the link between phylogenetic networks and planar graphs should prove useful in future for developing new approaches to both construct and visualise phylogenetic networks.

Original languageEnglish
Pages (from-to)1289-1297
Number of pages9
JournalIEEE/ACM Transactions on Computational Biology and Bioinformatics
Volume20
Issue number2
Early online date23 Jun 2022
DOIs
Publication statusPublished - Mar 2023

Keywords

  • Phylogenetic network
  • level-network
  • planar digraph
  • pyramid
  • regular network
  • upward planar

Cite this