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.
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

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 : mercredi 23 mars 2016 - 21:12:23
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

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>

Partager

Métriques

Consultations de
la notice

193

Téléchargements du document

82