臺灣博碩士論文加值系統

疏水性和極性模型(HP model)是常用的蛋白質摺疊結構預測的方式。本研究設計了混和粒子群優化算法，是結合粒子群最佳化算法 （Particle swarm optimization）與禁忌搜索算法 (Tabu search)，並針對此研究改良Tabu搜尋的方式。其中PSO擁有良好的全域搜尋能力，而tabu search加強區域搜尋。通過預測28個已知的蛋白質結構，我們在HP model的蛋白質折疊結構預測下，評估算法的性能。PSO-Tabu與其他算法相比在短的氨基酸序列或長的氨基酸序列預測中都表現出高性能，高穩定性。PSO-Tabu在近乎所有的胺基酸序列預測中都能找到最佳結構。證明PSO-Tabu能在使用HP model預測蛋白質結構時可以有效摺疊出近似於真實蛋白質結構。

The hydrophobic-polar (HP) model is commonly used for predicting protein folding structures and hydrophobic interactions. This study developed a particle swarm optimization (PSO)-based algorithm combined with local search algorithms; specifically, the PSO algorithm (which can execute global search processes) was combined Tabu search algorithms, yielding the proposed PSO-Tabu algorithm. By using 28 known protein structures, we evaluated the performance of the PSO-Tabu algorithm in predicting protein folding in the HP model. The proposed PSO-Tabu algorithm exhibited favorable performance in predicting both short and long amino acid sequences with high reproducibility and stability, compared with many reported algorithms. The PSO-Tabu algorithm yielded optimal solutions for all the predicted protein folding structures. All PSO-Tabu-predicted protein folding structures possessed a hydrophobic core that is similar to normal protein folding.

摘要 iii
ABSTRACT iv
ACKNOWLEDGEMENT v
I. INTRODUCTION 1
1.1 Background 1
1.2 Motivation 2
1.3 Purpose 2
II. RELATED WORKS 4
2.1 Proteins 4
2.2 HP model 4
III. IMPROVED OPTIMAL PREDICTION ALGORITHM 6
3.1 PSO algorithm 6
3.1.1 Encoding 7
3.1.2 Particle Initialization 8
3.1.3 Fitness calculation 10
3.1.4 The population topology 12
3.1.5 Updating pbest and lbest 12
3.1.6 Updating particles 13
3.2 Tabu search 14
3.2.1 Part 1 of search 14
3.2.2 Part 2 of search 15
3.2.3 Tabu list 16
3.3 Parameter settings 18
III. RESULT 19
4.1 Data set 19
4.2 Comparison PSO based on difference topology 21
4.3 Comparison between the prediction accuracies of PSO-Tabu and other algorithms under the square lattice model of the sequence 1 22
4.4 Comparison between the prediction accuracies of PSO-Tabu and other algorithms under the triangular lattice model of the sequence 1 28
4.5 Comparison between the prediction stability of PSO-Tabu and other algorithms under the triangular lattice model of the sequence 1 30
4.6 Comparison of the best prediction results among several algorithms of the sequence 2 35
4.7 The success rate of the best structure prediction of the sequence 2 37
4.8 Mean of the best fitness 39
4.9 Visualization of the best prediction results 41
IV. DISCUSSION 53
5.1 The difference of local search addition 53
5.2 Exploring the design of tabu search 56
5.3 Discuss the data results 61
V. CONCLUSION 63
VI. FUTURE WORKS 64
REFERENCES 65
PUBLICATION LIST 68

