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

Three networks with no strong temporal ordering relative to any valid support tree. Network (i) fails to be acyclic (and so is technically not even a binary phylogenetic network), but Networks (ii) and (iii) are acyclic (and so have a weak temporal ordering).
© Copyright Policy - creative-commons
Related In: Results  -  Collection

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

Figure 6: Three networks with no strong temporal ordering relative to any valid support tree. Network (i) fails to be acyclic (and so is technically not even a binary phylogenetic network), but Networks (ii) and (iii) are acyclic (and so have a weak temporal ordering).

Mentions: Notice that the (weak) temporal ordering condition in itself implies that must be acyclic, since if is a directed cycle in a tree-based network, then some pair of adjacent vertices in the cycle—say and —forms an arc of the support tree and so . However, since the -values of the vertices in the remainder of the path from to is non-decreasing (by (i) and (ii)′), this would imply that , which is a contradiction. Figure 6 illustrates three tree-based networks that have no strong temporal ordering relative to any valid support tree.


Which Phylogenetic Networks are Merely Trees with Additional Arcs?

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

Three networks with no strong temporal ordering relative to any valid support tree. Network (i) fails to be acyclic (and so is technically not even a binary phylogenetic network), but Networks (ii) and (iii) are acyclic (and so have a weak temporal ordering).
© Copyright Policy - creative-commons
Related In: Results  -  Collection

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

Figure 6: Three networks with no strong temporal ordering relative to any valid support tree. Network (i) fails to be acyclic (and so is technically not even a binary phylogenetic network), but Networks (ii) and (iii) are acyclic (and so have a weak temporal ordering).
Mentions: Notice that the (weak) temporal ordering condition in itself implies that must be acyclic, since if is a directed cycle in a tree-based network, then some pair of adjacent vertices in the cycle—say and —forms an arc of the support tree and so . However, since the -values of the vertices in the remainder of the path from to is non-decreasing (by (i) and (ii)′), this would imply that , which is a contradiction. Figure 6 illustrates three tree-based networks that have no strong temporal ordering relative to any valid support tree.

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