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 different lineages. This has motivated researchers to adopt phylogenetic networks and other general models to study genome evolution. One important problem arising from reconstruction and verification of phylogenetic networks is the cluster containment problem, namely determining whether or not a cluster of taxa is displayed in a phylogenetic network. In this work, a new upper bound for this NP-complete problem is established through an efficient reduction to the SAT problem. Two efficient (albeit exponential time) methods are also implemented. It is developed on the basis of generalization of the so-called reticulation-visible property of phylogenetic networks.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
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 LearningContainment for Rule-Based Ontology-Mediated Queries
Many efforts have been dedicated to identifying restrictions on ontologies expressed as tuple-generating dependencies (tgds), a.k.a. existential rules, that lead to the decidability for the problem of answering ontology-…
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…
A Semi-Supervised Pipeline for Generalized Behavior Discovery from Animal-Borne Motion Time Series
Learning behavioral taxonomies from animal-borne sensors is challenging because labels are scarce, classes are highly imbalanced, and behaviors may be absent from the annotated set. We study generalized behavior discover…