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

(i) A network from Marcussen et al. (2014) showing three ancient hybridization events in the evolution of bread wheat. Corollary 3 terminates at (ii) to show that the network is tree-based. Finding a particular support tree requires selecting a label for an unlabeled arc, extending the labeling using the rules ()′ and ()′ repeatedly, and continuing this process. In this example, the six unlabeled arcs consist of three pairs, with the arcs in each pair incoming to one of the three vertices of in-degree 2. Assigning a label ( or ) to an arc in one pair determines the assignment for the other arc in that pair but does not force any further arc assignments. Thus three independent assignments can be made for each pair, leading to  choices in total. For the particular choice shown in (iii) we obtain the support tree  shown in (iv) and thereby the tree-based representation shown in (v). In this example, the eight rooted binary phylogenetic trees that the network can be based on are all distinct.
© Copyright Policy - creative-commons
Related In: Results  -  Collection

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

Figure 4: (i) A network from Marcussen et al. (2014) showing three ancient hybridization events in the evolution of bread wheat. Corollary 3 terminates at (ii) to show that the network is tree-based. Finding a particular support tree requires selecting a label for an unlabeled arc, extending the labeling using the rules ()′ and ()′ repeatedly, and continuing this process. In this example, the six unlabeled arcs consist of three pairs, with the arcs in each pair incoming to one of the three vertices of in-degree 2. Assigning a label ( or ) to an arc in one pair determines the assignment for the other arc in that pair but does not force any further arc assignments. Thus three independent assignments can be made for each pair, leading to choices in total. For the particular choice shown in (iii) we obtain the support tree shown in (iv) and thereby the tree-based representation shown in (v). In this example, the eight rooted binary phylogenetic trees that the network can be based on are all distinct.

Mentions: Figure 4(i) shows a binary phylogenetic network on five leaves and three reticulations (vertices of in-degree 2). This network is essentially equivalent to the one shown in Figure 3 of Marcussen et al. (2014), under the taxon labeling a=Triticum uartu, b=Triticum turgidum, c=Triticum aestivum, d=Aegilops tauschii, e=Aegilops speltoides.Figure 4.


Which Phylogenetic Networks are Merely Trees with Additional Arcs?

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

(i) A network from Marcussen et al. (2014) showing three ancient hybridization events in the evolution of bread wheat. Corollary 3 terminates at (ii) to show that the network is tree-based. Finding a particular support tree requires selecting a label for an unlabeled arc, extending the labeling using the rules ()′ and ()′ repeatedly, and continuing this process. In this example, the six unlabeled arcs consist of three pairs, with the arcs in each pair incoming to one of the three vertices of in-degree 2. Assigning a label ( or ) to an arc in one pair determines the assignment for the other arc in that pair but does not force any further arc assignments. Thus three independent assignments can be made for each pair, leading to  choices in total. For the particular choice shown in (iii) we obtain the support tree  shown in (iv) and thereby the tree-based representation shown in (v). In this example, the eight rooted binary phylogenetic trees that the network can be based on are all distinct.
© Copyright Policy - creative-commons
Related In: Results  -  Collection

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

Figure 4: (i) A network from Marcussen et al. (2014) showing three ancient hybridization events in the evolution of bread wheat. Corollary 3 terminates at (ii) to show that the network is tree-based. Finding a particular support tree requires selecting a label for an unlabeled arc, extending the labeling using the rules ()′ and ()′ repeatedly, and continuing this process. In this example, the six unlabeled arcs consist of three pairs, with the arcs in each pair incoming to one of the three vertices of in-degree 2. Assigning a label ( or ) to an arc in one pair determines the assignment for the other arc in that pair but does not force any further arc assignments. Thus three independent assignments can be made for each pair, leading to choices in total. For the particular choice shown in (iii) we obtain the support tree shown in (iv) and thereby the tree-based representation shown in (v). In this example, the eight rooted binary phylogenetic trees that the network can be based on are all distinct.
Mentions: Figure 4(i) shows a binary phylogenetic network on five leaves and three reticulations (vertices of in-degree 2). This network is essentially equivalent to the one shown in Figure 3 of Marcussen et al. (2014), under the taxon labeling a=Triticum uartu, b=Triticum turgidum, c=Triticum aestivum, d=Aegilops tauschii, e=Aegilops speltoides.Figure 4.

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