Accelerating Protein Structure Prediction using Particle Swarm Optimization on GPU

Background: Protein tertiary structure prediction (PSP) is one of the most challenging problems in bioinformatics. Different methods have been introduced to solve this problem so far, but PSP is computationally intensive and belongs to the NP-hard class. One of the best solutions to accelerate PSP is the use of a massively parallel processing architecture, such graphical processing unit (GPU), which is used to parallelize computational algorithms. In this paper, we have proposed a parallel architecture to accelerate PSP using the particle swarm optimization (PSO).

Methodology/Principal Findings: A bio-inspired method, particle swarm optimization have been used as the optimization method to solve PSP. We have also done a comprehensive study on implementing different topologies of PSO on GPU to consider the acceleration rate. Our solution belongs to ab-initio category which is based on the dihedral angles and calculates the energy-levels to predict the tertiary structure. Indeed, we have studied the search space of a protein strongly to find the best pair of angles that gives the minimum free energy. A profile-level knowledge-based force field by PSI-BLAST using multiple sequence alignment has been applied to energy calculation as the fitness function.

Conclusions: Different topologies and variations of PSO are considered here and the experimental results show that the speedup gain using GPU is about 34 times faster than CPU implementation of the algorithm with an acceptable precision. The energy value of predicted structures confirms the algorithm. However, as this work concentrate on accelerating the problem the root mean square deviation (RMSD) analysis is not performed because it depends to the selected force field directly.



Implementation topologies

Download CUDA/C++ source codes: