© 2008 Society of Systematic Biologists
A Rapid Bootstrap Algorithm for the RAxML Web Servers
1 The Exelixis Lab, Teaching and Research Unit Bioinformatics, Department of Computer Science, Ludwig-Maximilians-University Munich Amalienstr. 17, D-80333, Munich, Germany; E-mail: stamatakis{at}bio.ifi.lmu.de
2 San Diego Supercomputer Center La Jolla, California, USA
3 School of Life Sciences, Ecole Polytechnique Fédérale de Lausanne Lausanne, Switzerland
Edited by Susanne Renner
 |
Abstract |
|---|
Despite recent advances achieved by application of high-performance computing methods and novel algorithmic techniques to maximum likelihood (ML)-based inference programs, the major computational bottleneck still consists in the computation of bootstrap support values. Conducting a probably insufficient number of 100 bootstrap (BS) analyses with current ML programs on large datasets—either with respect to the number of taxa or base pairs—can easily require a month of run time. Therefore, we have developed, implemented, and thoroughly tested rapid bootstrap heuristics in RAxML (Randomized Axelerated Maximum Likelihood) that are more than an order of magnitude faster than current algorithms. These new heuristics can contribute to resolving the computational bottleneck and improve current methodology in phylogenetic analyses. Computational experiments to assess the performance and relative accuracy of these heuristics were conducted on 22 diverse DNA and AA (amino acid), single gene as well as multigene, real-world alignments containing 125 up to 7764 sequences. The standard BS (SBS) and rapid BS (RBS) values drawn on the best-scoring ML tree are highly correlated and show almost identical average support values. The weighted RF (Robinson-Foulds) distance between SBS- and RBS-based consensus trees was smaller than 6% in all cases (average 4%). More importantly, RBS inferences are between 8 and 20 times faster (average 14.73) than SBS analyses with RAxML and between 18 and 495 times faster than BS analyses with competing programs, such as PHYML or GARLI. Moreover, this performance improvement increases with alignment size. Finally, we have set up two freely accessible Web servers for this significantly improved version of RAxML that provide access to the 200-CPU cluster of the Vital-IT unit at the Swiss Institute of Bioinformatics and the 128-CPU cluster of the CIPRES project at the San Diego Supercomputer Center. These Web servers offer the possibility to conduct large-scale phylogenetic inferences to a large part of the community that does not have access to, or the expertise to use, high-performance computing resources.
Keywords: Maximum likelihood; phylogenetic inference; rapid bootstrap; RAxML; support values
Received December 23, 2007; Revised March 6, 2008; Accepted May 20, 2008
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  J. L. Klassen Pathway Evolution by Horizontal Transfer and Positive Selection Is Accommodated by Relaxed Negative Selection upon Upstream Pathway Genes in Purple Bacterial Carotenoid Biosynthesis J. Bacteriol., December 15, 2009; 191(24): 7500 - 7508. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
U. Krauss, B. Q. Minh, A. Losi, W. Gartner, T. Eggert, A. von Haeseler, and K.-E. Jaeger Distribution and Phylogeny of Light-Oxygen-Voltage-Blue-Light-Signaling Proteins in the Three Kingdoms of Life J. Bacteriol., December 1, 2009; 191(23): 7234 - 7242. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 T. M. Townsend, D. R. Vieites, F. Glaw, and M. Vences Testing Species-Level Diversification Hypotheses in Madagascar: The Case of Microendemic Brookesia Leaf Chameleons Syst Biol, December 1, 2009; 58(6): 641 - 656. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 S. Agrawal, G. G. van Dooren, W. L. Beatty, and B. Striepen Genetic Evidence that an Endosymbiont-derived Endoplasmic Reticulum-associated Protein Degradation (ERAD) System Functions in Import of Apicoplast Proteins J. Biol. Chem., November 27, 2009; 284(48): 33683 - 33691. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 A. Eiler, S. Beier, C. Sawstrom, J. Karlsson, and S. Bertilsson High Ratio of Bacteriochlorophyll Biosynthesis Genes to Chlorophyll Biosynthesis Genes in Bacteria of Humic Lakes Appl. Envir. Microbiol., November 15, 2009; 75(22): 7221 - 7228. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 J. Jezbera, A. K. Sharma, U. Brandt, W. F. Doolittle, and M. W. Hahn 'Candidatus Planktophila limnetica', an actinobacterium representing one of the most numerically important taxa in freshwater bacterioplankton Int J Syst Evol Microbiol, November 1, 2009; 59(11): 2864 - 2869. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 M. Rastgou, M. K. Habibi, K. Izadpanah, V. Masenga, R. G. Milne, Y. I. Wolf, E. V. Koonin, and M. Turina Molecular characterization of the plant virus genus Ourmiavirus and evidence of inter-kingdom reassortment of viral genome segments as its possible route of origin J. Gen. Virol., October 1, 2009; 90(10): 2525 - 2535. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 Y. Furuse, A. Suzuki, and H. Oshitani Large-Scale Sequence Analysis of M Gene of Influenza A Viruses from Different Species: Mechanisms for Emergence and Spread of Amantadine Resistance Antimicrob. Agents Chemother., October 1, 2009; 53(10): 4457 - 4463. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 R. Schultheiss, B. Van Bocxlaer, T. Wilke, and C. Albrecht Old fossils-young species: evolutionary history of an endemic gastropod assemblage in Lake Malawi Proc R Soc B, August 7, 2009; 276(1668): 2837 - 2846. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
M. W. Hahn, E. Lang, U. Brandt, Q. L. Wu, and T. Scheuerl Emended description of the genus Polynucleobacter and the species Polynucleobacter necessarius and proposal of two subspecies, P. necessarius subsp. necessarius subsp. nov. and P. necessarius subsp. asymbioticus subsp. nov. Int J Syst Evol Microbiol, August 1, 2009; 59(8): 2002 - 2009. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 N. Mine, J. Guglielmini, M. Wilbaux, and L. Van Melderen The Decay of the Chromosomally Encoded ccdO157 Toxin-Antitoxin System in the Escherichia coli Species Genetics, April 1, 2009; 181(4): 1557 - 1566. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 C. Spitzer, F. C. Reyes, R. Buono, M. K. Sliwinski, T. J. Haas, and M. S. Otegui The ESCRT-Related CHMP1A and B Proteins Mediate Multivesicular Body Sorting of Auxin Carriers in Arabidopsis and Are Required for Plant Development PLANT CELL, March 1, 2009; 21(3): 749 - 766. [Abstract] [Full Text] [PDF]
|
|