Adapting PAxML to the Hitachi SR8000-F1 Supercomputer

Heuristics for the NP-complete problem of calculating the optimal phy-logenetic tree for a set of aligned rRNA sequences based on the maximum likelihood method are computationally expensive. Thus, supercomputers and appropriately optimized and adapted parallel programs are required in order to perform computations of large phylogenetic tress. The core of most parallel algorithms is the tree evaluation function, calculating the likelihood value for each tree topology. It accounts for the greatest part of overall computation time. This paper introduces a general method for significantly accelerating the computation of the maximum likelihood value for a given tree topology by using SEVs (Subtree Equality Vectors) to significantly reduce the number of floating point operations during each topology evaluation. Furthermore, we present the parallel implementation of our method in a program called PAxML derived from parallel fastDNAml and describe its adaptation to the Hitachi SR8000-F1 architecture. Tests performed with various sequential and parallel phylogeny programs on SUN workstations show global run time improvements of 35% to 47% induced by our method, whereas analogous initial tests on the Hitachi SR8000-F1, with an appropriately adapted version of PAxML show global run time improvements of 24% to 35% over parallel fastDNAml, as well as a promising floating point performance per processor ranging between 106 Mflops/s and 129 Mflops/s.1