International Journal of Scientific & Technology Research

Home About Us Scope Editorial Board Blog/Latest News Contact Us
10th percentile
Powered by  Scopus
Scopus coverage:
Nov 2018 to May 2020


IJSTR >> Volume 9 - Issue 9, September 2020 Edition

International Journal of Scientific & Technology Research  
International Journal of Scientific & Technology Research

Website: http://www.ijstr.org

ISSN 2277-8616

Ant Colony Optimization Algorithm For Protein Folding Problem On Graphics Processing Units

[Full Text]



Bekmuratov Tulkun, Bazarov Rustam



ant colony optimization algorithm, graphics processing units, protein folding problem.



This article describes the methods of modification and parallelization of ant colony optimization algorithm for the protein folding problem. It describes in detail the software implementation of parallel ant colony optimization algorithm on the graphics processing units.



[1] K.A. Dill, “Theory for the folding and stability of globular Proteins“, J. Biochemistry, vol. 24, pp. 1501–1509, 1985. doi: http://dx.doi.org/10.1021/bi00327a032.
[2] P. Crescenzi, D. Goldman, C. Papadimitriou, A. Piccolboni, M. Yannakakis, “On the complexity of protein folding“, Computation Biology vol. 5 no. 3, pp. 423-465, 1998, doi: http://dx.doi.org/10.1089/cmb.1998.5.423
[3] A. Shmygelska, H.H. Hoos, An ant colony optimisation algorithm for the 2D and 3D hydrophobic polar protein folding problem Bmc Bioinformatics vol. 6 no. 30, 2005, doi: http://dx.doi.org/10.1186/1471-2105-6-30
[4] A.S. Kolaskar, S. Sawant, “Prediction of conformational states of amino acids using a Ramachandran plot“, International Journal of Peptide and Protein Research vol. 47(1-2), pp. 110-116, 1996, doi: http: //dx.doi.org/10.1186/1471-2105-6-30
[5] C. Levinthal. “How to fold graciously“, J. Mossbaun spectroscopy in Biological Systems Proceedings, pp. 22-24, 1969.
[6] A.V. Finkelstein, O.B. Ptitsyn, Protein physics. San Diego: Acadimic Press.,354P, 2002.
[7] A.V. Makeev, The basics of biology [Osnovy biologii]. Moscow: Mir. 235 p, 1997. (in Russian)
[8] A.M. Malyshenko, The mathematical foundations of systems theory [Matematicheskie osnovy teorii system] Tomsk: Polytechnic University Publ., 364 p. (in Russian)
[9] B. Alberts, A. Johnson, Lewis J. Molecular Biology of the Cell. New York Garland Science Available at: https://www.ncbi.nlm.nih.gov/books/NBK26830, 2002.
[10] S. Istrail, F. Lam. Combinatorial algorithms for protein folding in lattice models: a survey of mathematical results Commun. Inf. Syst. 9(4):303–346 doi: http://dx.doi.org/ 2009
[11] F.M. Richards. Areas, volumes, packing and protein structure Annual Review of Biophysics and Bioengineering 6(1):151-176 doi: http://dx.doi.org/10.1146/annurev.bb.06.060177.001055 1977
[12] K.A. Dill. Dominant forces in protein folding. Biochemistry 29(31):7133-7155 doi: http://dx.doi.org/10.1021/bi00483a001, 1990.
[13] M. Mann, S. Will, R. Backofen. CPSP-tools - Exact and complete algorithms for high-throughput 3D lattice protein studies/ Bmc Bioinformatics 9(1):230 doi: http://dx.doi.org/10.1186/1471-2105-9-230, 2008.
[14] C. Thachuk, A. Shmygelska, H.H. Hoos. 2007. A replica exchange Monte Carlo algorithm for protein folding in the HP model Bmc Bioinformatics 8:342 doi: http://dx.doi.org/10.1186/1471-2105-8-342
[15] A.P. Karpenko. Modern search optimization algorithms. Algorithms, inspired by nature [Sovremennye algoritmy poiskovoy optimizatsii. Algoritmy, vdokhnovlennye prirodoy]. Moscow.: Bauman MSTU Publ., 446 p., 2014. (in Russian).
[16] S. Gordon. The self-avoiding walk: a brief survey. Proceednigs of the 33rd SPA Conference. Surveys in Stochastic Processes. Berlin: European Math. Society. 181–199, 2010.
[17] T. Thalheim, D. Merkle, M. Middendorf. Protein folding in the HP-model solved with a hybrid population based ACO Algorithm. IAENG International Journal of Computer Science 35(3):201-300 doi: http://dx.doi.org/ 2008.
[18] Xiao-Min Hu, Jun Zhang, Yun Li. Orthogonal methods based ant colony search for solving continious optimization problems. Journal of Computer Science and Technology 23(1):2-18 doi: http://dx.doi.org/10.1007/s11390-008-9111-5 2008.
[19] Stuzle T., Doringo M. A short convergence proof for a class of ACO algorithms. IEEE Transactions on Evolutionary Computation 6(4):358-365 doi: http://dx.doi.org/10.1109/TEVC.2002.802444 2002.
[20] L. Carvelli , G. Sebastiani. Some issues of aco algorithm convergence Ant Colony Optimization - Methods and Applications 6(4):358-365 doi: http://dx.doi.org/10.5772/14510 2011
[21] D. Chu, M. Till, A. Zomaya. Parallel ant colony optimization for 3D protein structure prediction using the HP lattice model Proceedings 19th IEEE International Parallel and Distributed Processing Symposium vol. 7. Washington: IEEE Computer Society. 193. 2005.
[22] Delisle, P., Krajecki M., Gravel M., Gagne C 2005. Parallel implementation of an ant colony optimization metaheuristic with OpenMP Proceedings of the 3rd European Workshop on OpenMP (EWOMP’01). Barselona: IEEE Computer Society. 193.
[23] Wen-mei W. Hwu. GPU computing gems emerald edition. San Francisco: Morgan Kaufmann Publishers Inc., CA, USA, 886 p. 2011.
[24] T.F. Bekmuratov, D.T. Muhamedieva, R.K. Bazarov, D.D. Ahmedov. Parallel ant colony optimization algorithm [Parallelnyi muravyinyi algoritm optimizacii]. Information and energetics problems [Problemy informatiki i energetiki] 1-2:11–15. doi: http://dx.doi.org/. (In Russian) 2014.
[25] T. F. Bekmuratov, R.K. Bazarov, D.K. Bazarov. The implementation of ant colony optimization algorithm for the study of protein folding problem in distributed systems by the software agents Problems of Computational and Applied Mathematics [Realizaciya muravyinogo algoritma foldinga belkov metodami programmnyh agentov v raspredelennyh systemah]. [Problemy vychislitelnoy i prikladnoy matematiki] 2(8):103–113. 2017doi: http://dx.doi.org/. (In Russian)
[26] R.K. Bazarov. The solving of protein folding problem in distributed computing grid-systems [Reshenie zadachi foldinga belkov v raspredelennyh vychislitelnyh grid-sistemach]. 6th Symposium (International) “New Energy Saving Subsoil Technologies and the Increasing of the Oil and Gas Impact” Proceedings of Republic scientific and technical conference, Tashkent pp. 130-131, mart 10-11, 2016. (In Russian)
[27] V.P. Bruskov, D.K. Bazarov. Grid infrastructure with support for computing on GPUs [Grid-infrastructura s podderjkoy vychisleniy na graficheskih processorah]. “Computer science: problems, methodology, technologies“, Proceedings of XVII international scientific and methodological conference, Voronej, pp 190-195, 2017.
[28] CUDA Zone. Available at: https://developer.nvidia.com/cuda-zone