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
Type de document :
Communication dans un congrès
Zsuzsanna Lipták; William F. Smyth. IWOCA 2015, Oct 2015, Verona, Italy. Springer, Lecture Notes in Computer Science, 9538, pp.197-208, 2016, Proceedings of the 26th International Workshop on Combinatorial Algorithms. 〈10.1007/978-3-319-29516-9_17〉
Liste complète des métadonnées

Littérature citée [10 références]  Voir  Masquer  Télécharger
https://hal-upec-upem.archives-ouvertes.fr/hal-01226035
Contributeur : Philippe Gambette <>
Soumis le : samedi 7 novembre 2015 - 23:14:02
Dernière modification le : jeudi 5 juillet 2018 - 14:45:57
Document(s) archivé(s) le : lundi 8 février 2016 - 11:14:30

Fichier

IWOCA2015_genetically_stable (...
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

UPEC-UPEM | 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. Zsuzsanna Lipták; William F. Smyth. IWOCA 2015, Oct 2015, Verona, Italy. Springer, Lecture Notes in Computer Science, 9538, pp.197-208, 2016, Proceedings of the 26th International Workshop on Combinatorial Algorithms. 〈10.1007/978-3-319-29516-9_17〉. 〈hal-01226035〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

327

Téléchargements de fichiers

137

Contact

support.ccsd.cnrs.fr
hal.support@ccsd.cnrs.fr
Logo CCSD