Design And Implementation Of Parallel PHYLIP Based On The Multi-Core Computing Environment

Phylogenetic analysis is an important bioinformatics research, which includes a lot of algorithms to generate phylogenetic tree. The performances of these algorithms have been concerned as sequence datasets have been becoming larger and larger these years. PHYLIP, as a widely used phylogeny package, has performance problem too. Some of its programs have high time complexity, which need dozens of hours to deal with large datasets. So far, there are parallel works on PHYLIP yet, but most of them are based on a previous version and under a message-passing environment.On the other head, there are more powerful parallel methods as the dominance of multi-core CPU and the development of GPGPU. Compared to the message-passing environment, they can achieve good performance with less hardware investment.In this paper, we paralleled distance matrix method programs and maximum likelihood programs in PHYLIP under a multi-core CPU environment and a GPGPU environment respectively. We analyzed these programs, considered the characteristics of the two environments, found suitable parallel strategies and optimization methods, and finally achieved high performances. On a multi-core CPU environment, which has 4 cores and 8 threads, distance matrix method programs paralleled by using OpenMP can achieve speedups of 7X to 8X, and maximum likelihood programs can also achieve speedups of 2X to 6X; Similarly; On a NVIDIA Tesla C2050 GPU, programs are accelerated by using CUDA, two distance matrix method programs achieve speedups of 16X and 72X respectively, and a maximum likelihood program also has a speedup of more than 9X. The result shows that multi-core CPU and GPGPU environments are powerful and cost-effective parallel environments,which can significantly improve the performance of matrix method programs and maximum likelihood programs. We can also conclude that, to achieve high performance, it is necessary to analyze algorithms correctly, and chose suitable parallel strategies and optimization methods according to the characteristics of the parallel environment.