Bioinformatics Vol. 17 no. 12 2001
Pages 1168-1178
© 2001 Oxford University Press
Minimum conflict: a divide-and-conquer approach to phylogeny estimation
1 Ruhr-Universität
Bochum, Lehrstuhl für spez. Zoologie,
D-44780 Bochum, Germany
2 Universität
Bielefeld, Technische Fakultät,
D-33594 Bielefeld, Germany
3 Universität
Münster, Integrated Functional
Genomics, IZKF, D-48149 Münster,
Germany
Received on December 1, 2000
; revised on May 8, 2001
; accepted on May 25, 2001
Motivation: Fast and reliable phylogeny estimation is rapidly gaining importance as more and more genomic sequence information is becoming available, and the study of the evolution of genes and genomes accelerates our understanding in biology and medicine alike. Branch attraction phenomena due to unequal amounts of evolutionary change in different parts of the phylogeny are one major problem for current methods, placing the species that evolved fast in one part of the phylogenetic tree, and the species that evolved slowly in the other.
Results: We describe a way to avoid the artifactual attraction of species that evolved slowly, by detecting shared old character states using a calibrated comparison with an outgroup. The corresponding focus on shared novel character states yields a fast and transparent phylogeny estimation algorithm, by application of the divide-and-conquer principle, and heuristic search: shared novelties give evidence of the exclusive common heritage (monophyly) of a subset of the species. They indicate conflict in a split of all species considered, if the split tears them apart. Only the split at the root of the phylogenetic tree cannot have such conflict. Therefore, we can work top-down, from the root to the leaves, by heuristically searching for a minimum-conflict split, and tackling the resulting two subsets in the same way. The algorithm, called ‘minimum conflict phylogeny estimation’ (MCOPE), has been validated successfully using both natural and artificial data. In particular, we reanalyze published trees, yielding more plausible phylogenies, and we analyze small ‘undisputed’ trees on the basis of alignments considering structural homology.
Availability: MCOPEis available via http://bibiserv.techfak.uni-bielefeld.de/mcope/.
Contact: fuellen{at}alum.mit.edu
* To whom correspondence should be addressed.
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  S. Hoegg, M. Vences, H. Brinkmann, and A. Meyer Phylogeny and Comparative Substitution Rates of Frogs Inferred from Sequences of Three Nuclear Genes Mol. Biol. Evol., July 1, 2004; 21(7): 1188 - 1200. [Abstract] [Full Text] [PDF]
|
|