摘要
蛋白质的空间构象问题是计算生物研究中涉及的一类重要问题。本文研究蛋白质的氨基酸序列在空间中如何排列构成它的基态的问题,即蛋白质折叠问题。本文采用广受欢迎的格点模型(HP模型)为蛋白质折叠问题的模型,并针对二维HP模型和三维HP模型,分别利用磁滞优化算法(HO)和极值优化算法研究了蛋白质折叠问题。
首先,本文首次把磁滞优化算法(HO)应用到二维HP模型的蛋白质折叠问题中。HO算法是一种基于物理的优化算法,最早是由G.Zar a nd等人于2002年针对旋转玻璃模型所提出的。算法的核心在于利用交流去磁过程达到优化的效果。具体地说,通过在模型中引入外部场强度,随着外部场强度方向的依次交替变化,逐步优化目标函数,使其最终趋于最优解。HO算法的创始人曾把它应用到100个城市的旅行商问题求解中,并分析了该算法的有效性,本文首次把HO算法应用到蛋白质折叠问题中,针对二维的HP模型,HO算法对于氨基酸序列长度小于85的蛋白质折叠问题求解十分有效,能较快找到最优构象。
其次,本文扩展了极值优化算法,把它成功地应用到更为复杂的三维蛋白质折叠优化问题中。对于三维的HP模型,找寻最优解更加复杂,很多算法比如遗传算法,蒙特卡罗算法等近年来也在解决二维HP模型的蛋白质折叠问题之后,尝试扩展到解决三维HP模型的优化问题。相比而言,极值优化算法是一种收敛速度快,局部搜索能力强,且设计简单容易实现的优化算法。极值优化算法应用到二维蛋白质折叠优化问题中,对于短序列的蛋白质优化问题呈现出了很好的效果。本文则在此基础上把它应用到更为复杂的三维蛋白质折叠优化问题中,通过对局部适值差的分子改变空间位置,逐步调整氨基酸分子在空间分布状态,最终折叠成最低能量构型。
最后,本文对全文做了总结,并对未来的研究做了展望。
The problem of the protein's conformational space is a very important subject in computational biology. This thesis studies on the problem about how fold the amino acids'sequences to its native state, which is called protein folding problem. A popular lattice model (HP model), is exploited in this thesis as the basic model of protein folding problem. For 2D and 3D HP model, hysteretic optimization (HO) algorithm and extremal optimization (EO) algorithm are used respectively to study the protein folding problem.
Firstly, hysteretic optimization algorithm (HO) is applied for the first time in this thesis to the study of 2D-HP model of protein folding problems. The hysteretic optimization (HO) is an algorithm based on physics and was originally proposed by G. Zarand et al for spin glass model in 2002. The initiative of HO solution is that it uses the AC-demagnetization process to achieve the purpose for system optimization. Specifically, the objective function is optimized step by step by introducing an external field into the model and alternately switching its direction and it finally approaches to the optimal solution. The initiator of HO, G. Zarand, once exploited it to solve a travelling salesman problem (TSP) with 100 cities and discussed its efficiency. In this study, we successfully apply HO to protein folding problem with 2D-HP model and the simulation results show that HO is efficient and easy to get the optimal conformation when the protein's amino acids sequence's length is less than 85.
Then, the extremal optimization (EO) algorithm is extended and successfully exploited in this thesis to study the 3D-HP model of the protein folding problem. In the framework of 3D-HP model, it is much complicated to get the optimal solution of the protein folding problem. In recent years, with the successful application in the 2D-HP model of the protein folding problem, many algorithms such as genetic algorithm, Monte Carlo algorithm, etc. have been trying to solve the protein folding problem with 3D- HP model. The extremal optimization (EO) algorithm is a fast convergent algorithm, good for local searching and easy to design and implement. When applying EO to 2D protein folding problem, it shows a good result for short sequences. Based on the reported results, EO is applied in this thesis to more complex 3D protein folding problem by changing the space position of the molecule whose local fitness is poor, thereby adjusting the amino acids'space arrangement state and finally folding to a proper structure with the least energy.
The conclusion and the future work are discussed in the end of the paper.
引文
[1]C. B. Anfinsen, Principles that govern the folding of protein chains [J]. Science, 1973,181(4096):223-227.
[2]黄文奇,基于模拟退火算法的蛋白质折叠问题求解,计算机工程与应用,2005,41(7).
[3]Ken A. Dill, S.Banu Ozkan, M.Scott Shell,Thomas R. Weikl, The Protein Folding Problem, Annu. Rev. Biophys 37 (2008) 289-316.
[4]张晓龙,程文,基于改进的禁忌搜索的蛋白质三维结构预测,计算机工程,Vo1.35,No.4,31-34.
[5]Stillinger F H,Toy Model for Protein Folding[J], Phy. Rev.,1993, 48(2):1469-1477.
[6]Bonnie Berger and Tom Leighton, Protein folding in the hydrophobic hydrophilic (HP) model is np-complete. Journal of Computational Biology, 1998,5(1):27-40.
[7]W. Xie, Y. F. Wang, Three-Dimensional Computer Simulation for Protein Folding, Journal of Shanghai University (Natural Science), Vol.6, No.6, (2000).
[8]Chris Thachuk, Alena Shmygelska and Holger H Hoos, A replica exchange Monte Carlo algorithm for protein folding in the HP model, BMC Bioinformatics (2007), 8:342.
[9]李婷婷,面向蛋白质折叠结构问题的粒子群优化算法的改进研究,武汉科技大学硕士学位论文,2008.
[10]Holland, J.H. Adaptation in Natural and Artificial Systems. Ann Arbor MI: University of Michigan Press,1975.
[11]周明,孙树栋。遗传算法原理及应用,北京,国防工业出版社,1999.
[12]Kennedy J, Eberhart R. Particle Swarm Optimization[C]. In:IEEE International Conference on Neural Networks, Perth, Australia,1995:(1942-1948).
[13]Eberhart R, Kennedy J, A New Optimizer Using Particle Swarm Theory[C]. In: Proc of the Sixth International Symposium on Micro Machine and Human Science, Nagoya, Japan,1995:39-43.
[14]李爱国,覃征,粒子群优化算法,计算机工程与应用,2002,38(21):1-3.
[15]杨维,李歧强,粒子群优化算法综述,中国工程科学,2,004,Vol.6,No.5,87-94.
[16]Krikpa Trick S, Gelett C, Veechi M, Optimization by simulated annealing [J]. Science,1983,220(8):671-680.
[17]张波,叶家玮,胡郁葱,模拟退火算法在路径优化问题中的应用,中国公路学报,2004,Vol.17,No.1,79-81.
[18]Prof. David Gossard, Retrieving and Viewing Protein Structures from the Protein Data Base, MIT course,2003.
[19]M. J. Sternberg, Protein Structure Prediction, OIRL Press at Oxford University Press,1996.
[20]S. Sun, Reduced representation model of protein structure prediction:statistical potential and genetic algorithm, Protein Sci.,2:762-785,1993.
[21]J. U. Bowie and D. Eisenberg. An evolutionary approach to folding small a-helical proteins that uses sequence information and an empirical guiding fitness function, Proc. Natl. Acad. Sci. USA,91:4436-4440,1994.
[22]Bastolla U., H. Frauenkron, E. Gestner, P. Grassberger, and W. Nadler, Testing a new Monte Carlo algorithm for the protein folding problem, Proteins:Structure, Function & Genetics 32(1):52-66,1998.
[23]Chikenji G., M. Kikuchi, and Y. Iba, Multi-Self-Overlap Ensemble for protein folding:ground state search and thermodynamics, Phys. Rev. Let.83(9): 1886-1889,1999.
[24]Liang F., and W. H. Wong, Evolutionary Monte Carlo for protein folding simulations, J. Chem. Phys.115(7):3374-3380,2001.
[25]Ramakrishnan R., B. Ramachandran, and J. F. Pekny, A dynamic Monte Carlo algorithm for exploration of dense conformational spaces in heteropolymers, J. Chem. Phys.106(6):2418-2424,1997.
[26]林晓丽,万程鹏,基于AB非格模型和遗传退火算法的蛋白质折叠预测,科技创业月刊,第七期,2008,140-143.
[27]周洪斌,吕强,粒子群优化算法应用研究,苏州大学硕士学位论文,2009.
[28]张红娟,唐焕文,基于非格点模型的蛋白质结构预测研究,大连理工大学,硕士学位论文,2005.
[29]刘玲玉,蛋白质折叠的研究进展,内蒙古农业科技,2003(S2):50-54.
[30]G.Zar a nd, F. P a zm a ndi, K.F. P a 1, GT. Zim a nyi, Using Hysteresis for Optimization, Phys. Rev. Lett.89 (2002) 150201.
[31]K.F. Pal, Hysteretic optimization, faster and simpler, Physica A 360 (2006) 525-533.
[32]Hengyun Lu, Genke Yang, Extremal Optimization for protein folding simulations on the lattice, Computers and Mathematics with Applications 57 (2009) 1855-1861.
[33]程念华,黄文奇,求解蛋白质折叠问题的改进PERM算法,华中科技大学硕士学位论文,2005.
[34]H. P. Hsu, V. Mehra, W. Nadler, etal. Growth Algorithms for Lattice Heteropolymers at Low Temperatures Journal of Chemical Physics,2003,118(1): 444-452.
[35]H. P. Hsu, V. Mehra, W. Nadler,etal. A Growth-based optimization algorithm for lattice heteropolymers. Physical Review E,2003,68(2):1007-1011.
[36]黄文奇,崔茂林,求解蛋白质折叠构型预测问题的PERM改进算法,微计算机应用,2004,25(3).
[37]K.F. Pal, Hysteretic optimization for traveling salesman problem, Physica A 329 (2003) 287-297.
[38]K.F. Lau, K.A. Dill, A lattice statistical mechanics model of the conformation and sequence space of proteins, Macromolecules 22 (1989)3986-3997.
[39]Boettcher, S., Percus, A.G. Extremal optimization:methods derived from co-evolution.Proceedings of the Genetic and Evolutionary Computation Conference, San Francisco:MorganKaufmann:825-832.1999.
[40]Boettcher, S., Percus, A.G. Nature's way of optimizing. Artificial Intelligence, 119:275-286.2000.
[41]李天龙,基于自组织优化算法的一类组合优化问题求解,浙江大学硕士学位论文,2010.
[42]Holland, J.H. Adaptation in Natural and Artificial Systems. Ann Arbor MI: University of Michigan Press,1975.
[43]M. Dorigo. Optimization, Leaning and Natural Algorithm. Ph. D. Thesis. Dipartimentod iE lettronica,Po litecnicod iM ilano, It aly,1992.
[44]黄岚,王康平,周春光,庞巍,董龙江,彭利,粒子群优化算法求解旅行商问题,吉林大学学报理学版,2003,Vol.43,No.4,477-480.
[45]S. Boettcher, A. G. Percus, Nature's way of optimizing, Phys. Rev. E68 (2004) 066703.
[46]M. E. Menai, M. Batouche, Efficient initial solution to extremal optimization algorithm for eighted MAXSAT. problem, in:IEA/AIE, (2003) 592-603.
[47]Yue K, Fiebig K M, Thomas P D, Chan H S, Shakhnovich E I and Dill K A, A test of lattice protein folding algorithms, Proc Nut/Acud Sei, (1995) 92:325-329.
[48]Lucio T, Salvatore T, Contact interactions method:A new algorithm for protein folding simulations, Protein Science, (1996) 5:147-153.
[49]Michael B, Handan A, Wolfhard J, Multicanonical study of course-grained off-lattice models for folding heteropolymers, Physical Review E 71, (2005) 031906.
[50]巴德年,医学科学面临的新课题,中华医学杂志,Vol.82,No.1,2002.
[51]王晔,顾振纶,秦正红,蛋白质错误折叠与神经退行性疾病,中国临床神经科学,Vol.13,No.4,2005.
[52]周筠梅,蛋白质的错误折叠与疾病[J],生物化学与生物物理进展,2000,27:579-584.
[53]黄星,卢滇楠,闫明,刘铮,蛋白质体外折叠技术研究现状与展望,化工进展,2002,21(12):875.
[54]Reiss C, Lesnik T, Parvez H, et al, Conformational toxicity and sporadic conformational diseases[J], Toxicology,2000,153(1-3):115-121.
[55]张先恩,生物结构自组装,中国科学杂志社科学通报,2009,Vol.54,No.18,2682-2690.
[56]Walter Kauzman, Structural factors in protein denaturation, J Cell Physiol Suppl.1956 May; 47(Suppl 1):113-31.
[57]王琼,浅谈疯牛病之病因及其检测手段,化学教育,2002,(9).
[58]严玉霖,陈玲,高洪,疯牛病致病机理研究进展,动物医学进展,2003,24(6):49-52.
[59]李一凡,张勇,蛋白质巯基亚硝基化与帕金森病,生命的化学,2006,26(6):543-546.
[60]杨卉,陈生弟,parkin基因与帕金森病,中华老年医学杂志,2004,23(5):353-355.
[61]Alberto Caprara, Robert Carr, Sorin Istrail, Giuseppe Lancia, and Brian Walenz, 1001 Optimal PDB Structure Alignments:Integer Programming Methods for Finding the Maximum Contact Map Overlap, Journal of Computational Biology, Vol. 11,No.1,2004,27-52.
[62]Ilya N. Shindyalov and Philip E. Bourne, Protein structure alignment by incremental combinatorial extension (CE) of the optimal path, Protein Engineering, Vol.11, No.9,1998,739-747.