Do branch lengths help to locate a tree in a phylogenetic network?

Abstract : Phylogenetic networks are increasingly used in evolutionary biology to represent the history of species that have undergone reticulate events such as horizontal gene transfer, hybrid speciation and recombination. One of the most fundamental questions that arise in this context is whether the evolution of a gene with one copy in all species can be explained by a given network. In mathematical terms, this is often translated in the following way: is a given phylogenetic tree contained in a given phylogenetic network? Recently this tree containment problem has been widely investigated from a computational perspective, but most studies have only focused on the topology of the phylo-genies, ignoring a piece of information that, in the case of phylogenetic trees, is routinely inferred by evolutionary analyses: branch lengths. These measure the amount of change (e.g., nucleotide substitutions) that has occurred along each branch of the phylogeny. Here, we study a number of versions of the tree containment problem that explicitly account for branch lengths. We show that, although length information has the potential to locate more precisely a tree within a network, the problem is computationally hard in its most general form. On a positive note, for a number of special cases of biological relevance, we provide algorithms that solve this problem efficiently. This includes the case of networks of limited complexity, for which it is possible to recover, among the trees contained by the network with the same topology as the input tree, the closest one in terms of branch lengths.
Type de document :
Article dans une revue
Bulletin of Mathematical Biology, Springer Verlag, 2016, 78 (9), pp.1773-1795. 〈10.1007/s11538-016-0199-4〉
Liste complète des métadonnées

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

https://hal-upec-upem.archives-ouvertes.fr/hal-01372824
Contributeur : Admin Upem <>
Soumis le : mardi 27 septembre 2016 - 16:44:36
Dernière modification le : vendredi 19 octobre 2018 - 14:22:03
Document(s) archivé(s) le : mercredi 28 décembre 2016 - 14:20:16

Fichier

2016GambetteIerselKelkPardiSco...
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Philippe Gambette, Leo Van Iersel, Steven Kelk, Fabio Pardi, Celine Scornavacca. Do branch lengths help to locate a tree in a phylogenetic network?. Bulletin of Mathematical Biology, Springer Verlag, 2016, 78 (9), pp.1773-1795. 〈10.1007/s11538-016-0199-4〉. 〈hal-01372824〉

Partager

Métriques

Consultations de la notice

546

Téléchargements de fichiers

47