Which Phylogenetic Networks are Merely Trees with Additional Arcs?
Bottom Line: Here, we establish a precise and easily tested criterion (based on "2-SAT") that efficiently determines whether or not any given network can be realized in this way.Moreover, the proof provides a polynomial-time algorithm for finding one or more trees (when they exist) on which the network can be based.A number of interesting consequences are presented as corollaries; these lead to some further relevant questions and observations, which we outline in the conclusion.
Affiliation: Centre for Research in Mathematics, School of Computing, Engineering and Mathematics, University of Western Sydney, Australia;Show MeSH
Related in: MedlinePlus
Mentions: Starting from any rooted binary phylogenetic tree, if we sequentially add one or more arcs (directed edges), each placed from a point on one tree arc to a point on another tree arc, then provided no directed cycles arise, we obtain a rooted binary phylogenetic network. Many classes of phylogenetic networks can be generated in this way, even if, at first, their descriptions seem somewhat different. For instance, networks based on hybridization can be drawn by adding two arcs from points on tree arcs to meet at a new hybridization vertex, with a further arc leading to a hybrid offspring; however, an equivalent network can be produced by starting with a phylogenetic tree on the same leaf set and simply adding arcs just between tree arcs (Fig. 1 provides an example).Figure 1.
Affiliation: Centre for Research in Mathematics, School of Computing, Engineering and Mathematics, University of Western Sydney, Australia;