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 in general, even in the class of binary network. Recently, it was proven to be solvable in cubic time, and later in quadratic time for the class of general reticulation visible networks. In this paper, we further improve the time complexity into linear time.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
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…
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…
Fast Methods for Solving the Cluster Containment Problem for Phylogenetic Networks
Genetic and comparative genomic studies indicate that extant genomes are more properly considered to be a fusion product of random mutations over generations and genomic material transfers between individuals of differen…
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…
Solving the Tree Containment Problem Using Graph Neural Networks
Tree Containment is a fundamental problem in phylogenetics useful for verifying a proposed phylogenetic network, representing the evolutionary history of certain species. Tree Containment asks whether the given phylogene…
Graph Neural NetworkInductive Learning