计算机科学 ›› 2017, Vol. 44 ›› Issue (5): 211-217.doi: 10.11896/j.issn.1002-137X.2017.05.038

• 人工智能 • 上一篇    下一篇

基于副本交换的局部增强差分进化蛋白质结构从头预测方法

李章维,郝小虎,张贵军   

  1. 浙江工业大学信息工程学院 杭州310023,浙江工业大学信息工程学院 杭州310023,浙江工业大学信息工程学院 杭州310023
  • 出版日期:2018-11-13 发布日期:2018-11-13
  • 基金资助:
    本文受国家自然科学基金(61075062,61379020),浙江省自然科学基金(LY13F030008),浙江省科技厅公益项目(2014C33088),浙江省重中之重学科开放基金(20120811)资助

Replica Exchange Based Local Enhanced Differential Evolution Searching Method in Ab-initio Protein Structure Prediction

LI Zhang-wei, HAO Xiao-hu and ZHANG Gui-jun   

  • Online:2018-11-13 Published:2018-11-13

摘要: 针对蛋白质高维构象空间搜索问题,提出一种基于副本交换的局部增强差分进化蛋白质结构从头预测方法(RLDE)。首先,采用基于知识的Rosetta粗粒度能量模型显著降低构象空间优化变量维数;其次,引入基于片段库知识的片段组装技术进一步减小构象搜索空间,有效避免搜索过程中的熵效应;此外,在每个副本层设置构象种群,采用差分进化算法对种群进行更新,然后利用Monte Carlo算法对种群做局部增强,以此得到全局和部分局部最优构象。综上,RLDE利用差分进化算法较强的全局搜索能力可以对构象空间进行有效的全局搜索;借助Monte Carlo算法局部搜索性能对构象空间局部极小区域进行更为充分的采样;副本交换策略保证了副本层中种群的多样性,同时能够增强算法跳出局部极小的能力,从而使得算法对构象空间的搜索能力进一步增强。15个目标蛋白测试结果表明,所提方法能够有效地对构象空间采样,得到高精度的近天然态蛋白质构象。

关键词: 从头预测,蛋白质结构预测,副本交换,Monte Carlo,片段组装,差分进化算法

Abstract: To address the searching problem in high-dimensional protein conformational space,a replica exchange based local enhanced differential evolution searching method in ab-initio protein structure prediction (RLDE) was proposed.In this paper,the knowledge-based coarse-grained energy model,Rosetta,was employed to considerably reduce the optimal variable dimension of protein conformational space;the knowledge-based fragment assembly technique was introduced to further reduce the dimension of protein conformational space.Thus the entropy effect caused by searching in high-dimensionality conformational space could be avoided.Additionally,a conformation population was put into every replica layer,differential evolution algorithm was adopted to update the population in each layer,and the updated populations were then enhanced by Monte Carlo method.As a consequence,the global optimal conformation and a series of metastable conformations were generated.In conclusion,RLDE can effectively search the global conformational space through the strong global searching ability of differential evolution algorithm.The well local searching performance of Monte Carlo is also employed to sample the local minimum area adequately.Replica exchange strategy ensures the diversity of population in replica layers,and the capacity of algorithm to jump out of local minimum is enhanced as well,thereby makes the searching ability further heightened.Test results of 15 target proteins show that the proposed method can generated high-resolution near-native protein conformations by searching the conformational space effectively.

Key words: Ab-initio prediction,Protein structure prediction,Replica exchange,Monte Carlo,Fragment assembly,Differential evolution algorithm

