臺灣博碩士論文加值系統

從胺基酸序列預測蛋白質結構在生物計算領域是一個著名的問題，解決蛋白質結構的問題是研究蛋白質最重要的工作，親疏水性模型是一個高度簡化的模型，用來表示真實世界蛋白質的特性，在親疏水性模型的蛋白質摺疊問題是要找出最低自由能的蛋白質結構。為了增進預測蛋白質結構的能力，本篇論文提出改良式蜜蜂群演算法從序列來決定蛋白質結構，我們證明我們的演算法可以成功應用在蛋白質摺疊問題在親疏水性晶格模型上，模擬結果也顯示出我們所提出的方法比起其他的演算法效能要來的好。

In the computational biology, the prediction of proteins conformation from its amino acid sequence is one of the most prominent problems, solving the problem of protein structure is the most important works for study proteins, Hydrophobic-hydrophilic (HP) model is highly simplified model; it can represent behavioral properties of real-world proteins. Protein folding problem in the HP lattice model is the problem of finding the lowest free energy conformation. In order to enhance the performance of predicting protein structure, we propose a modified artificial bee colony (MABC) algorithm to determine the protein structure from sequence. We demonstrate that our algorithm can be applied successfully to the protein folding problem based on the hydrophobic-hydrophilic lattice model. Simulation results indicate that our approach performs better than those of existing evolutionary algorithms.

摘要 I
Abstract II
Acknowledgment IV
List of Figures VII
List of Tables IX
Chapter 1 1
1.1 Motivation 1
1.2 Literature Survey 2
1.3 Thesis Organization 3
Chapter 2 5
2.1 Properties of Proteins 5
2.2 The HP Protein Model 8
2.3 Calculating the Free Energy 11
Chapter 3 13
3.1 Review the Artificial Bee Colony Algorithm 13
3.1.1 Behavior of Real Bees 14
3.1.2 Artificial Bee Colony Algorithm 18
3.2 Modified Artificial Bee Colony Algorithm 21
3.3 Numerical Simulation Results 23
Chapter 4 32
4.1 2D Protein Structure Simulation 32
4.2 3D Protein Structure Simulation 39
Chapter 5 47
Bibliography 48

List of Figures
Figure 1: A sequence of all the protein structures from primary to quaternary 7 Figure 2: An optimal conformation for the sequence “(HP)2PH(HP)2(PH)2HP(PH)2”; (a) the 2D HP lattice model; (b)the 3D HP lattice model 10
Figure 3: Behavior of honeybee foraging for nectar 17
Figure 4: The flowchart of the modified artificial bee colony algorithm 23
Figure 5: Evolution of mean best values for function 1 27
Figure 6: Evolution of mean best values for function 2 28
Figure 7: Evolution of mean best values for function 3 29
Figure 8: Evolution of mean best values for function 4 30
Figure 9: Evolution of mean best values for function 5 31
Figure 10: The schemes were represented by internal coordinates (the black cube represents the current location). 33
Figure 11: Opposite motion: the second to fifth residues motioned opposite position. 34
Figure 12: Rotation motion. The second to fifth residues will move to 35
clockwise position and form the structure as the right 35
Figure 13: Results of the structure of 8 protein sequences. 38
Figure 14: The schemes were represented by internal coordinates (the black cube VIII represents the current location). 40
Figure 15: All the residues move in the opposite direction 41
Figure 16: (a) The clockwise rotation motion; (b) the counterclockwise rotation motion 42
Figure 17: Results of the structure of 7 protein sequence 45
List of Tables
Table 1: The symbolic expression of twenty amino acids and their hydrophobic 6
Table 2: Numerical benchmark functions 24
Table 3: Results from function 1 27
Table 4: Results from function 2 28
Table 5: Results from function 3 29
Table 6: Results from function 4 30
Table 7: Results from function 5 31
Table 8: In 2D case, the residue folds direction with local search 35
Table 9: The 2D HP benchmarks 36
Table 10: Comparison of our approach with the genetic algorithm (GA), ant
colony optimization (ACO), Monte Carlo (MC), and tabu search with genetic
algorithm (GTS) 39
Table 11: In 3D case, the residue folds direction with local search 43
Table 12: The 3D HP benchmarks 43
Table 13: The simulation results obtained from the proposed algorithms
compared with the methods given in the literature 46

