| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
© 2007 Society of Systematic Biologists
Increasing the Efficiency of Searches for the Maximum Likelihood Tree in a Phylogenetic Analysis of up to 150 Nucleotide Sequences
1 Department of Parasitology (SWEPAR), National Veterinary Institute and Swedish University of Agricultural Sciences 751 89, Uppsala, Sweden E-mail: David.Morrison{at}bvf.slu.se
Edited by Laura Kubatko: Associate Editor Jack Sullivan Editor-in-Chief
 |
Abstract |
|---|
Even when the maximum likelihood (ML) tree is a better estimate of the true phylogenetic tree than those produced by other methods, the result of a poor ML search may be no better than that of a more thorough search under some faster criterion. The ability to find the globally optimal ML tree is therefore important. Here, I compare a range of heuristic search strategies (and their associated computer programs) in terms of their success at locating the ML tree for 20 empirical data sets with 14 to 158 sequences and 411 to 120,762 aligned nucleotides. Three distinct topics are discussed: the success of the search strategies in relation to certain features of the data, the generation of starting trees for the search, and the exploration of multiple islands of trees. As a starting tree, there was little difference among the neighbor-joining tree based on absolute differences (including the BioNJ tree), the stepwise-addition parsimony tree (with or without nearest-neighbor-interchange (NNI) branch swapping), and the stepwise-addition ML tree. The latter produced the best ML score on average but was orders of magnitude slower than the alternatives. The BioNJ tree was second best on average. As search strategies, star decomposition and quartet puzzling were the slowest and produced the worst ML scores. The DPRml, IQPNNI, MultiPhyl, PhyML, PhyNav, and TreeFinder programs with default options produced qualitatively similar results, each locating a single tree that tended to be in an NNI suboptimum (rather than the global optimum) when the data set had low phylogenetic information. For such data sets, there were multiple tree islands with very similar ML scores. The likelihood surface only became relatively simple for data sets that contained approximately 500 aligned nucleotides for 50 sequences and 3,000 nucleotides for 100 sequences. The RAxML and GARLI programs allowed multiple islands to be explored easily, but both programs also tended to find NNI suboptima. A newly developed version of the likelihood ratchet using PAUP* successfully found the peaks of multiple islands, but its speed needs to be improved.
Keywords: Large data sets; maximum likelihood; phylogeny; search strategies; tree islands
Received January 10, 2007; Revised April 23, 2007; Accepted October 9, 2007
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  K. Mummenhoff, A. Polster, A. Muhlhausen, and G. Theissen Lepidium as a model system for studying the evolution of fruit development in Brassicaceae J. Exp. Bot., April 1, 2009; 60(5): 1503 - 1513. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 A. Kawakita and M. Kato Repeated independent evolution of obligate pollination mutualism in the Phyllantheae-Epicephala association Proc R Soc B, February 7, 2009; 276(1656): 417 - 426. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 A. Stamatakis, P. Hoover, and J. Rougemont A Rapid Bootstrap Algorithm for the RAxML Web Servers Syst Biol, October 1, 2008; 57(5): 758 - 771. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
D. A. Morrison Phylogenetic Trees Made Easy: A How-to Manual, third edition.--Barry G. Hall. 2008. Sinauer Associates, Sunderland, Massachusetts. xiv + 230 pp. ISBN 978-0-87893-310-5. $US39.95 {pound}24.99 (paperback) Syst Biol, August 1, 2008; 57(4): 658 - 660. [Full Text] [PDF]
|
|