SDM : A Fast Distance-Based Approach for (Super)Tree Building in Phylogenomics - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles Systematic Biology Year : 2006

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


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.
Fichier principal
Vignette du fichier
Criscuolo_et_al-2006-SystBiol-2.pdf (1.26 Mo) Télécharger le fichier
Origin Publisher files allowed on an open archive

Dates and versions

lirmm-00136655 , version 1 (05-09-2012)



Alexis Criscuolo, Vincent Berry, Emmanuel J.P. Douzery, Olivier Gascuel. SDM : A Fast Distance-Based Approach for (Super)Tree Building in Phylogenomics. Systematic Biology, 2006, 55 (5), pp.740-755. ⟨10.1080/10635150600969872⟩. ⟨lirmm-00136655⟩
288 View
470 Download



Gmail Mastodon Facebook X LinkedIn More