From Gene Trees to Species Trees
Authors:
- Bin MaBMBin Ma
- Ming LiMLMing Li
- Louxin ZhangLZLouxin Zhang
- 1 January 2000
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 30 (3) , 729-752
Abstract
This paper studies various algorithmic issues in reconstructing a species tree from gene trees under the duplication and the mutation costmodel. This is a fundamental problem in computational molecular biology. Our main results are as follows. A linear time algorithm is presented for computing all the losses in duplications associated with the least common ancestor mapping from a gene tree to a species tree. This answers a problem raised recently by Eulenstein, Mirkin, and Vingron [J. Comput. Bio., 5 (1998), pp. 135--148]. The complexity of finding an optimal species tree from gene trees is studied. The problem is proved to be NP-hard for the duplication cost and for the mutation cost. Further, the concept of reconciled trees was introduced by Goodman et al. and formalized by Page for visualizing the relationship between gene and species trees. We show that constructing an optimal reconciled tree for gene trees is also NP-hard. Finally, we consider a general reconstruction problem and show it to be NP-hard even for the well-known nearest neighbor interchange distance. A new and efficiently computable metric is defined based on the duplication cost. We show that the problem of finding an optimal species tree from gene trees is NP-hard under this new metric but it can be approximated within factor 2 in polynomial time. Using this approximation result, we propose a heuristic method for finding a species tree from gene trees with uniquely labeled leaves under the duplication cost. Our experimental tests demonstrate that when the number of species is larger than 15 and gene trees are close to each other, our heuristic method is significantly better than the existing program in Page's GeneTree 1.0 that starts the search from a random tree.Keywords
This publication has 27 references indexed in Scilit:
- On the equivalence of two tree mapping measuresDiscrete Applied Mathematics, 1998
- Duplication-Based Measures of Difference Between Gene and Species TreesJournal of Computational Biology, 1998
- On the Nearest Neighbour Interchange Distance Between Evolutionary TreesJournal of Theoretical Biology, 1996
- Reconstruction of Ancient Molecular PhylogenyMolecular Phylogenetics and Evolution, 1996
- A Biologically Consistent Model for Comparing Molecular PhylogeniesJournal of Computational Biology, 1995
- PHYLOGENIES FROM MOLECULAR SEQUENCES: INFERENCE AND RELIABILITYAnnual Review of Genetics, 1988
- Fast Algorithms for Finding Nearest Common AncestorsSIAM Journal on Computing, 1984
- Fitting the Gene Lineage into its Species Lineage, a Parsimony Strategy Illustrated by Cladograms Constructed from Globin SequencesSystematic Zoology, 1979
- Cyclic ordering is NP-completeTheoretical Computer Science, 1977
- Construction of Phylogenetic TreesScience, 1967