Folding and unfolding phylogenetic trees and networks.
Phylogenetic networks are rooted, labelled directed acyclic graphswhich are commonly used to represent reticulate evolution. There is a close relationship between phylogenetic networks and multi-labelled trees (MUL-trees). Indeed, any phylogenetic network N can be "unfolded" to obtain a MUL-tree U(N) and, conversely, a MUL-tree T can in certain circumstances be "folded" to obtain aphylogenetic network F(T) that exhibits T. In this paper, we study properties of the operations U and F in more detail. In particular, we introduce the class of stable networks, phylogenetic networks N for which F(U(N)) is isomorphic to N, characterise such networks, and show that they are related to the well-known class of tree-sibling networks. We also explore how the concept of displaying a tree in a network N can be related to displaying the tree in the MUL-tree U(N). To do this, we develop aphylogenetic analogue of graph fibrations. This allows us to view U(N) as the analogue of the universal cover of a digraph, and to establish a close connection between displaying trees in U(N) and reconciling phylogenetic trees with networks.
School of Computing Sciences, University of East Anglia, Norwich, NR4 7TJ, UK.
Katharina T
KT
Huber
School of Computing Sciences, University of East Anglia, Norwich, NR4 7TJ, UK.
Vincent
V
Moulton
School of Mathematics and Statistics, University of Canterbury, Christchurch, New Zealand.
Mike
M
Steel
School of Computing Sciences, University of East Anglia, Norwich, NR4 7TJ, UK. taoyang.wu@gmail.com.
Taoyang
T
Wu
D000465:Algorithms; D002965:Classification / Q000379:methods*; D008957:Models, Genetic; D010802:Phylogeny
Graph fibrations; Multi-labelled trees; Phylogenetic networks; Tree and network reconciliation; Universal cover of a digraph