Solving the tree containment problem in linear time for nearly stable phylogenetic networks

Abstract : A phylogenetic network is a rooted acyclic digraph whose leaves are uniquely labeled with a set of taxa. The tree containment problem asks whether or not a phylogenetic network displays a phylogenetic tree over the same set of labeled leaves. It is a fundamental problem arising from validation of phylogenetic network models. The tree containment problem is NP-complete in general. To identify network classes on which the problem is polynomial time solvable, we introduce two classes of networks by generalizations of tree-child networks through vertex stability, namely nearly stable networks and genetically stable networks. Here, we study the combinatorial properties of these two classes of phylogenetic networks. We also develop a linear-time algorithm for solving the tree containment problem on binary nearly stable networks.
Type de document :
Article dans une revue
Discrete Applied Mathematics, Elsevier, 2018, 246, pp.62-79. 〈10.1016/j.dam.2017.07.015〉
Liste complète des métadonnées

Littérature citée [8 références]  Voir  Masquer  Télécharger

https://hal-upec-upem.archives-ouvertes.fr/hal-01575001
Contributeur : Philippe Gambette <>
Soumis le : jeudi 26 juillet 2018 - 12:54:08
Dernière modification le : mardi 7 août 2018 - 14:19:46
Document(s) archivé(s) le : samedi 27 octobre 2018 - 12:56:24

Fichier

DAM2017.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Philippe Gambette, Andreas D.M. Gunawan, Anthony Labarre, Stéphane Vialette, Louxin Zhang. Solving the tree containment problem in linear time for nearly stable phylogenetic networks. Discrete Applied Mathematics, Elsevier, 2018, 246, pp.62-79. 〈10.1016/j.dam.2017.07.015〉. 〈hal-01575001〉

Partager

Métriques

Consultations de la notice

321

Téléchargements de fichiers

28