Abstract
A binary phylogenetic network may or may not be obtainable from a tree by the addition of directed edges (arcs) between tree arcs. 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.
| Original language | English |
|---|---|
| Pages (from-to) | 768-777 |
| Number of pages | 10 |
| Journal | Systematic Biology |
| Volume | 64 |
| Issue number | 5 |
| DOIs | |
| Publication status | Published - 2015 |
Open Access - Access Right Statement
© The Author(s) 2015. Published by Oxford University Press on behalf of the Society of Systematic Biologists. This is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted reuse, distribution, and reproduction in any medium, provided the original work is properly cited.Keywords
- algorithms
- biomathematics
- genetic transformation
- phylogeny