 |
HAL UPEC - UPEM Portal |  |
 |
Solving the Tree Containment Problem for Genetically Stable Networks in Quadratic Time
Abstract : A phylogenetic network is a rooted acyclic digraph whose leaves are labeled with a set of taxa. The tree containment problem is a fundamental problem arising from model validation in the study of phylogenetic networks. It asks to determine whether or not a given network displays a given phylogenetic tree over the same leaf set. It is known to be NP-complete in general. Whether or not it remains NP-complete for stable networks is an open problem. We make progress towards answering that question by presenting a quadratic time algorithm to solve the tree containment problem for a new class of networks that we call genetically stable networks, which include tree-child networks and comprise a subclass of stable networks.
Cited literature [10 references]
https://hal-upec-upem.archives-ouvertes.fr/hal-01226035
Contributor : Philippe Gambette <>
Submitted on : Saturday, November 7, 2015 - 11:14:02 PM
Last modification on : Wednesday, February 26, 2020 - 7:06:07 PM
Document(s) archivé(s) le : Monday, February 8, 2016 - 11:14:30 AM
Contributor : Philippe Gambette <>
Submitted on : Saturday, November 7, 2015 - 11:14:02 PM
Last modification on : Wednesday, February 26, 2020 - 7:06:07 PM
Document(s) archivé(s) le : Monday, February 8, 2016 - 11:14:30 AM
File
IWOCA2015_genetically_stable (...
Files produced by the author(s)
