Enhanced Van der Waals calculations in genetic algorithms for protein structure prediction

摘要

Several ab initio computational methods for protein structure prediction have been designed using full-atom models and force field potentials to describe interactions among atoms. Those methods involve the solution of a combinatorial problem with a huge search space. Genetic algorithms (GAs) have shown significant performance increases for such methods. However, even a small protein may require hundreds of thousands of energy function evaluations making GAs suitable only for the prediction of very small proteins. We propose an efficient technique to compute the van der Waals energy (the greatest contributor to protein stability) speeding up the whole GA. First, we developed a Cell-List Reconstruction procedure that divides the tridimensional space into a cell grid for each new structure that the GA generates. The cells restrict the calculations of van der Waals potentials to ranges in which they are significant, reducing the complexity of such calculations from quadratic to linear. Moreover, the proposal also uses the structure of the cell grid to parallelize the computation of the van der Waals energy, achieving additional speedup. The results have shown a significant reduction in the run time required by a GA. For example, the run time for the prediction of a protein with 147,980 atoms can be reduced from 217 days to 7 h.