SDM : A Fast Distance-Based Approach for (Super)Tree Building in Phylogenomics

Abstract : Phylogenomic studies aim to build phylogenies from large sets of homologous genes. Such genome-sized data require fast methods, because of the typically large numbers of taxa examined. In this framework, distance-based methods are useful for exploratory studies and building a starting tree to be refined by a more powerful maximum likelihood (ML) approach. However, estimating evolutionary distances directly from concatenated genes gives poor topological signal as genes evolve at different rates. We propose a novel method, named Super Distance Matrix (SDM), which follows the same line as Average Consensus Supertree (ACS, Lapointe and Cucumel, 1997) and combines the evolutionary distances obtained from each gene into a single distance supermatrix to be analyzed using a standard distance-based algorithm. SDM deforms the source matrices, without modifying their topological message, to bring them as close as possible to each other; these deformed matrices are then averaged to obtain the distance supermatrix. We show that this problem is equivalent to the minimization of a least-squares criterion subject to linear constraints. This problem has a unique solution which is obtained by resolving a linear system. As this system is sparse, its practical resolution requires O((nk)^a) time, where n is the number of taxa, k the number of matrices and a < 2, which allows the distance supermatrix to be quickly obtained. Several uses of SDM are proposed, from fast exploratory studies to more accurate approaches requiring heavier computing time. Using simulations, we show that SDM is a relevant alternative to the standard Matrix Representation with Parsimony (MRP) method, notably when the taxa sets of the different genes have low overlap. We also show that SDM can be used to build an excellent starting tree for an ML approach, which both reduces the computing time and increases the topogical accuracy. We use SDM to analyze the dataset of Gatesy et al. (2002) that involves 48 genes of 75 placental mammals. The results indicate that these genes have strong rate heterogeneity and confirm the simulation conclusions.
Type de document :
Article dans une revue
Systematic Biology, Oxford University Press (OUP), 2006, 55 (5), pp.740-755. 〈10.1080/10635150600969872〉
Liste complète des métadonnées

Littérature citée [76 références]  Voir  Masquer  Télécharger
Contributeur : Olivier Gascuel <>
Soumis le : mercredi 5 septembre 2012 - 14:52:17
Dernière modification le : jeudi 11 janvier 2018 - 06:26:12
Document(s) archivé(s) le : jeudi 6 décembre 2012 - 16:50:19


Fichiers éditeurs autorisés sur une archive ouverte




Alexis Criscuolo, Vincent Berry, Emmanuel J. P. Douzery, Olivier Gascuel. SDM : A Fast Distance-Based Approach for (Super)Tree Building in Phylogenomics. Systematic Biology, Oxford University Press (OUP), 2006, 55 (5), pp.740-755. 〈10.1080/10635150600969872〉. 〈lirmm-00136655〉



Consultations de la notice


Téléchargements de fichiers