计算机科学 ›› 2019, Vol. 46 ›› Issue (6A): 80-84.

• 智能计算 • 上一篇    下一篇

蛋白质结构从头预测多级个体筛选进化算法

李章维, 郝小虎, 张贵军   

  1. 浙江工业大学信息工程学院 杭州310023
  • 出版日期:2019-06-14 发布日期:2019-07-02
  • 通讯作者: 张贵军(1974-),男,博士,教授,主要研究方向为智能信息处理、全局优化理论及算法设计、生物信息学,E-mail:zgj@zjut.edu.cn(通信作者)。
  • 作者简介:李章维(1967-),男,博士,副教授,CCF会员,主要研究方向为智能信息处理,E-mail:lzw@zjut.edu.cn;郝小虎(1990-),男,博士生,主要研究方向为智能信息处理、生物信息学;
  • 基金资助:
    本文受国家自然科学基金(61075062,61379020) 资助。

Multi-layer Screening Based Evolution Algorithm for De Novo Protein Structure Prediction

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

  1. College of Information Engineering,Zhejiang University of Technology,Hangzhou 310023,China
  • Online:2019-06-14 Published:2019-07-02

摘要: 针对蛋白质高维构象空间采样多样性问题,文中提出了一种蛋白质结构从头预测多级个体筛选进化算法(MlISEA)。基于进化算法框架,首先采用基于知识的Rosetta粗粒度能量模型作为优化目标函数,以降低构象空间优化变量维数;其次以基于9片段和3片段的片段组装技术为不同的变异策略,增加同代种群的多样性;同时,设计多级个体筛选方法,进一步增加不同代种群间的多样性;然后利用Monte Carlo算法较强的局部搜索能力对每个个体做局部增强,以得到当前的局部最优解;最后,得到全局最优解以及不同的局部最优解。10个目标蛋白的测试结果表明,所提方法能够有效提高采样多样性,得到TMscore大于0.5的预测构象,为进一步做结构修饰提供便利。

关键词: MonteCarlo, TMscore, 从头预测, 进化算法, 片段组装

Abstract: Aiming at the diversity of sampling in high-dimensional protein conformational space,a multi-layer screening based evolution algorithm for de novo protein structure prediction (MlISEA),was proposed.On the basis of the evolution algorithm framework,the knowledge-based Rosetta coarse-grained energy model is employed as the objective function,to reduce the optimal variable dimension of protein conformational space.Taking 9-mer and 3-mer fragment assembly technique as two different kinds of mutation strategies,the diversity of the individuals in the same generation can be increased.In conjunction,multi-layer individual screening method is designed for further improving the diversity of the individuals in different generations.Then,Monte Carlo algorithm is adopted to enhance the performance for each individual to get the local optimal solution.Finally,the global resolution and different local solutions can be obtained.Test results of 10 target proteins show that the proposed method can effectively improve the diversity of sampling,the prediction conformations with TMscore greater than 0.5 can be obtained for further refinement.

Key words: De novo, Evolution algorithm, Fragment assembly, Monte Carlo, TMscore

中图分类号: 

  • TP301.6