[1]C. Anfinsen, "The formation and stabilization of protein structure," Biochemical Journal, vol. 128, pp. 737, 1972.
[2]K. A. Dill, "Theory for the folding and stability of globular proteins," Biochemistry, vol. 24, pp. 1501-1509, 1985.
[3]P. Crescenzi, D. Goldman, C. Papadimitriou, A. Piccolboni, and M. Yannakakis, "On the complexity of protein folding," Journal of computational biology, vol. 5, pp. 423-465, 1998.
[4]N. D. Jana and J. Sil, "Protein structure prediction in 2D HP lattice model using differential evolutionary algorithm," in Proceedings of the International Conference on Information Systems Design and Intelligent Applications 2012 (INDIA 2012) held in Visakhapatnam, India, January 2012, 2012, pp. 281-290.
[5]A. Bechini, "On the characterization and software implementation of general protein lattice models," PLoS One, vol. 8, p. e59504, 2013.
[6]F. Glover, "Tabu search-part I," ORSA Journal on computing, vol. 1, pp. 190-206, 1989.
[7]R. Mendes, J. Kennedy, and J. Neves, "The fully informed particle swarm: simpler, maybe better," IEEE transactions on evolutionary computation, vol. 8, pp. 204-210, 2004.
[8]J. Kennedy, "Particle swarm optimization," in Encyclopedia of Machine Learning, ed: Springer, 2010, pp. 760-766.
[9]N. D. Jana and J. Sil, "Protein structure prediction in 2D HP lattice model using differential evolutionary algorithm," Proceedings of the International Conference on Information Systems Design and Intelligent Applications (India 2012), vol. 132, pp. 281-290, 2012.
[10]E. García-Gonzalo and J. Fernández-Martínez, "A brief historical review of particle swarm optimization (PSO)," J Bioinf Intell Control, vol. 1, pp. 3-16, 2012.
[11]E. García-Gonzalo and J. Fernández-Martínez, "A brief historical review of particle swarm optimization (PSO)," Journal of Bioinformatics and Intelligent Control, vol. 1, pp. 3-16, 2012.
[12]M. Clerc and J. Kennedy, "The particle swarm-explosion, stability, and convergence in a multidimensional complex space," IEEE transactions on Evolutionary Computation, vol. 6, pp. 58-73, 2002.
[13]J. Kennedy, "Particle swarm optimization," in Encyclopedia of machine learning, ed: Springer, 2011, pp. 760-766.
[14]T. Jiang, Q. Cui, G. Shi, and S. Ma, "Protein folding simulations of the hydrophobic–hydrophilic model by combining tabu search with genetic algorithms," The Journal of chemical physics, vol. 119, pp. 4592-4596, 2003.
[15]M. K. Islam, M. Chetty, and M. Murshed, "Novel local improvement techniques in clustered memetic algorithm for protein structure prediction," in IEEE Congress on Evolutionary Computation (CEC), 2011, pp. 1003-1011.
[16]N. Krasnogor and J. Smith, "A memetic algorithm with self-adaptive local search: TSP as a case study," in GECCO, 2000, pp. 987-994.
[17]J. Santos and M. Diéguez, "Differential evolution for protein structure prediction using the HP model," in Foundations on Natural and Artificial Computation. vol. 6686, J. M. Ferrández, J. R. Á. Sánchez, F. d. l. Paz, and F. J. Toledo, Eds., ed Berlin: Springer, 2011, pp. 323-333.
[18]J. Santos and M. Diéguez, "Differential evolution for protein structure prediction using the HP model," in International Work-Conference on the Interplay Between Natural and Artificial Computation, 2011, pp. 323-333.
[19]K. A. Dill, "Theory for the folding and stability of globular proteins," Biochemistry, vol. 24, pp. 1501-9, 1985.
[20]R. Unger and J. Moult, "Genetic algorithms for protein folding simulations," Journal of molecular biology, vol. 231, pp. 75-81, 1993.
[21]N. Krasnogor, B. Blackburne, E. K. Burke, and J. D. Hirst, "Multimeme algorithms for protein structure prediction," in International Conference on Parallel Problem Solving from Nature, 2002, pp. 769-778.
[22]M. T. Hoque, M. Chetty, and L. S. Dooley, "A hybrid genetic algorithm for 2D FCC hydrophobic-hydrophilic lattice model to predict protein folding," in AI 2006: Advances in Artificial Intelligence, ed: Springer, 2006, pp. 867-876.
[23]H.-J. Böckenhauer, A. Z. M. D. Ullah, L. Kapsokalivas, and K. Steinhöfel, "A local move set for protein folding in triangular lattice models," in Algorithms in Bioinformatics, ed: Springer, 2008, pp. 369-381.
[24]S.-C. Su, C.-J. Lin, and C.-K. Ting, "An effective hybrid of hill climbing and genetic algorithm for 2D triangular protein structure prediction," Proteome science, vol. 9, pp. S19, October 14 2011.
[25]J. Smith, "The co-evolution of memetic algorithms for protein structure prediction," in Recent advances in memetic algorithms, ed: Springer, 2005, pp. 105-128.
[26]M. Michael Gromiha and L.-T. Huang, "Machine learning algorithms for predicting protein folding rates and stability of mutant proteins: Comparison with statistical methods," Current Protein and Peptide Science, vol. 12, pp. 490-502, 2011.
[27]Y. W. Li, T. Wüst, and D. P. Landau, "Monte Carlo simulations of the HP model (the “Ising model” of protein folding)," Computer physics communications, vol. 182, pp. 1896-1899, 2011.
[28]L. Mirny and E. Shakhnovich, "Protein folding theory: from lattice to all-atom models," Annual review of biophysics and biomolecular structure, vol. 30, pp. 361-396, 2001.
[29]A. Shmygelska, R. Aguirre-Hernandez, and H. H. Hoos, "An ant colony optimization algorithm for the 2D HP protein folding problem," in International Workshop on Ant Algorithms, 2002, pp. 40-52.
[30]M. K. Islam and M. Chetty, "Novel memetic algorithm for protein structure prediction," in Australasian Joint Conference on Artificial Intelligence, 2009, pp. 412-421.
[31]M. Chen and W.-Q. Huang, "A branch and bound algorithm for the protein folding problem in the HP lattice model," Genomics Proteomics Bioinformatics, vol. 3, pp. 225-30, 2005.
[32]C. Rego, H. Li, and F. Glover, "A filter-and-fan approach to the 2D HP model of the protein folding problem," Annals of Operations Research, vol. 188, pp. 389-414, 2011.
[33]K. W. DeRonne and G. Karypis, "Effective optimization algorithms for fragment-assembly based protein structure prediction," Journal of bioinformatics and computational biology, vol. 5, pp. 335-352, 2007.
[34]X. Lin and X. Zhang, "Protein structure prediction with local adjust tabu search algorithm," BMC bioinformatics, vol. 15, pp. S1, 2014.