Reconciliation and local gene tree rearrangement can be of mutual profit

Thi Nguyen 1 Vincent Ranwez 2 Stéphanie Pointet 3 Anne-Muriel Arigon Chifolleau 4 Jean-Philippe Doyon 4 Vincent Berry 4
2 DAAV - Diversité, Adaptation et Amélioration de la Vigne [AGAP]
UMR AGAP - Amélioration génétique et adaptation des plantes méditerranéennes et tropicales
4 MAB - Méthodes et Algorithmes pour la Bioinformatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Background Reconciliation methods compare gene trees and species trees to recover evolutionary events such as duplications, transfers and losses explaining the history and composition of genomes. It is well-known that gene trees inferred from molecular sequences can be partly erroneous due to incorrect sequence alignments as well as phylogenetic reconstruction artifacts such as long branch attraction. In practice, this leads reconciliation methods to overestimate the number of evolutionary events. Several methods have been proposed to circumvent this problem, by collapsing the unsupported edges and then resolving the obtained multifurcating nodes, or by directly rearranging the binary gene trees. Yet these methods have been defined for models of evolution accounting only for duplications and losses, i.e. can not be applied to handle prokaryotic gene families. Results We propose a reconciliation method accounting for gene duplications, losses and horizontal transfers, that specifically takes into account the uncertainties in gene trees by rearranging their weakly supported edges. Rearrangements are performed on edges having a low confidence value, and are accepted whenever they improve the reconciliation cost. We prove useful properties on the dynamic programming matrix used to compute reconciliations, which allows to speed-up the tree space exploration when rearrangements are generated by Nearest Neighbor Interchanges (NNI) edit operations. Experiments on synthetic data show that gene trees modified by such NNI rearrangements are closer to the correct simulated trees and lead to better event predictions on average. Experiments on real data demonstrate that the proposed method leads to a decrease in the reconciliation cost and the number of inferred events. Finally on a dataset of 30k gene families, this reconciliation method shows a ranking of prokaryotic phyla by transfer rates identical to that proposed by a different approach dedicated to transfer detection [BMCBIOINF 11:324, 2010, PNAS 109(13):4962-4967, 2012]. Conclusions Prokaryotic gene trees can now be reconciled with their species phylogeny while accounting for the uncertainty of the gene tree. More accurate and more precise reconciliations are obtained with respect to previous parsimony algorithms not accounting for such uncertainties [LNCS 6398:93-108, 2010, BIOINF 28(12): i283-i291, 2012]. A software implementing the method is freely available at
Type de document :
Article dans une revue
Algorithms for Molecular Biology, BioMed Central, 2013, 8 (12), 〈10.1186/1748-7188-8-12〉
Liste complète des métadonnées

Littérature citée [40 références]  Voir  Masquer  Télécharger
Contributeur : Anne-Muriel Arigon Chifolleau <>
Soumis le : jeudi 23 mai 2013 - 15:13:14
Dernière modification le : jeudi 11 janvier 2018 - 06:26:12
Document(s) archivé(s) le : lundi 3 avril 2017 - 04:42:57


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



Thi Nguyen, Vincent Ranwez, Stéphanie Pointet, Anne-Muriel Arigon Chifolleau, Jean-Philippe Doyon, et al.. Reconciliation and local gene tree rearrangement can be of mutual profit. Algorithms for Molecular Biology, BioMed Central, 2013, 8 (12), 〈10.1186/1748-7188-8-12〉. 〈lirmm-00812726〉



Consultations de la notice


Téléchargements de fichiers