遗传退火法预测蛋白质结构
|
摘要
蛋白质结构预测问题就是如何从蛋白质的氨基酸序列出发预测它的构象折叠。怎样由一定的氨基酸顺序排列的多肽链生成一定空间结构的蛋白质,这是一个人类破译生命奥秘的重大问题。蛋白质的折叠问题就是通过蛋白质的一级结构来预测蛋白质的三维结构。蛋白质折叠热力学假说中明确指出蛋白质一级结构可以完全决定其空间构型,天然结构下的蛋白质的自由能是全局最小值。因而如何从一级结构预测其三维构型以及如何找到蛋白质折叠能量函数的最小值就成为目前国内外的研究热点。蛋白质折叠过程是热力学过程和动力学过程的综合,其折叠的随机性、过程的复杂性可想而知。因而要对折叠过程进行研究,寻找能量函数的极小值必须借助简化模型和特殊方法进行。
本文的工作是在二维HP非格模型的基础上展开的。蛋白质结构预测模型存在着大量的局部极小值,本文结合遗传算法和模拟退火算法的特点,形成混合遗传退火算法,并用于二维HP非格模型进行蛋白质折叠结构预测,二维HP非格模型把20种氨基酸分为疏水性H和亲水性P两种残基考虑。通过对遗传退火算法中的交叉和变异操作的改进,并且重新设计出假设生成后的排序策略,优化算法能在保持较高精度的情况下搜索到蛋白质序列的最低能量构形。
利用本文的方法对一系列的蛋白质链的空间结构进行了预测,通过对遗传退火混合法的分析与其他方法的预测结果的对比,我们发现本文中的方法生成的新的构象具有更佳的合法性,也减少了无效构象产生的几率,所以能更快地找到合法的能量最低的构象。实验结果表明该混合遗传退火算法优于单纯的遗传法和模拟退火算法。
The issues of protein configuration forecasting are the questions how to forecast its folding from the protein aminophenol sequence. How the spatial protein configuration created by the definite aminophenol one-dimensionnal configuration, is an important issue that the human unveil the mystery of life. The problem of protein folding is to predict the protein three-dimensional structure from its one-dimensional structure. The protein folding thermodynamic hypothesis point out that the spatial structure of a protein is encoded by its primary structure, and its unique spatial structure is the conformation with minimal free energy. So it becomes the internal and overseas research hotspot at present that how to predict the spatial configuration by the sequence of amino acids and how to find the minimal free energy. The course of Protein folding includes a course of thermodynamics and that of dynamics, which is rather random and complex. Therefore, predigesting model and especial method are all necessary in the course of searching the minimal of protein folding energy function.
On the basis of HP off-lattice model consisting of hydrophobic and hydrophilic residues,anovel hybrid algorithm that combines genetic algorithm and simulated annealing is presented for dealing with multi-extremum and multi-parameter problem in this thesis. A kind of optimization of the crossover and mutation operators in the genetic annealing algorithm is implemented, and a new sort strategy of the current hypotheses is designed. The optimization hybrid algorithm is feasible to predict protein folding structure, and can insure the solution hybrid algorithm is feasible to predict protein folding structure, and can insure the solution quality when used to search for the global minimum energy conformations of proteins with AB off-lattice model.
At the end of paper, the GAA were applied in some protein sequence, via analysisof process of GAA and result of GAA and other algorithms mentioned in this paper, astringency of energy of GAA is better than other algorithms mentioned. AT the same time,the tentative conforms of GAA were more valid than other algorithms mentioned and probability of producing invalid was largely reduced. Experimental results demonstrate that genetic annealing algorithm is of better performance and accuracy compared to the previous methods.
本文的工作是在二维HP非格模型的基础上展开的。蛋白质结构预测模型存在着大量的局部极小值,本文结合遗传算法和模拟退火算法的特点,形成混合遗传退火算法,并用于二维HP非格模型进行蛋白质折叠结构预测,二维HP非格模型把20种氨基酸分为疏水性H和亲水性P两种残基考虑。通过对遗传退火算法中的交叉和变异操作的改进,并且重新设计出假设生成后的排序策略,优化算法能在保持较高精度的情况下搜索到蛋白质序列的最低能量构形。
利用本文的方法对一系列的蛋白质链的空间结构进行了预测,通过对遗传退火混合法的分析与其他方法的预测结果的对比,我们发现本文中的方法生成的新的构象具有更佳的合法性,也减少了无效构象产生的几率,所以能更快地找到合法的能量最低的构象。实验结果表明该混合遗传退火算法优于单纯的遗传法和模拟退火算法。
The issues of protein configuration forecasting are the questions how to forecast its folding from the protein aminophenol sequence. How the spatial protein configuration created by the definite aminophenol one-dimensionnal configuration, is an important issue that the human unveil the mystery of life. The problem of protein folding is to predict the protein three-dimensional structure from its one-dimensional structure. The protein folding thermodynamic hypothesis point out that the spatial structure of a protein is encoded by its primary structure, and its unique spatial structure is the conformation with minimal free energy. So it becomes the internal and overseas research hotspot at present that how to predict the spatial configuration by the sequence of amino acids and how to find the minimal free energy. The course of Protein folding includes a course of thermodynamics and that of dynamics, which is rather random and complex. Therefore, predigesting model and especial method are all necessary in the course of searching the minimal of protein folding energy function.
On the basis of HP off-lattice model consisting of hydrophobic and hydrophilic residues,anovel hybrid algorithm that combines genetic algorithm and simulated annealing is presented for dealing with multi-extremum and multi-parameter problem in this thesis. A kind of optimization of the crossover and mutation operators in the genetic annealing algorithm is implemented, and a new sort strategy of the current hypotheses is designed. The optimization hybrid algorithm is feasible to predict protein folding structure, and can insure the solution hybrid algorithm is feasible to predict protein folding structure, and can insure the solution quality when used to search for the global minimum energy conformations of proteins with AB off-lattice model.
At the end of paper, the GAA were applied in some protein sequence, via analysisof process of GAA and result of GAA and other algorithms mentioned in this paper, astringency of energy of GAA is better than other algorithms mentioned. AT the same time,the tentative conforms of GAA were more valid than other algorithms mentioned and probability of producing invalid was largely reduced. Experimental results demonstrate that genetic annealing algorithm is of better performance and accuracy compared to the previous methods.
引文
[1]Gyapay G., Morissette J,Dulbecco R. A turning point in cancer research:sequencing the human genome[J]. Science 1986,231 (4742):1055-1056
[2]赵南明,周海梦.生物物理学[M]北京：高等教育出版社,2007
[3]杨铭.结构生物学概论[M] 北京：北京医科大学出版社,2002
[4]K. F. Lau, K. A. Dill. A lattice statistical mechanics model of the conformational and sequence space of proteins [J]. Macromolecules,1989(22):53-55
[5]W. E. Hart, S. Istrail. Robust proofs of NP- hardness for protein folding general lattices and energy potentials [J]. Journal of Computational Biology,1997(1)
[6]F. H. Stillinger, T. Head- Gordon and C. L. Hirshfel. Toy model for protein folding [J].Phys. Rev.,1993(48)
[7]K. A. Dill. Dominant forces in protein folding[J]. Biochemistry,1990 (31)
[8]邵平凡,万程鹏.求解全局优化问题的遗传退火算法.计算机工程与应用[J].2007,(12)：67-69
[9]H.- P. Hsu, V. Mehra, W. Nadler, and P. Grassberger. Growth algorithms for lattice heteropolymers at low temperatures [J]. Chem.Phys.2003(1)
[10]阎隆飞,孙之荣.蛋白质分子结构[M].北京：清华大学出版社,1999.5.
[11]Yuko Okamoto. Protein Folding Problem as Studied by Monte Carlo Simulated Annealing[J]. Physical Properties Research,1998,70 (6):719-742.
[12]黄文奇,李宗日文.基于模拟退火算法的蛋白质折叠问题求解[J].计算机工程与应用,2005,7：40-41.
[13]T. Hiroyasu, M. Miki, M. Ogura, and Y. Okamoto. Examination of Parallel Simulated Annealing using Genetic Crossover [J]. Journal of Information Processing Society of Japan,2002,43 (SIG7 (TOM6)):70-79.
[14]王小平,曹立明.遗传算法—理论、应用与软件实现[M].陕西：西安交通大学出版社,2002.
[15]F. A. Momany, R. F. McGuire, A.W. Burgess, and H. A. Scheraga[J]. J. Phys. Chem.,1975,79:2361-2381.
[16]康立山,谢云,矢尤勇等.非数值并行算法——模拟退火算法[M].北京：科学出版社,1994.
[17]Yusuke Tanimura,Keiko Aoi. Implementation of Protein Tertiary Struc2ture Prediction System with NetSolve[J]. Future Generation Computing Systems, Meta computing Issue,2004,15:649-658.
[18]李世炳,邹忠毅.简介导引模拟退火法及其应用[J],物理,2002,24(2)：307-319
[19]倪红春,卫翼飞.基于遗传算法的蛋白质折叠模拟系统[J],上海大学学报(自然版),2001,7(4)：359-364,
[20]唐焕文,靳利霞,计明军.蛋白质结构预测的优化模型与方法[J]工程数学学报2002,19(2)：13-22
[21]靳利霞,唐焕文.模拟退火算法的一种改进及其在蛋白质结构预测中的应用[J].,系统工程理论与实践,2002,9：92-96
[22]彭东海.基于模拟退火的混和遗传算法[J].湖南工程学院学报,2005(3)：53-57
[23]郝博,王雷,景晓东.基于混和遗传算法优化的数据预处理组合方法研究[J].计算机应用研究,2005(12)：39～40
[24]Levinthal C. Are there pathways for protein folding? [J]. J. Chem.Phys.,1968,65:44-45.
[25]Wetlaufer DB. Nucleation,rapid folding,and globular intrachain regions in proteins[J]. Proc. Natl. Acad Sci. USA,1973,70 (3):697-701.
[26]Wolynes PG,Onuchic JN,Thirumalai D. Navigating the folding routes[J]. Science,1995,267(5204):1619-1620.
[27]K. A. Dill,H. S. Chan. From Levinthal to pathways to funnels[J]. Nature Struct.Biol.,1997,4:9-10.
[28]Tsai CJ,Ma BY,Kumar S,et al. Protein folding:Binding of conformationally fluctuation building blocks viapopulation selection [J]. Crit. Rev.Biochem.Mol. biol.,2001,36 (5):399-443.
[29]Wallace LA,Robert Matthews C. Sequential vs. parallel protein-fold-ing mechanisms:experiment tests for complex folding reactions[J].Bio-phys Chem.,2002,101-102(1):113-131.
[30]Baker D. A surprising simplicity to protein folding[J]. Nature,2000, 405(6782):39-42.
[31]Oliveberg M. Characterization of the transition states for protein fold- ing:towards a new level of mechanistic detail in protein engineering analysis[J]. Curr. Opin. Struct.Biol.,2001,11 (1):94-100.
[32]Udea Y,Taketomi H,Go N:Studies of protein folding,unfolding,and fluctuations by computer simulation.2.3 - dimensional lattice model for lysozyme[J].Biopolymers,1978,17:1531-1548.
[33]Marek cieplak. Cooperativity and contact order in protein folding[J]. Phys. Rev. E,2004,69:031907.
[34]Michael Andrec,Anthony K. Felts, Emilio Gallicchio, Ronald M. Levy,Protein folding pathways from replica exchange simulations and a kinetic network model [J]. PNAS,2005,102:6801-6806.
[35]Audun Bakka,Johan S. HHye. One-dimensional Ising model applied to protein folding[J]. Physica A,2003,323:504-518.
[36]Unger R. et al., Genetic algorithms for protein folding simulations[J]. J.Mol.Biol.,1993,231:75.
[37]Wang JS,Swendsen RH. Cluster Monte Carlo Algorithm[J]. Physica A,1990,167:565.
[38]解伟,王翼飞.蛋白质折叠的计算机模拟上海大学学报[J](自然科学版)第6卷第2期2000年4月：145-149
[39]林晓丽,万程鹏.基于AB非格模型和遗传退火算法的蛋白质折叠预测[J]科技创业2008(7)：140-143
[40]刘景发,陈端兵,刘朝霞.改进的势能曲面变平法在二维非格点模型中的应用[J]计算机科学2008(10)：243-245
[41]解伟,王翼飞.蛋白质折叠的三维计算机模拟[J]上海大学学报(自然科学版)第6卷第6期：548-550
[2]赵南明,周海梦.生物物理学[M]北京：高等教育出版社,2007
[3]杨铭.结构生物学概论[M] 北京：北京医科大学出版社,2002
[4]K. F. Lau, K. A. Dill. A lattice statistical mechanics model of the conformational and sequence space of proteins [J]. Macromolecules,1989(22):53-55
[5]W. E. Hart, S. Istrail. Robust proofs of NP- hardness for protein folding general lattices and energy potentials [J]. Journal of Computational Biology,1997(1)
[6]F. H. Stillinger, T. Head- Gordon and C. L. Hirshfel. Toy model for protein folding [J].Phys. Rev.,1993(48)
[7]K. A. Dill. Dominant forces in protein folding[J]. Biochemistry,1990 (31)
[8]邵平凡,万程鹏.求解全局优化问题的遗传退火算法.计算机工程与应用[J].2007,(12)：67-69
[9]H.- P. Hsu, V. Mehra, W. Nadler, and P. Grassberger. Growth algorithms for lattice heteropolymers at low temperatures [J]. Chem.Phys.2003(1)
[10]阎隆飞,孙之荣.蛋白质分子结构[M].北京：清华大学出版社,1999.5.
[11]Yuko Okamoto. Protein Folding Problem as Studied by Monte Carlo Simulated Annealing[J]. Physical Properties Research,1998,70 (6):719-742.
[12]黄文奇,李宗日文.基于模拟退火算法的蛋白质折叠问题求解[J].计算机工程与应用,2005,7：40-41.
[13]T. Hiroyasu, M. Miki, M. Ogura, and Y. Okamoto. Examination of Parallel Simulated Annealing using Genetic Crossover [J]. Journal of Information Processing Society of Japan,2002,43 (SIG7 (TOM6)):70-79.
[14]王小平,曹立明.遗传算法—理论、应用与软件实现[M].陕西：西安交通大学出版社,2002.
[15]F. A. Momany, R. F. McGuire, A.W. Burgess, and H. A. Scheraga[J]. J. Phys. Chem.,1975,79:2361-2381.
[16]康立山,谢云,矢尤勇等.非数值并行算法——模拟退火算法[M].北京：科学出版社,1994.
[17]Yusuke Tanimura,Keiko Aoi. Implementation of Protein Tertiary Struc2ture Prediction System with NetSolve[J]. Future Generation Computing Systems, Meta computing Issue,2004,15:649-658.
[18]李世炳,邹忠毅.简介导引模拟退火法及其应用[J],物理,2002,24(2)：307-319
[19]倪红春,卫翼飞.基于遗传算法的蛋白质折叠模拟系统[J],上海大学学报(自然版),2001,7(4)：359-364,
[20]唐焕文,靳利霞,计明军.蛋白质结构预测的优化模型与方法[J]工程数学学报2002,19(2)：13-22
[21]靳利霞,唐焕文.模拟退火算法的一种改进及其在蛋白质结构预测中的应用[J].,系统工程理论与实践,2002,9：92-96
[22]彭东海.基于模拟退火的混和遗传算法[J].湖南工程学院学报,2005(3)：53-57
[23]郝博,王雷,景晓东.基于混和遗传算法优化的数据预处理组合方法研究[J].计算机应用研究,2005(12)：39～40
[24]Levinthal C. Are there pathways for protein folding? [J]. J. Chem.Phys.,1968,65:44-45.
[25]Wetlaufer DB. Nucleation,rapid folding,and globular intrachain regions in proteins[J]. Proc. Natl. Acad Sci. USA,1973,70 (3):697-701.
[26]Wolynes PG,Onuchic JN,Thirumalai D. Navigating the folding routes[J]. Science,1995,267(5204):1619-1620.
[27]K. A. Dill,H. S. Chan. From Levinthal to pathways to funnels[J]. Nature Struct.Biol.,1997,4:9-10.
[28]Tsai CJ,Ma BY,Kumar S,et al. Protein folding:Binding of conformationally fluctuation building blocks viapopulation selection [J]. Crit. Rev.Biochem.Mol. biol.,2001,36 (5):399-443.
[29]Wallace LA,Robert Matthews C. Sequential vs. parallel protein-fold-ing mechanisms:experiment tests for complex folding reactions[J].Bio-phys Chem.,2002,101-102(1):113-131.
[30]Baker D. A surprising simplicity to protein folding[J]. Nature,2000, 405(6782):39-42.
[31]Oliveberg M. Characterization of the transition states for protein fold- ing:towards a new level of mechanistic detail in protein engineering analysis[J]. Curr. Opin. Struct.Biol.,2001,11 (1):94-100.
[32]Udea Y,Taketomi H,Go N:Studies of protein folding,unfolding,and fluctuations by computer simulation.2.3 - dimensional lattice model for lysozyme[J].Biopolymers,1978,17:1531-1548.
[33]Marek cieplak. Cooperativity and contact order in protein folding[J]. Phys. Rev. E,2004,69:031907.
[34]Michael Andrec,Anthony K. Felts, Emilio Gallicchio, Ronald M. Levy,Protein folding pathways from replica exchange simulations and a kinetic network model [J]. PNAS,2005,102:6801-6806.
[35]Audun Bakka,Johan S. HHye. One-dimensional Ising model applied to protein folding[J]. Physica A,2003,323:504-518.
[36]Unger R. et al., Genetic algorithms for protein folding simulations[J]. J.Mol.Biol.,1993,231:75.
[37]Wang JS,Swendsen RH. Cluster Monte Carlo Algorithm[J]. Physica A,1990,167:565.
[38]解伟,王翼飞.蛋白质折叠的计算机模拟上海大学学报[J](自然科学版)第6卷第2期2000年4月：145-149
[39]林晓丽,万程鹏.基于AB非格模型和遗传退火算法的蛋白质折叠预测[J]科技创业2008(7)：140-143
[40]刘景发,陈端兵,刘朝霞.改进的势能曲面变平法在二维非格点模型中的应用[J]计算机科学2008(10)：243-245
[41]解伟,王翼飞.蛋白质折叠的三维计算机模拟[J]上海大学学报(自然科学版)第6卷第6期：548-550