Comparing parallel algorithms for van der waals energy with cell-list technique for protein structure prediction / Comparando algoritmos paralelos para energia de van der waals com técnica de lista de células para predição de estrutura de proteína

Daniel R. F. Bonetti, Gesiel Rios Lopes, Alexandre C. B. Delbem, Paulo S. L. Souza, Kalinka C. Branco, Gonzalo Travieso


The discovery of the structure of a protein is a difficult and expensive task, because it requires minimizing different energies related to them. The van der Waals energy hás the most expensive evaluation in this context, and computational methods have been developed in this way, such as Genetic Algorithm (GA) and cell-list technique, which reduces its the complexity from O(n2) to O(n). Even with the support of GA and cell lists, the van der Waals energy evaluation still requires a long computing time, even for a small protein. Parallel Computing is capable to reduce the runtime to predict the structure of proteins. Parallel algorithms in such context are usually specific for one programming model and computer architecture, resulting in limited speedups. This paper compares the runtime of three distinct parallel algorithms for the evaluation of an ab initio and full-atom approach based on GA and cell-list technique, in order to minimize the van der Waals energy. The three parallel algorithms are in C and use one of these programming models: MPI, OpenMP or hybrid (MPI+Open MP). Our results show that van der Waals Energy are executed faster and with better speedups when using hybrid and more flexible parallel algorithms to predict the structure of larger proteins. We also show that for small proteins the communication of MPI imposes a high overhead for the parallel execution and, thus the Open MP presents a better relation cost x benefit in such cases.


Parallel computing, Genetic Algorithms, Protein Structure Prediction, ab initio, van der Waals energy.

Full Text:



Alba, E., Nebro, A. J., and Troya, J. M. (2002). Heterogeneous computing and parallel genetic algorithms. Journal of Parallel and Distributed Computing, 62:1362–1385. Malaga 29071, Spain accepted January 29, 2002.´

Allen, M. P. and Tildesley, D. J. (1987). Computer Simulation of Liquids. Oxford University Press.

Anfinsen, C. B. (1972). Studies on the principles that govern the folding of protein chains. Nobel Lecture, pages 103–119.

Becker, O. M., Jr., A. D. M., Roux, B., and Watanabe, M. (2001). Computational Biochemistry and Biophysics. CRC.

Ben´ıtez, C. M. V. and Lopes, H. S. (2010). Protein structure prediction with the 3dhp side-chain model using a master–slave parallel genetic algorithm. Journal of the Brazilian Computer Society, 16(1):69–78.

Berg, J., Tymoczko, J., and Stryer, L. (2002). Biochemistry 5th ed. W. H. Freeman.

Bonetti, D. R., Delbem, A. C., Travieso, G., and Souza, P. S. L. (2013). Enhanced van der waals calculations in genetic algorithms for protein structure prediction. Concurrency and Computation: Practice and Experience, 25(15):2170–2186.

Bonetti, D. R. F. (2010). Aumento da eficiencia do calculo da energia de van der waals em algoritmos geneticos para predicao de estruturas de proteinas. Master’s thesis, Institute of Mathematics Sciences and Computation - University of Sao

Paulo. tde-20052010-110415/pt-br.php.

Bonetti, D. R. F., DELBEM, A. C. B., and ANDRADE, F. B. (2010a). Improving the efficiency of the van der waals energy function used in the genetic algorithms for protein structure prediction. Biomat 2010 10h International Symposium on Mathematical and Computational Biology.

Bonetti, D. R. F., Delbem, A. C. B., Travieso, G., and de Souza, P. S. L. (2010b). Optimizing van der waals calculi using cell-lists and mpi. In Evolutionary Computation (CEC), 2010 IEEE Congress on, pages 1 –7.

Brasil, C. R. S. and Delbem, A. C. B. (2011). Ivestigating relevants aspects moeas protein structure prediction. GECCO 2011, pages 1–8. Manuscript sumbitted for publication.

Brasil, C. R. S., Lima, T. W. D., Gabriel, P. H. R., and Delbem, A. C. B. (2008). Moprotpred: A multiobjective evolutionary algorithm to protein structure prediction with area accessibility. 8th International Symposium on Mathematical and Computational Biology. Proceedings of BIOMAT 2008, pages 1–2. Campos do Jordao.

Case, D., Darden, T., Cheatham, T., III, Simmerling, C., Wang, J., Duke, R., Luo, R., Merz, K., Wang, B., Pearlman, D., Crowley, M., Brozell, S., Tsui, V., Gohlke, H., Mongan, J., Hornak, V., Cui, G., Beroza, P., Schafmeister, C., Caldwell, J., Ross, W., and Kollman, P. (2004). AMBER 8. University of California, San Francisco.

Das, S., Abraham, A., Chakraborty, U., and Konar, A. (2009). Differential evolution using a neighborhood-based mutation operator. Evolutionary Computation, IEEE Transactions on, 13(3):526–553.

de Lima Correa, L., Borguesan, B., Krause, M. J., and Dorn, M. (2018).ˆ Threedimensional protein structure prediction based on memetic algorithms. Computers Operations Research, 91:160 – 177.

Dorn, M., e Silva, M. B., Buriol, L. S., and Lamb, L. C. (2014). Three-dimensional protein structure prediction: Methods and computational strategies. Computational Biology and Chemistry, 53:251 – 276.

Friesner, R. A. (2002). Computational Methods for Protein Folding: Advances in Chemical Physics. Wiley.

Haile, J. (1992). Molecular dynamics simulation: elementary methods. John Wiley & Sons, Inc. New York, NY, USA.

Handl, J., Lovell, S. C., and Knowles, J. (2008). Investigations into the effect of multiobjectivization in protein structure prediction. In Rudolph, G., Jansen, T., Beume, N., Lucas, S., and Poloni, C., editors, Parallel Problem Solving from Nature – PPSN X, pages 702–711, Berlin, Heidelberg. Springer Berlin Heidelberg.

IOzone (2009). Iozone filesystem benchmark.

Jones, J. E. (1924). On the determination of molecular fields. ii. from the equation of state of a gas. Proceedings of the Royal Society of London. Series A, 106(738):463–477.

Larranaga, P. and Lozano, J. A. (2002). Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation (Genetic Algorithms and Evolutionary Computation). Kluwer Academic Publishers Group.

Nelson, D. L. and Cox, M. M. (2004). Lehninger Principles Of Biochemistry Fourth Edition. w. H. Freeman.

Sandia, C. (2003). LAMMPS Users Manual. Last access: December, 2010.

Spoel, D. V. D., Lindahl, E., Hess, B., van Buuren, A. R., Apol, E., Meulenhoff, P. J., Tieleman, D. P., Sijbers, A. L. T. M., Feenstra, K. A., van Drunen, R., and Berendsen, H. J. C. (2004). Gromacs User Manual Version 3.2. 19-21.

Storn, R. and Price, K. (1997). Differential evolution - a simple and efficient heuristic for global optimization over continuous spaces. Journal of Global Optimization, 11:341– 359. 10.1023/A:1008202821328.

Stote, R., Dejaegere, A., Kuznetsov, D., and Falquet, L. (1999). Tutorial charmm.

Webster, D. M. (2000). Protein Structure Prediction: Methods and Protocols. Humana




  • There are currently no refbacks.