[1] DILL K A,MACCALLUM J L.The Protein Folding Problem,50 Years On [J].Science,2012,338(6110):1042-1046.
[2] ANFINSEN C B.Principles that govern the folding of protein chains [J].Science,1973,181(96):223-230.
[3] DORNA M,SILVAB M B,BURIOLA L S,et al.3-dimensional protein structure prediction:Methods and computational strategies [J].Computational Biology and Chemistry,2014,53(B):51-276.
[4] KRYSHTAFOVYCH A,FIDELIS K,MOULT J.CASP10 re-sults compared to those of previous CASP experiments [J].Proteins:Structure,Function,and Bioinformatics,2014,82(S2):164-174.
[5] BAKER D,SALI A.Protein structure prediction and structural genomics [J].Science,2001,294(5540):93-96.
[6] BELIAKOV G,LIMA K F.Challenges of continuous global optimization in molecular structure prediction [J].European Journal of Operational Research,2007,181(3):1198-1213.
[7] LEE J,WU S,ZHANG Y.From Protein Structure to Function with Bioinformatics [M].Berlin:Springer Netherlands,2009:3-25.
[8] TANTA A A,MELAB N,TALBI E G,et al.A parallel hybrid genetic algorithm for protein structure prediction on the computational grid [J].Future Generation Computer Systems,2007,23(3):398-409.
[9] HOQUE M T,CHETTY M,LEWIS A,et al.Twin Removal in Genetic Algorithms for Protein Structure Prediction Using Low-Resolution Model [J].IEEE/ACM Transactions on Computational Biology and Bioinformatics,2011,8(1):234-245.
[10] ISLAM M K,CHETTY M.Clustered Memetic Algorithm with Local Heuristics for Ab Initio Protein Structure Prediction [J].IEEE Transactions on Evolutionary Computation,2013,17(4):58-576.
[11] CUSTDIO F L,BARBOSA H J C,D ARDENNE L E.A multiple minima genetic algorithm for protein structure prediction [J].Applied Soft Computing,2014,15(2):88-99.
[12] STORN R,PRICE K.Differential Evolution-A Simple and Efficient Heuristic for global Optimization over Continuous Spaces [J].Journal of global optimization,1997,11(4):341-359.
[13] ZOU D X,WU J H,GAO L Q,et al.A modified differential evolution algorithm for unconstrained optimization problems [J].Neurocomputing,2013,120(11):469-481.
[14] CASCIATI,SARA.Differential evolution approach to reliability-oriented optimal design[J].Probabilistic Engineering Mechanics,2014,36(4):72-80.
[15] DUAN Y,KOLLMAN P A.Pathways to a protein folding intermediate observed in a 1-microsecond simulation in aqueous solution [J].Science,1998,282(5389):740-744.
[16] SCHERAGE H A,KHALILI,LIWO A.Protein-folding dyna-mics:overview of molecular simulation techniques [J].Annual Review of Physical Chemistry,2007,58(1):57-83.
[17] LINDORFF-LARSEN K,TRBOVICN,MARAGAKIS P,et al.Structure and Dynamics of an Unfolded Protein Examined by Molecular Dynamics Simulation[J].Journal of the American Chemical Society,2012,134(8):3787-3791.
[18] ZHANG Y,KIHARA D,SKOLNICK J.Local energy landscape flattening:Parallel hyperbolic Monte Carlo sampling of protein folding [J].Proteins:Structure,Function and Bioinformatics,2002,48(2):192-201.
[19] SHEN Y,PICORD G,GUYON F,et al.Detecting protein candidate fragments using a structural alphabet profile comparison approach [J].PloS one,2013,8(11):e80493.
[20] XU D,ZHANG Y.Toward optimal fragment generations for ab initio protein structure assembly [J].Proteins:Structure,Function and Bioinformatics,2013,81(2):229-239.
[21] DOTU I,CEBRIA M,VAN H P,et al.On Lattice ProteinStructure Prediction Revisited [J].IEEE/ACM Transactions on Computational Biology and Bioinformatics,2011,8(6):1620-1632.
[22] TYKA M D,JUNG K,BAKER D.Efficient sampling of protein conformational space using fast loop building and batch minimization on highly parallel computers[J].Journal of ComputationalChemistry,2012,33(31):2483-2491.
[23] JOO K,LEE J,SIM S,et al.Protein structure modeling forCASP10 by multiple layers of global optimization [J].Proteins:Structure Function and Bioinformatics,2014,82(S2):188-195.
[24] SUGITA Y,OKAMOTO Y.Replica-exchange molecular dy-namics method for protein folding[J].Chemical Physics Letters,1999,314(1/2):141-151.
[25] SUGITA Y,OKAMOTO Y.Replica-exchange multicanonical algorithm and multicanonical replica-exchange method for simulating systems with rough energy landscape [J].Chemical Physics Letters,2000,329(3):261-270.
[26] CZAPLEWSKI C,KALINOWSKI S,LIWO A,et al.Applicationof Multiplexed Replica Exchange Molecular Dynamics to the UNRES Force Field:Tests with alpha and alpha+beta Proteins [J].Journal of Chemical Theory and Computation,2009,3(5):627-640.
[27] HANSMANN U H E.Parallel tempering algorithm for conformational studies of biological molecules [J].Chemical Physics Letters,1997,281(1):140-150.
[28] GNTERTA P,BILLETERA M,OHLENSCHLGERB O,et al.Conformational analysis of protein and nucleic acid fragments with the new grid search algorithm FOUND [J].Journal of Biomolecular NMR,1998,12(4):543-548.
[29] PETRELLA R J.A versatile method for systematic conformational searches:Application to CheY [J].Journal of computational chemistry,2011,32(11):2369-2385.
[30] SCHERAGE H A.Some approaches to the multiple-minimaproblem in the calculation of polypeptide and protein structures [J].International Journal of Quantum Chemistry,1992,42(5):1529-1536.
[31] ADJIMAN C S,DALLWIG S,FLOUDAS C A,et al.A global optimization method,αBB,for general twice-differentiable constrained NLPs-I.Theoretical advances-II.Application of theory and test problems [J].Computers and Chemical Engineering,1998,22(9):1137-1158.
[32] KLEPEIS J L,PIEJA M J,F LOUDAS C A.Hybrid global optimization algorithms for protein structure prediction:Alternating hybrids [J].Biophysical Journal,2003,84(2):869-882.
[33] FLOUDAS C A,FUNG H K,MCALLISTER S R,et al.Ad-vances in protein structure prediction and de novo protein design:A review [J].Chemical Engineering Science,2006,61(3):966-988.
[34] OLSON B,MOLLOY K,SHEHU A.In search of the proteinnative state with a probabilistic sampling approach [J].Journal of Bioinformatics and Computational Biology,2011,9(3):383-398.
[35] OLSON B,SHEHU A.Evolutionary-inspired probabilistic sear-ch for enhancing sampling of local minima in the protein energy surface[J].Proteome Science,2012,10(S1):S5.
[36] MOLLOY K,SALEH S,SHEHU A.Probabilistic Search andEnergy Guidance for Biased Decoy Sampling in Ab-initio Protein Structure Prediction [J].IEEE/ACM Transactions on Computational Biology and Bioinformatics,2013,10(5):1162-1175.
[37] KEAVER-FAY A,TYKA M,LEWIS S M,et al.ROSETTA3:an objectoriented software suite for the simulation and design of macromolecules [J].Methods in Enzymology,2011,487:545-574.
[38] XU D,ZHANG Y.Ab-initio protein structure assembly usingcontinuous structure fragments and optimized knowledge-based force field [J].Proteins:Structure,Function,and Bioinforma-tics,2012,80(7):1715-1735.
[39] STOEAN C,PREUSS M,STOEAN R,et al.Multimodal Optimization by Means of a Topological Species Conservation Algorithm [J].Evolutionary Computation,2010,14(6):842-864.
[40] ZHANG Y S,HAO Z F,HUANG H.Global convergence and premature convergence of two-membered evolution strategy [J].Journal of Computer Research and Development,2014,54(4):754-761.(in Chinese) 张宇山,郝志峰,黄翰.二元进化策略的全局收敛与早熟收敛 [J].计算机研究与发展,2014,54(4):754-761.
[41] KIM D E,BLUM B,BRADLEY P,et al.Sampling bottlenecks in de novo protein structure prediction [J].Journal of molecular biology,2009,393(1):249-260.
[42] KMIECIK S,JAMROZ M,KOLINSKI A.Multiscale Approa-ches to Protein Modeling [M].Berlin:Springer Science,2011:281-293.
[43] BRADLEY P,MISURA K M,BAKER D.Toward high-resolution de novo structure prediction for small proteins [J].Science,2005,309(5742):1868-1871.
[44] LIWO A,KHALILI M,SCHERAGE H A.Ab initio simulations of protein-folding pathways by molecular dynamics with the united-residue model of polypeptide chains [J].PNAS,2005,102(7):2362-2367.
[45] SALEH S,OLSON B,SHEHU A.A population-based evolu-tionary search approach to the multiple minima problem in de novo protein structure prediction [J].BMC Structural Biology,2013,13(S1):S4.
[46] KUHLMAN B,BAKER D.Native protein sequences are closeto optimal for their structures [J].Proceedings of the National Academy of Sciences of the Unitized States of America,2000,97(19):10383-10388.
[47] KORTEMME T,MOROZOV A V,BAKER D.An orientation-dependent hydrogen bonding potential improves prediction of specificity and structure for proteins and protein-protein complexes [J].Journal of molecular biology,2003,326(4):1239-1259.
[48] HUANG E S,SAMUDRALA R,PARK B H.Scoring Functions for ab initio Protein Structure Prediction [J].Methods in Mole-cular Biology,2000,143:223-245.
[49] EARL D J,DEEM M W.Parallel tempering:Theory,applications,and new perspectives [J].Physical Chemistry Chemical Physics,2005,7(23):3910-3916.
[50] LIAO C Y,ZHOU J.Replica Exchange Molecular Dynamics Si-mulations on the Folding of Trpzip4 β-Hairpin [J].ACTA CHIMICA SINICA,2013,71:593-601.(in Chinese) 廖晨伊,周健.β发卡多肽Trpzip4折叠的副本交换分子动力学模拟 [J].化学学报,2013,71:593-601.
[51] STORN R.Differential evolution design of an IIR-filter in Evolutionary Computation [C]∥Proceedings of IEEE International Conference on Evolutionary Computation(ICEC’96).New York:IEEE,1996:268-273.
[52] BERG B A,NEUHAUS T.Multicationical ens EMBLE-A new approach to simulate1ST-order Phase-Transitions[J].Physics Review Letter,1992,68(1):9-12.
[53] YU W J,SHEN M,CHEN W N,et al.Differential evolution with two-level parameter adaptation [J].IEEE Transactions on Cybernetics,2014,44(7):1080-1099.
[54] DING F,TSAO D,NIE H,et al.Ab initio folding of proteinsusing all-atom discrete molecular dynamics [J].Structure,2008,16(7):1010-1018.
[55] OKAMOTO Y,FUKUGITA M,NAKAZAWA T,et al.Alpha-helix folding by Monte Carlo simulated annealing in isolated C-peptide of ribonuclease A[J].Protein Eng.,1991,4(6):639-686.
[56] ZHANG W,WU C,DUAN Y.Convergence of replica exchange molecular dynamics [J].Journal of Chemical Physics,2005,123(15):154105-154113.

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!