Ayrık Yapay Arı Kolonisi Algoritması ile Protein Yapısı Tahmini

Proteinlerin yerine getirdiği görevler doğal durumları olarak adlandırılan üçüncül yapıları ile alakalıdır. Günümüzde birçok proteinin birincil yapı olarak adlandırılan dizilimleri bilinmekle beraber işlevlerini açıklayan üçüncül yapıları bilinmemektedir. Ele alınan dizide bulunan amino asitlerin üçüncül yapı oluşumuna yol açan özelliklerinin kullanılarak üçüncül yapılarının tahmin edilmesi proteinlerin gerçek doğasının tam anlaşılması ve bilimsel olarak kullanılmasının önünü açacaktır. Proteinlerin doğal yapılarına katlanması ile ilgili yapılan çalışmalarda en düşük serbest enerji düzeyinin elde edilmesi eğilimi tespit edilmiştir. Serbest enerji düzeylerini hesaplamada, sudan kaçma özelliği yoğun olarak kullanılmaktadır. Bu özelliğe göre sınıflandırılan amino asitleri temel alan HP modeli basitliği ve gerçekçiliği ile dikkat çekmektedir. Çalışmamızda HP modelinin doğadaki protein davranışı incelenerek geliştirilmiş bir türü olan Üç Boyutlu Hidrofobik Polar Yan Zincir modeli kullanılmıştır. Aday protein modellerinin oluşturulmasında arıların besin arama davranışlarını modelleyen Yapay Arı Kolonisi Algoritması temelli oluşturulan ayrık model önerilmiştir. Benzer çalışmalarda kullanılan başarımların test edildiği örnek dizilerde daha az maliyetle iyi sonuçlar alınmıştır.

Anahtar Kelimeler:

Biyoenformatik, Protein Yapı Tahmini; Yapay Arı Koloni Algoritması; Ayrık Optimizasyon

Protein Structure Prediction with Discrete Artificial Bee Colony Algorithm

Tasks that proteins perform are directly related to native conditions named their tertiary structure. Although arrays of numerous proteins’ primary structure are known, tertiary structures those explain their functions are not well defined. Studies on translation of proteins to their tertiary structure found tendency of provision of minimal free energy level. HP model, used in calculation of free energy levels and based on the amino acids grouped by their hydrophobic characteristics, is standing out with its simplicity and authenticity. In this paper, three-dimensional hydrophobic side chain model that was developed by investigation of the protein behavior of HP model in nature was used. A new discrete model based on Artificial Bee Colony Algorithm that is simulating the foraging behaviors of bees is proposed to form the protein tertiary structures. The success of proposed model is tested on widely used benchmark protein arrays and compared with the results of similar methods from literature.

PDF

___

