New Fast and Accurate Heuristics for Inference
                   of Large Phylogenetic Trees

      Alexandros P. Stamatakis, Harald Meier, Thomas Ludwig


ABSTRACT

Inference of phylogenetic trees comprising hundreds or even thousands
of organisms based on the maximum likelihood method is computationally
extremely expensive. We present simple new heuristics which yield
accurate trees for synthetic (simulated) as well as real data and
significantly reduce execution time. The new heuristics have been
implemented in a program called RAxML which is freely available as
open source code. Furthermore, we present a distributed version of our
algorithm which is implemented in an MPI-based prototype. This
prototype is currently being used to implement an http-based
seti@home-like version of RAxML. We compare our program with PHYML and
MrBayes which to our best knowledge are currently the fastest and most
accurate programs for phylogenetic tree inference based on statistical
methods. Experiments are conducted using 50 synthetic 100 taxon
alignments as well as real-world alignments comprising 101 up to 1000
sequences. RAxML outperforms MrBayes for real-world data both in terms
of speed and final likelihood values. Furthermore, for real data RAxML
requires less time (factor 2-8) than PHYML to reach PHYML's final
likelihood values and yields better final trees due to its more
exhaustive search strategy. For synthetic data MrBayes is slightly
more accurate than RAxML and PHYML but significantly slower.