Attempting to recognize a tree inside a  network is a fundamental undertaking in evolutionary analysis. Therefore, the notion of tree-based  phylogenetic networks, which was introduced by Francis and Steel, has attracted much attention of researchers in the area of theoretical biology in the last few years. Tree-based networks can be viewed as a natural generalization of rooted binary phylogenetic trees because they are merely trees with additional arcs, and in defining those networks, a certain kind of spanning trees called subdivision trees plays an essential role . In this paper, we provide a structural characterization of tree-based networks that furnishes efficient algorithms for solving the following problems in linear time (for enumeration, in linear delay)  : given a rooted binary phylogenetic network N, 1) determine whether or not N is tree-based and find a subdivision tree  if there exists any (decision/search problem); 2) compute the number of subdivision trees of N (counting problem); 3) list all subdivision trees of N (enumeration problem); and 4) find a subdivision tree to maximize or minimize a prescribed objective function (optimization problem). Our structural result settles numerous questions including the complexity of the problem of counting subdivision trees that was left open in the paper of Francis and Steel, and also provides short proofs of different known results from a unifying point of view. The results in this paper still hold for a certain class of non-binary networks. Some applications and further research directions are also mentioned .
Attempting to recognize a tree inside a phylogenetic network is a fundamental undertaking in evolutionary analysis. Therefore, the concept of " tree-based " phylogenetic networks, which was introduced by Francis and Steel, has attracted much attention of theoretical biologists in the last few years. In this context, spanning trees of a certain kind called "subdivision trees" play an essential role and there are many important computational problems about them, whose time complexity is still unclear. Against this backdrop, the present paper aims to provide a graph theoretical framework for solving different problems on subdivision trees in a simple and unified manner. To this end, we focus on a structure called the maximal zig-zag trail decomposition that is inherent in any rooted binary phylogenetic network N and prove a structure theorem that characterizes the collection of all subdivision trees of N. Our theorem does not only imply and unify various results in the literature but also yield linear time (for enumeration, linear delay) algorithms for the following problems : given a rooted binary phylogenetic network N, 1) determine whether or not N has a subdivision tree and find one if there exists any (decision/search problem); 2) compute the number of subdivision trees of N (counting problem); 3) list all subdivision trees of N (enumeration problem); and 4) find a subdivision tree to maximize or minimize a prescribed objective function (optimization problem). Importantly, the results and algorithms in this paper still hold true for some non-binary phylogenetic networks and this generalization gives a partial answer to an open question from Pons, Semple, and Steel. We also mention some statistical applications and further research directions .
A
phylogenetic
R
notion of
concept of "
A
"
R
researchers in the area of theoretical biology
theoretical biologists
R
Tree-based networks can be viewed as a natural generalization of rooted binary phylogenetic trees because they are merely trees with additional arcs, and in defining those networks,
In this context, spanning trees of
R
of spanning trees called subdivision trees plays
called "subdivision trees" play
R
. In this paper, we provide a structural characterization of tree-based networks that furnishes efficient algorithms for solving the following problems in
and there are many important computational problems about them, whose time complexity is still unclear. Against this backdrop, the present paper aims to provide a graph theoretical framework for solving different problems on subdivision trees in a simple and unified manner. To this end, we focus on a structure called the maximal zig-zag trail decomposition that is inherent in any rooted binary phylogenetic network N and prove a structure theorem that characterizes the collection of all subdivision trees of N. Our theorem does not only imply and unify various results in the literature but also yield
D
in
A
algorithms for the following problems
R
is tree-based and find
has
A
and find one
R
Our structural result settles numerous questions including the complexity of the problem of counting subdivision trees that was left open in the paper of Francis and Steel, and also provides short proofs of different known results from a unifying point of view. The results
Importantly, the results and algorithms
R
for a certain class of
true for some
R
networks. Some
phylogenetic networks and this generalization gives a partial answer to an open question from Pons, Semple, and Steel. We also mention some statistical
D
are also mentioned