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) A network that is not tree-based, even though it satisfies the antichain-to-leaf property. That this network fails to be tree based can be verified by applying Corollary 3; starting with the arcs in  labeled  (shown in bold in (b)) and applying the conditions ()′ and ()′ repeatedly, we are forced to label both of the arcs outgoing from  by , and at the next step ()′ would assign one of these two arcs a second label .
© Copyright Policy - creative-commons
Related In: Results  -  Collection

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

Figure 3: (a) A network that is not tree-based, even though it satisfies the antichain-to-leaf property. That this network fails to be tree based can be verified by applying Corollary 3; starting with the arcs in labeled (shown in bold in (b)) and applying the conditions ()′ and ()′ repeatedly, we are forced to label both of the arcs outgoing from by , and at the next step ()′ would assign one of these two arcs a second label .

Mentions: It might seem plausible that the antichain-to-leaf property is also a sufficient condition for a network to be tree-based. Alas, this is not the case, and Fig. 3 shows a particular case where the antichain-to-leaf property holds, yet the network is not tree-based.Figure 3.


Which Phylogenetic Networks are Merely Trees with Additional Arcs?

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

(a) A network that is not tree-based, even though it satisfies the antichain-to-leaf property. That this network fails to be tree based can be verified by applying Corollary 3; starting with the arcs in  labeled  (shown in bold in (b)) and applying the conditions ()′ and ()′ repeatedly, we are forced to label both of the arcs outgoing from  by , and at the next step ()′ would assign one of these two arcs a second label .
© Copyright Policy - creative-commons
Related In: Results  -  Collection

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

Figure 3: (a) A network that is not tree-based, even though it satisfies the antichain-to-leaf property. That this network fails to be tree based can be verified by applying Corollary 3; starting with the arcs in labeled (shown in bold in (b)) and applying the conditions ()′ and ()′ repeatedly, we are forced to label both of the arcs outgoing from by , and at the next step ()′ would assign one of these two arcs a second label .
Mentions: It might seem plausible that the antichain-to-leaf property is also a sufficient condition for a network to be tree-based. Alas, this is not the case, and Fig. 3 shows a particular case where the antichain-to-leaf property holds, yet the network is not tree-based.Figure 3.

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