[1] M. Zvelebil and J. Baum, Understanding bioinformatics. New York: Garland Science, 2008.
[2] R. Unger and J. Moult, "Genetic algorithms for protein folding simulations.," J. Mol. Biol., vol. 231, pp. 75-81, 1993.
[3] K. A. Dill, "Theory for the folding and stability of globular proteins.," Biochemistry, vol. 24, no. 6, pp. 1501-1509, 1985.
[4] Y. Karami, M. Fathy, H. Khakzad, H. Shirazi, and S. Arab, "Protein structure prediction using bioinspired algorithm: A review," AISP 2012 - 16th CSI Int. Symp. Artif. Intell. Signal Process., no. 978, pp. 201-206, 2012.
[5] J. Ye, "A review of artificial intelligence techniques applied to protein structure prediction," Simon Fraser University, 2007.
[6] M. Paluszewski, "Algorithms for Protein Structure Prediction," Københavns Universitet, Det Natur-og Biovidenskabelige Fakultet, Biologisk Institut, 2008.
[7] X. Zhang, T. Wang, H. Luo, J. Y. Yang, Y. Deng, J. Tang, and M. Q. Yang, "3D protein structure prediction with genetic tabu search algorithm," BMC Syst. Biol., vol. 4 Suppl 1, no. Suppl 1, p. S6, 2010.
[8] T. Jiang, Q. Cui, G. Shi, and S. Ma, "Protein folding simulations of the hydrophobic-hydrophilic model by combining tabu search with genetic algorithms," J. Chem. Phys., vol. 119, no. 8, p. 4592, 2003.
[9] X. Chen, M. Lv, L. Zhao, and X. Zhang, "An Improved Particle Swarm Optimization for Protein Folding Prediction," Int. J. Inf. Eng. Electron. Bus., vol. 3, no. 1, pp. 1-8, Feb. 2011.
[10] M. Garza-Fabre, E. Rodriguez-Tello, and G. Toscano-Pulido, "Comparative Analysis of Different Evaluation Functions for Protein Structure Prediction Under the HP Model," J. Comput. Sci. Technol., vol. 28, no. 5, pp. 868-889, 2013.
[11] C.-J. Lin and S.-C. Su, "Protein 3 D HP model folding simulation using a hybrid of genetic algorithm and particle swarm optimization," Int. J. Fuzzy Syst., vol. 13, no. 2, pp. 140-147, 2011.
[12] C. Chira, "A Hybrid Evolutionary Approach to Protein Structure Prediction with Lattice Models," Proteins, pp. 2300-2306, 2011.
[13] C. M. Johnson and A. Katikireddy, "A Genetic Algorithm with Backtracking for Protein structure Prediction," GECCO'06,July, vol. 8, p. -12, 2006.
[14] R. O. R. O. Day, J. B. Zydallis, G. B. G. B. Lamont, and R. Pachter, "Solving the protein structure prediction problem through a multiobjective genetic algorithm," Nanotechnology, vol. 2, pp. 32-35, 2002.
[15] H. A. A. H. A. A. Bahamish, R. Abdullah, and R. A. A. Salam, "Protein Tertiary Structure Prediction Using Artificial Bee Colony Algorithm," 2009 Third Asia Int. Conf. Model. Simul., 2009.
[16] C.-J. C. Lin and S. S.-C. Su, "Using an efficient artificial bee colony algorithm for protein structure prediction on lattice models," Int. J. Innov. Comput. Inf. Control, vol. 8, no. 3, pp. 2049-2064, 2012.
[17] A. G. Citrolo and G. Mauri, "A Hybrid Monte Carlo Ant Colony Optimization Approach for Protein Structure Prediction in the HP Model," Electron. Proc. Theor. Comput. Sci., vol. 130, pp. 61-69, 2013.
[18] B. Maher, A. Albrecht, M. Loomes, X.-S. Yang, and K. Steinhöfel, "A Firefly-Inspired Method for Protein Structure Prediction in Lattice Models," Biomolecules, vol. 4, no. 1, pp. 56-75, 2014.
[19] F. L. Custódio, H. J. C. Barbosa, and L. E. Dardenne, "A multiple minima genetic algorithm for protein structure prediction," Appl. Soft Comput. J., vol. 15, pp. 88-99, 2014.
[20] L. F. Nunes, L. C. Galvão, H. S. Lopes, P. Moscato, and R. Berretta, "An integer programming model for protein structure prediction using the 3D-HP side chain model," Discret. Appl. Math., vol. 198, pp. 206-214, 2016.
[21] M. Garza-Fabre, E. Rodriguez-Tello, and G. Toscano-Pulido, "Constraint-handling through multi-objective optimization: The hydrophobic-polar model for protein structure prediction," Comput. Oper. Res., vol. 53, pp. 128-153, 2015.
[22] J. G. P. Jin and H. Xu, "3D protein structure prediction of influenza A virus based on optimization genetic algorithm," vol. 27, no. 3, pp. 735-739, 2014.
[23] A. Perdomo-Ortiz, N. Dickson, M. Drew-Brook, G. Rose, and A. Aspuru-Guzik, "Finding low-energy conformations of lattice protein models by quantum annealing," Sci. Rep., vol. 2, pp. 1-7, 2012.
[24] A. Lesk, Introduction to Bioinformatics. Oxford University Press, 2014.
[25] C. B. Anfinsen, "Principles that govern the folding of protein chains," Science, vol. 181, no. 96, pp. 223-230, 1973.
[26] K. A. Dill, "Dominant forces in protein folding.," Biochemistry, vol. 29, no. 31, pp. 7133-7155, 1990.
[27] B. Honig, "Protein folding: from the levinthal paradox to structure prediction.," J. Mol. Biol., vol. 293, no. 2, pp. 283-293, 1999.
[28] R. König and T. Dandekar, "Refined Genetic Algorithm Simulations to Model Proteins," J. Mol. Model., vol. 5, no. 12, pp. 317-324, 1999.
[29] C. M. V. Benitez and H. S. Lopes, "A parallel genetic algorithm for protein folding prediction using the 3D-HP Side Chain model," in 2009 IEEE Congress on Evolutionary Computation, 2009, pp. 1297-1304.
[30] D. Karaboga, "An idea based on Honey Bee Swarm for Numerical Optimization," Tech. Rep. TR06, Erciyes Univ., no. TR06, p. 10, 2005.
[31] C. Ozturk, E. Hancer, and D. Karaboga, "Improved clustering criterion for image clustering with artificial bee colony algorithm," Pattern Anal. Appl., vol. 18, no. 3, pp. 587-599, 2015.
[32] C. Ozturk, E. Hancer, and D. Karaboga, "Dynamic clustering with improved binary artificial bee colony algorithm," Appl. Soft Comput., vol. 28, pp. 69-80, 2015.
[33] C. Ozturk, E. Hancer, and D. Karaboga, "A novel binary artificial bee colony algorithm based on genetic operators," Inf. Sci. (Ny)., vol. 297, pp. 154-170, 2015.
[34] D. Ye and Z. Chen, "A new approach to minimum attribute reduction based on discrete artificial bee colony," Soft Comput., pp. 1893-1903, 2014.
[35] I. Ribas, R. Companys, and X. Tort-Martorell, "An efficient Discrete Artificial Bee Colony algorithm for the blocking flow shop problem with total flowtime minimization," Expert Syst. Appl., vol. 42, no. 15-16, pp. 37-41, 2015.
[36] Y.-Y. Han, D. Gong, and X. Sun, "A discrete artificial bee colony algorithm incorporating differential evolution for the flow-shop scheduling problem with blocking," Eng. Optim., vol. 47, no. 7, pp. 927-946, 2015.
[37] Z. Cui and X. Gu, "An improved discrete artificial bee colony algorithm to minimize the makespan on hybrid flow shop problems," Neurocomputing, vol. 148, pp. 248-259, 2015.
[38] D. Karaboga and S. Aslan, "A discrete artificial bee colony algorithm for detecting transcription factor binding sites in DNA sequences.," Genet. Mol. Res., vol. 15, no. 2, pp. 1-11, 2016.
[39] Y. Huo, Y. Zhuang, J. Gu, S. Ni, and Y. Xue, "Discrete gbest-guided artificial bee colony algorithm for cloud service composition," Appl. Intell., pp. 661-678, 2014.
[40] T. Batbat, "Protein Yapısının Yapay Arı Kolonisi Algoritması Ile Tahmini," Erciyes Üniversitesi, 2014.
[41] C. M. V. Benitez and H. S. Lopes, "Hierarchical Parallel Genetic Algorithm applied to the threedimensional HP Side-chain Protein Folding Problem," in 2010 IEEE International Conference on Systems, Man and Cybernetics, 2010, pp. 2669- 2676.
[42] R. Unger and J. Moult, "Genetic Algorithm for 3D Protein Folding Simulations," in Proceedings of the 5th International Conference on Genetic Algorithms, 1993, pp. 581-588.
[43] C. Vargas Benítez, H. S. Lopes, C. M. V. Benítez, H. S. Lopes, C. Vargas Benítez, and H. S. Lopes, "Parallel Artificial Bee Colony Algorithm Approaches for Protein Structure Prediction Using the 3DHP-SC Model," in Intelligent Distributed Computing IV SE - 27, vol. 315, Springer, 2010, pp. 255-264.