Locating a Phylogenetic Tree in a Reticulation-Visible Network in Quadratic Time
In phylogenetics, phylogenetic trees are rooted binary trees, whereas phylogenetic networks are rooted arbitrary acyclic digraphs. Edges are directed away from the root and leaves are uniquely labeled with taxa in phylogenetic networks. For the purpose of validating evolutionary models, biologists check whether or not a phylogenetic tree is contained in a phylogenetic network on the same taxa. This tree containment problem is known to be NP-complete. A phylogenetic network is reticulation-visible if every reticulation node separates the root of the network from some leaves. We answer an open problem by proving that the problem is solvable in quadratic time for reticulation-visible networks. The key tool used in our answer is a powerful decomposition theorem. It also allows us to design a linear-time algorithm for the cluster containment problem for networks of this type and to prove that every galled network with n leaves has 2(n-1) reticulation nodes at most.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Solving Tree Containment Problem for Reticulation-visible Networks with Optimal Running Time
Tree containment problem is a fundamental problem in phylogenetic study, as it is used to verify a network model. It asks whether a given network contain a subtree that resembles a binary tree. The problem is NP-complete…
Locating a Tree in a Reticulation-Visible Network in Cubic Time
In this work, we answer an open problem in the study of phylogenetic networks. Phylogenetic trees are rooted binary trees in which all edges are directed away from the root, whereas phylogenetic networks are rooted acycl…
Bounding the number of reticulation events for displaying multiple trees in a phylogenetic network
Reconstructing a parsimonious phylogenetic network that displays multiple phylogenetic trees is an important problem in theory of phylogenetics, where the complexity of the inferred networks is measured by reticulation n…
On Tree Based Phylogenetic Networks
A large class of phylogenetic networks can be obtained from trees by the addition of horizontal edges between the tree edges. These networks are called tree based networks. Reticulation-visible networks and child-sibling…
Computing the Bounds of the Number of Reticulations in a Tree-Child Network That Displays a Set of Trees
Phylogenetic network is an evolutionary model that uses a rooted directed acyclic graph (instead of a tree) to model an evolutionary history of species in which reticulate events (e.g., hybrid speciation or horizontal ge…