Solving the Tree Containment Problem for Genetically Stable Networks in Quadratic Time

Philippe Gambette 1 Andreas D.M. Gunawan 2 Anthony Labarre 1 Stéphane Vialette 1 Louxin Zhang 2
1 LIGM - Laboratoire d'Informatique Gaspard-Monge
2 Department of Mathematics [Singapore]
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.
Keywords : tree containment phylogenetic network genetically stable
Document type :
Conference papers
Complete list of metadatas

Cited literature [10 references]  Display  Hide  Download
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 : Thursday, July 5, 2018 - 2:45:57 PM
Long-term archiving on: Monday, February 8, 2016 - 11:14:30 AM

File

IWOCA2015_genetically_stable (...
Files produced by the author(s)

Identifiers

Collections

UPEC-UPEM | CNRS | LIGM_ALGO | LIGM | LIGM_MOA | ENPC | PARISTECH | ESIEE-PARIS

Citation

Philippe Gambette, Andreas D.M. Gunawan, Anthony Labarre, Stéphane Vialette, Louxin Zhang. Solving the Tree Containment Problem for Genetically Stable Networks in Quadratic Time. IWOCA 2015, Oct 2015, Verona, Italy. pp.197-208, ⟨10.1007/978-3-319-29516-9_17⟩. ⟨hal-01226035⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

417

Files downloads

239

Contact

CCSD