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 acyclic digraphs. For the purpose of evolutionary model validation, biologists often want to know whether or not a phylogenetic tree is contained in a phylogenetic network. The tree containment problem is NP-complete even for very restricted classes of networks such as tree-sibling phylogenetic networks. We prove that this problem is solvable in cubic time for stable phylogenetic networks. A linear time algorithm is also presented for the cluster containment problem.
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 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 phylog…
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…