Inference of phylogenetic trees comprising thousands of taxa using maximum likelihood is computationally extremely expensive. We present simple heuristics which yield accurate trees for simulated as well as real data and reduce execution time. The new heuristics have been implemented in a program called RAxML which is freely available. Furthermore, we present a distributed version of our algorithm which is implemented in an MPI-based prototype. This prototype is being used to implement an http-based seti@home-like version of RaxML. We compare our program with PHYML and MrBayes which are currently the fastest and most accurate programs for phylogenetic tree inference. Experiments are conducted using 50 simulated 100 taxon alignments as well as real-world alignments with 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 outperforms PHYML by factor 2-8 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

@inproceedings{NFAAHFIOLP04,
	author	 = {Alexandros P. Stamatakis and Thomas Ludwig and Harald Meier},
	title	 = {{New Fast and Accurate Heuristics for Inference of Large Phylogenetic Trees}},
	year	 = {2004},
	booktitle	 = {{Proceedings of 18th IEEE/ACM International Parallel and Distributed Processing Symposium}},
	publisher	 = {IEEE Computer Society},
	address	 = {Washington, DC, USA},
	pages	 = {193},
	conference	 = {IPDPS-04},
	organization	 = {University of New Mexico},
	location	 = {Santa Fe, New Mexico},
	isbn	 = {0-7695-2132-0},
	doi	 = {http://dx.doi.org/10.1109/IPDPS.2004.1303212},
	abstract	 = {Inference of phylogenetic trees comprising thousands of taxa using maximum likelihood is computationally extremely expensive. We present simple heuristics which yield accurate trees for simulated as well as real data and reduce execution time. The new heuristics have been implemented in a program called RAxML which is freely available. Furthermore, we present a distributed version of our algorithm which is implemented in an MPI-based prototype. This prototype is being used to implement an http-based seti@home-like version of RaxML. We compare our program with PHYML and MrBayes which are currently the fastest and most accurate programs for phylogenetic tree inference. Experiments are conducted using 50 simulated 100 taxon alignments as well as real-world alignments with 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 outperforms PHYML by factor 2-8 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},
}