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

Some pertinent examples of binary networks, one tree-based and two not: Examples (i) (from van Iersel 2013) and (ii) are not tree-based, while Example (iii) is tree-based, despite first appearances. One can verify that (i) and (ii) are not tree-based by using the algorithm given in Corollary 3, although for these two examples, Proposition 2 suffices (see text for details). Example (iii) is tree-based via the tree arcs  and ; in this case  and  are linking arcs.
© Copyright Policy - creative-commons
Related In: Results  -  Collection

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

Figure 2: Some pertinent examples of binary networks, one tree-based and two not: Examples (i) (from van Iersel 2013) and (ii) are not tree-based, while Example (iii) is tree-based, despite first appearances. One can verify that (i) and (ii) are not tree-based by using the algorithm given in Corollary 3, although for these two examples, Proposition 2 suffices (see text for details). Example (iii) is tree-based via the tree arcs and ; in this case and are linking arcs.

Mentions: (iv) Not all binary phylogenetic networks are tree-based, one example (from van Iersel 2013) is shown in Figure 2(i) and another in Figure 2(ii). On the other hand, networks that are tree-based may not appear so because of the way they are drawn, an example being Figure 2(iii).


Which Phylogenetic Networks are Merely Trees with Additional Arcs?

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

Some pertinent examples of binary networks, one tree-based and two not: Examples (i) (from van Iersel 2013) and (ii) are not tree-based, while Example (iii) is tree-based, despite first appearances. One can verify that (i) and (ii) are not tree-based by using the algorithm given in Corollary 3, although for these two examples, Proposition 2 suffices (see text for details). Example (iii) is tree-based via the tree arcs  and ; in this case  and  are linking arcs.
© Copyright Policy - creative-commons
Related In: Results  -  Collection

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

Figure 2: Some pertinent examples of binary networks, one tree-based and two not: Examples (i) (from van Iersel 2013) and (ii) are not tree-based, while Example (iii) is tree-based, despite first appearances. One can verify that (i) and (ii) are not tree-based by using the algorithm given in Corollary 3, although for these two examples, Proposition 2 suffices (see text for details). Example (iii) is tree-based via the tree arcs and ; in this case and are linking arcs.
Mentions: (iv) Not all binary phylogenetic networks are tree-based, one example (from van Iersel 2013) is shown in Figure 2(i) and another in Figure 2(ii). On the other hand, networks that are tree-based may not appear so because of the way they are drawn, an example being Figure 2(iii).

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