[1]ANFINSEN C B.Principles that govern the folding of protein chains [J].Science,1973,181(96):223-230.
[2]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.
[3]SCHERAGA 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.
[4]LINDORFF-LARSEN K,TRBOVIC N,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.
[5]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.
[6]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.
[7]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.
[8]DOTU I,CEBRIA M,VAN H P,et al.On Lattice Protein Structure Prediction Revisited [J].IEEE/ACM Transactions on Computatio-nal Biology and Bioinformatics,2011,8(6):1620-1632.
[9]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 Computatio-nal Chemistry,2012,33(31):2483-2491.
[10]JOO K,LEE J,SIM S,et al.Protein structure modeling for CASP10 by multiple layers of global optimization [J].Proteins:Structure Function and Bioinformatics,2014,82(S2):188-195.
[11]SUGITA Y,OKAMOTO Y.Replica-exchange molecular dy-namics method for protein folding [J].Chemical Physics Letters,1999,314(1-2):141-151.
[12]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.
[13]CZAPLEWSKI C,KALINOWSKI S,LIWO A,et al.Application of 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.
[14]HANSMANN U H E.Parallel tempering algorithm for conformational studies of biological molecules [J].Chemical Physics Letters,1997,281(1):140-150.
[15]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.
[16]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.
[17]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.
[18]CUSTÓDIO F L,BARBOSA H J C,DARDENNE L E.A multiple minima genetic algorithm for protein structure prediction [J].Applied Soft Computing,2014,15(2):88-99.
[19]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.
[20]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.
[21]CASCIATI,SARA.Differential evolution approach to reliability-oriented optimal design [J].Probabilistic Engineering Mechanics,2014,36(4):72-80.
[22]HAO X H,ZHANG G J,ZHOU X G,et al.A novel method using abstract convex underestimation in ab-initio protein structure prediction for guiding search in conformational feature space [J].IEEE/ACM Transaction Computer Biol.Bioinf.,2016,13(5):887-900.
[23]HAO X H,ZHANG G J,ZHOU X G.Guiding exploration in conformational feature space with Lipschitz underestimation for ab-initio protein structure prediction [J].Computational Biology and Chemistry,2018,73:105-119.
[24]ZHANG G J,ZHOU X G,YU X F,et al.Enhancing protein conformational space sampling using distance profile-guided differential evolution [J].IEEE/ACM Transaction ComputerBiol.Bioinf.,2017,14(6):1288-1301.
[25]HAO X H,ZHANG G J,ZHOU X G.Conformational Space Sampling Method Using Multi-Subpopulation Differential Evolution for De novo Protein Structure Prediction [J].IEEE Transaction Nano Bioscience,2017,16(7):618-633.
[26]董辉,郝小虎,张贵军.蛋白质构象空间局部增强差分进化搜索方法 [J].计算机科学,2015,42(11A):22-26.
[27]李章维,郝小虎,张贵军.基于副本交换的局部增强差分进化蛋白质结构从头预测方法 [J].计算机科学,2017,44(5):211-217.
[28]CLAUSEN R,SHEHU A.A multiscale hybrid evolutionary algorithm to obtain sample-based representations of multi-basin protein energy landscapes [C]∥ACM-BCB,Newport Beach.CA,USA,2014:269-278.
[29]OLSON B,DE JONG K,SHEHU A.Off-lattice protein struc-ture prediction with homologous crossover [C]∥15th Annu.Conference Genet.Evol.Computer.2013:287-294.
[30]OLSON B,SHEHU A.Multi-objective optimization techniques for conformational sampling in template-free protein structure prediction [C]∥6th Int.Conf.Bioinf.Computer.Biol..2014:143-148.
[31]DAS S,SUGANTHAN P N.Differential evolution:a survey of the state-of-the-art [J].IEEE Transactions on Evolutionary Computation,2011,15:4-31.
[32]GARZA-FABRE M,KANDATHIL S M,HANDL J,et al.Gene-rating,Maintaining,and Exploiting Diversity in a Memetic Algorithm for Protein Structure Prediction [J].Evolutionary Computation,2016,24(4):577-607.
[33]KMIECIK S,JAMROZ M,KOLINSKI A.Multiscale Approaches to Protein Modeling [M].Berlin:Springer Science,2011:281-293.
[34]BRADLEY P,MISURA K M,BAKER D.Toward high-resolution de novo structure prediction for small proteins [J].Science,2005,309(5742):1868-1871.
[35]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.
[36]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.
[37]KUHLMAN B,BAKER D.Native protein sequences are close to optimal for their structures [J].Proceedings of the National Academy of Sciences of the Unitized States of America,2000,97(19):10383-10388.
[38]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.
[39]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.
[40]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.
[1] 刘宝宝, 杨菁菁, 陶露, 王贺应.
基于DE-LSTM模型的教育统计数据预测研究
Study on Prediction of Educational Statistical Data Based on DE-LSTM Model
计算机科学, 2022, 49(6A): 261-266. https://doi.org/10.11896/jsjkx.220300120
[2] 孙刚, 伍江江, 陈浩, 李军, 徐仕远.
一种基于切比雪夫距离的隐式偏好多目标进化算法
Hidden Preference-based Multi-objective Evolutionary Algorithm Based on Chebyshev Distance
计算机科学, 2022, 49(6): 297-304. https://doi.org/10.11896/jsjkx.210500095
[3] 李笠, 李广鹏, 常亮, 古天龙.
约束进化算法及其应用研究综述
Survey of Constrained Evolutionary Algorithms and Their Applications
计算机科学, 2021, 48(4): 1-13. https://doi.org/10.11896/jsjkx.200600151
[4] 周晟伊, 曾红卫.
进化算法与符号执行结合的程序复杂度分析方法
Program Complexity Analysis Method Combining Evolutionary Algorithm with Symbolic Execution
计算机科学, 2021, 48(12): 107-116. https://doi.org/10.11896/jsjkx.210200052
[5] 赵杨, 倪志伟, 朱旭辉, 刘浩, 冉家敏.
基于改进狮群进化算法的面向空间众包平台的多工作者多任务路径规划方法
Multi-worker and Multi-task Path Planning Based on Improved Lion Evolutionary Algorithm forSpatial Crowdsourcing Platform
计算机科学, 2021, 48(11A): 30-38. https://doi.org/10.11896/jsjkx.201200085
[6] 朱汉卿, 马武彬, 周浩浩, 吴亚辉, 黄宏斌.
基于改进多目标进化算法的微服务用户请求分配策略
Microservices User Requests Allocation Strategy Based on Improved Multi-objective Evolutionary Algorithms
计算机科学, 2021, 48(10): 343-350. https://doi.org/10.11896/jsjkx.201100009
[7] 张清琪, 刘漫丹.
复杂网络社区发现的多目标五行环优化算法
Multi-objective Five-elements Cycle Optimization Algorithm for Complex Network Community Discovery
计算机科学, 2020, 47(8): 284-290. https://doi.org/10.11896/jsjkx.190700082
[8] 董明刚, 弓佳明, 敬超.
基于谱聚类的多目标进化社区发现算法研究
Multi-obJective Evolutionary Algorithm Based on Community Detection Spectral Clustering
计算机科学, 2020, 47(6A): 461-466. https://doi.org/10.11896/JsJkx.191100215
[9] 杨浩, 陈红梅.
基于量子进化算法的非平衡数据混合采样算法
Mixed-sampling Method for Imbalanced Data Based on Quantum Evolutionary Algorithm
计算机科学, 2020, 47(11): 88-94. https://doi.org/10.11896/jsjkx.191000102
[10] 王瑄, 毛莺池, 谢在鹏, 黄倩.
基于差分进化的推断任务卸载策略
Inference Task Offloading Strategy Based on Differential Evolution
计算机科学, 2020, 47(10): 256-262. https://doi.org/10.11896/jsjkx.190800159
[11] 谢腾宇,周晓根,胡俊,张贵军.
基于接触图残基对距离约束的蛋白质结构预测算法
Contact Map-based Residue-pair Distances Restrained Protein Structure Prediction Algorithm
计算机科学, 2020, 47(1): 59-65. https://doi.org/10.11896/jsjkx.181202395
[12] 肖鹏, 邹德旋, 张强.
一种高效动态自适应差分进化算法
Efficient Dynamic Self-adaptive Differential Evolution Algorithm
计算机科学, 2019, 46(6A): 124-132.
[13] 耿焕同, 韩伟民, 周山胜, 丁洋洋.
一种基于新型邻域更新策略的MOEA/D算法
MOEA/D Algorithm Based on New Neighborhood Updating Strategy
计算机科学, 2019, 46(5): 191-197. https://doi.org/10.11896/j.issn.1002-137X.2019.05.029
[14] 金婷, 谭文安, 孙勇, 赵尧.
模糊多目标进化的社会团队形成方法
Social Team Formation Method Based on Fuzzy Multi-objective Evolution
计算机科学, 2019, 46(2): 315-320. https://doi.org/10.11896/j.issn.1002-137X.2019.02.048
[15] 刘鑫平, 顾春华, 罗飞, 丁炜超.
基于败者组与混合编码策略的NSGA-II改进算法
Improved NSGA-II Algorithm Based on Loser Group and Hybrid Coding Strategy
计算机科学, 2019, 46(10): 222-228. https://doi.org/10.11896/jsjkx.181001852
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!