Limits...
Which Phylogenetic Networks are Merely Trees with Additional Arcs?

Francis AR, Steel M - Syst. Biol. (2015)

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.

View Article: PubMed Central - PubMed

Affiliation: Centre for Research in Mathematics, School of Computing, Engineering and Mathematics, University of Western Sydney, Australia;

Show MeSH

Related in: MedlinePlus

A tree-based network on three leaves in which all possible trees on three leaves could be the base.
© Copyright Policy - creative-commons
Related In: Results  -  Collection

License
getmorefigures.php?uid=PMC4538883&req=5

Figure 1: A tree-based network on three leaves in which all possible trees on three leaves could be the base.

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.


Which Phylogenetic Networks are Merely Trees with Additional Arcs?

Francis AR, Steel M - Syst. Biol. (2015)

A tree-based network on three leaves in which all possible trees on three leaves could be the base.
© Copyright Policy - creative-commons
Related In: Results  -  Collection

License
Show All Figures
getmorefigures.php?uid=PMC4538883&req=5

Figure 1: A tree-based network on three leaves in which all possible trees on three leaves could be the base.
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.

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.

View Article: PubMed Central - PubMed

Affiliation: Centre for Research in Mathematics, School of Computing, Engineering and Mathematics, University of Western Sydney, Australia;

Show MeSH
Related in: MedlinePlus