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 MajorAlgorithms*Classification*Phylogeny*MinorComputer Simulation/standards Related in: MedlinePlus © Copyright Policy - creative-commons Related In: Results  -  Collection License getmorefigures.php?uid=PMC4538883&req=5 .flowplayer { width: px; height: px; } Figure 5: A network that is based on a tree (left) and displays (right), but is not based on the tree . Notice that in the right-hand network, vertex requires a linking arc to be attached to another linking arc. Mentions: It is clear that if is a tree-based network, and is based on , then must display , since we can just delete the linking arcs, and suppress any resulting vertices of in-degree and out-degree equal to 1. However, it is possible for a tree-based network to display the tree but fail to be based on (Fig. 5). In other words, the notion of a network being based on a tree is stronger than simply displaying the tree.Figure 5.

Which Phylogenetic Networks are Merely Trees with Additional Arcs?

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

Related In: Results  -  Collection

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

Figure 5: A network that is based on a tree (left) and displays (right), but is not based on the tree . Notice that in the right-hand network, vertex requires a linking arc to be attached to another linking arc.
Mentions: It is clear that if is a tree-based network, and is based on , then must display , since we can just delete the linking arcs, and suppress any resulting vertices of in-degree and out-degree equal to 1. However, it is possible for a tree-based network to display the tree but fail to be based on (Fig. 5). In other words, the notion of a network being based on a tree is stronger than simply displaying the tree.Figure 5.

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