Efficient FPT Algorithms for (Strict) Compatibility of Unrooted Phylogenetic Trees

Julien Baste 1 Christophe Paul 1 Ignasi Sau 1 Celine Scornavacca 2
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : In phylogenetics, a central problem is to infer the evolutionary relationships between a set of species $X$; these relationships are often depicted via a phylogenetic tree—a tree having its leaves labeled bijectively by elements of $X$ and without degree-2 nodes—called the “species tree.” One common approach for reconstructing a species tree consists in first constructing several phylogenetic trees from primary data (e.g., DNA sequences originating from some species in $X$), and then constructing a single phylogenetic tree maximizing the “concordance” with the input trees. The obtained tree is our estimation of the species tree and, when the input trees are defined on overlapping—but not identical—sets of labels, is called “supertree.” In this paper, we focus on two problems that are central when combining phylogenetic trees into a supertree: the compatibility and the strict compatibility problems for unrooted phylogenetic trees. These problems are strongly related, respectively, to the notions of “containing as a minor” and “containing as a topological minor” in the graph community. Both problems are known to be fixed parameter tractable in the number of input trees $k$, by using their expressibility in monadic second-order logic and a reduction to graphs of bounded treewidth. Motivated by the fact that the dependency on k of these algorithms is prohibitively large, we give the first explicit dynamic programming algorithms for solving these problems, both running in time $2O(k2)⋅n$, where n is the total size of the input.
Type de document :
Communication dans un congrès
AAIM: Algorithmic Aspects in Information and Management, Jul 2016, Bergamo, Italy. 11th International Conference on Algorithmic Aspects of Information and Management, LNCS (9778), pp.53-64, 2017, 〈10.1007/s11538-017-0260-y〉
Liste complète des métadonnées

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

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01481368
Contributeur : Christophe Paul <>
Soumis le : jeudi 2 mars 2017 - 15:03:16
Dernière modification le : vendredi 19 octobre 2018 - 14:22:03
Document(s) archivé(s) le : mercredi 31 mai 2017 - 15:03:22

Fichier

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

Identifiants

Citation

Julien Baste, Christophe Paul, Ignasi Sau, Celine Scornavacca. Efficient FPT Algorithms for (Strict) Compatibility of Unrooted Phylogenetic Trees. AAIM: Algorithmic Aspects in Information and Management, Jul 2016, Bergamo, Italy. 11th International Conference on Algorithmic Aspects of Information and Management, LNCS (9778), pp.53-64, 2017, 〈10.1007/s11538-017-0260-y〉. 〈lirmm-01481368〉

Partager

Métriques

Consultations de la notice

223

Téléchargements de fichiers

143