Which Phylogenetic Networks are Merely Trees with Additional Arcs?
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.
Affiliation: Centre for Research in Mathematics, School of Computing, Engineering and Mathematics, University of Western Sydney, Australia;Show MeSH
Related in: MedlinePlus
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.
Affiliation: Centre for Research in Mathematics, School of Computing, Engineering and Mathematics, University of Western Sydney, Australia;