[1] F. E. Cohen, and J. W. Kelly, “Therapeutic Approaches to Protein-misfolding Diseases,” Nature, 426, pp. 905–909, December 2003.
[2] T.N. Bui, and G. Sundarraj, “An efficient genetic algorithm for predicting protein tertiary structures in the 2D HP model”, Proceedings of the 2005 conference on Genetic and evolutionary computation (GECCO’05), pp. 385-392, 2005
[3] N. Krasnogor, W.E. Hart, J. Smith, and D.A. Pelta, “Protein structure prediction with evolutionary lgorithms,” Proceedings of the Genetic and Evolutionary Computation Conference, Orlando, FL, Morgan Kaufmann, USA, pp. 1596–1601, July 1999.
[4] F.M. Liang and W.H. Wong, “Evolutionary Monte Carlo for protein folding simulations,” Journal of Chemical Physics, vol. 115 no. 7, pp. 3374-80, 2001.
[5] N. Krasnogor, W.E. Hart, J. Smith, and D.A. Pelta, Protein structure prediction with evolutionary algorithms,” Proceedings of the Genetic and Evolutionary Computation Conference, Orlando, FL, Morgan Kaufmann, USA, pp. 1596–1601, July 1999.
[6] A. L. Patton, W. F. Punch III, and E. D. Goodman, “A standard GA approach 49 to native protein conformation prediction”, Proceedings of the Sixth International Conference on Genetic Algorithms, pp. 574-581. Morgan Kauffman, 1995.
[7] J. Pedersen and J. Moukt, “Protein folding simulations with genetic algorithms and a detailed molecular description”, Journal of Molecular Biology, vol. 269, no. 2, pp. 240–259, June 1997.
[8] N. Krasnogor, D. Pelta, P. M. Lopez, P. Mocciola, and E. de la Canal.“Genetic algorithms for the protein folding problem: a critical view”, In C.F.E. Alpaydin, ed., Proc. Engineering of Intelligent Systems. ICSC Academic Press, 1998.
[9] A. Shmygelska, R. Anguirre-Hernandez, and H. H. Hoos, “An ant colony optimization algorithm for the 2D HP protein folding problem,” Proc. Int. Workshop Ant Algorithms, Brussels, Belgium, pp. 40–52, Sep. 2002.
[10] V. Cutello, G. Morelli, G. Nicosia, and M. Pavone, “Immune Algorithms with Aging Operators for the String Folding Problem and the Protein Folding Problem,” Evolutionary Computation in Combinatorial Optimization (EvoCOP), pp. 80–90, May. 2005.
[11] C. P. de Almeida, R.A. Gonçalves and M.R. Delgado, “A Hybrid Immune-Based System for the Protein Folding Problem,” Evolutionary 50 Computation in Combinatorial Optimization (EvoCOP), pp.13-24, 2007.
[12] A. Berger1 and K. Linderstrom-Lang, “Deuterium exchange of poly-DL-alanine in aqueous solution,” Arch. Biochem. Biophys, pp.106–118, 1957.
[13] N.G. Hunt, L.M. Gregoret and F.E. Cohen, “The origins of protein secondary effects on packing density and hydrogen bonding studied by a fast conformational search,” J. Mol. Biol. 241 (2), pp. 214–225, 1994.
[14] Lau, K. F. and K. A. Dill, “A Lattice Statistical Mechanics Model of the Conformational and Sequence Spaces of Proteins,” Macromolecules, 22(10), pp. 3986–3997, Oct. 1989.
[15] Richards, F. M., “Areas, Volumes, Packing, and Protein Structure,” Annual Review of Biophysics and Bioengineering, pp. 151–176, 1977
[16] K.A. Dill “Theory for the folding and stability of globular proteins,”Biochemistry, vol. 24 no. 6:pp.1501–9, 1985.
[17] O. Takahashi, H. Kita and S. Kobayashi, “Protein folding by a hierarchical genetic algorithm,” The 4th Int. Symp. On Artificial Life and Robotics (AROB), 1999.
[18] Y.Z. Guo, E.M. Feng and Y. Wang, “Optimal HP configurations of proteins by combining local search with elastic net algorithm,” Journal of 51 Biochemical and Biophysical Methods, vol. 70, no. 3, pp. 335-340, April 2007.
[19] E. Bonabeau, M. Dorigo, G. Theraulaz, “Swarm Intelligence: From Natural to Artificial Systems”, New York, NY: Oxford University Press, 1999.
[20] L.N. De Castro, F.J. Von Zuben, “Artificial Immune Systems. Part I. Basic Theory And Applications”, Technical Report No. Rt Dca 01/99, Feec/Unicamp, Brazil, 1999.
[21] J. Vesterstrøm, J. Riget, “Particle Swarms Extensions for improved local, multi-modal, and dynamic search in numerical optimization,” MSc.Thesis,May 2002.
[22] J. Kennedy, R. C. Eberhart, “Particle swarm optimization”, In Proceedings of the1995 IEEE International Conference on Neural Networks, Vol. 4, pp.
1942–1948, 1995.
[23] V. Tereshko, A. Loengarov, “Collective decision-making in honey bee foraging dynamics,” Comput, Inf. Syst. J. 1352-94049, 2005.
[24] A. Yap and I. Cosic, “Application of genetic algorithm for predicting tertiary structure of peptide chains”, IEEE Engineering in Medicine and Biology, vol. 2, pp. 1214, October 1999.
[25] T. Jiang, Q. Cui, G. Shi, and S. Ma, “Protein folding simulations for the 52 hydrophobic-hydrophilic model by combining tabu search with genetic algorithms”, Journal of Chemical Physics, vol. 119, no. 8, pp.4592-4596, August 2003
[26] R. Unger and J. Moult, “Genetic algorithms for protein folding simulations,” Journal of Molecular Biology, vol. 231 no.1, pp. 75-81, May 1993.
[27] C. Cotta, “Protein structure prediction using evolutionary algorithms hybridized with backtracking,” Proc of the 7th International Work-Conference on Artificial and Natural Neural Networks, Lecture Notes in Computer Science, vol. 2687, pp. 321–328, 2003.
[28] V. Cutello, G. Morelli, G. Nicosia, and M. Pavone, “Immune Algorithms with Aging Operators for the String Folding Problem and the Protein Folding Problem,” Evolutionary Computation in Combinatorial Optimization (EvoCOP), pp. 80–90, May. 2005.
[29] C. P. de Almeida, R.A. Gonçalves and M.R. Delgado, “A Hybrid Immune-Based System for the Protein Folding Problem,” Evolutionary Computation in Combinatorial Optimization (EvoCOP), pp.13-24, 2007