Computer Science ›› 2019, Vol. 46 ›› Issue (6A): 80-84.

• Intelligent Computing • Previous Articles     Next Articles

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

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

CLC Number: 

  • 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] LI Dan-dan, WU Yu-xiang, ZHU Cong-cong, LI Zhong-kang. Improved Sparrow Search Algorithm Based on A Variety of Improved Strategies [J]. Computer Science, 2022, 49(6A): 217-222.
[2] LIU Bao-bao, YANG Jing-jing, TAO Lu, WANG He-ying. Study on Prediction of Educational Statistical Data Based on DE-LSTM Model [J]. Computer Science, 2022, 49(6A): 261-266.
[3] FU Si-qing, LI Tie-jun, ZHANG Jian-min. Architecture Design for Particle Transport Code Acceleration [J]. Computer Science, 2022, 49(6): 81-88.
[4] LUO Jun-ren, ZHANG Wan-peng, LU Li-na, CHEN Jing. Survey on Online Adversarial Planning for Real-time Strategy Game [J]. Computer Science, 2022, 49(6): 287-296.
[5] AO Tian-yu, LIU Quan. Upper Confidence Bound Exploration with Fast Convergence [J]. Computer Science, 2022, 49(1): 298-305.
[6] LIU Tian-xing, LI Wei, XU Zheng, ZHANG Li-hua, QI Xiao-ya, GAN Zhong-xue. Monte Carlo Tree Search for High-dimensional Continuous Control Space [J]. Computer Science, 2021, 48(10): 30-36.
[7] WANG Dong, SHANG Hong-hui, ZHANG Yun-quan, LI Kun, HE Xin-fu, JIA Li-xia. Application of Atomic Dynamics Monte Carlo Program MISA-KMC in Study of Irradiation Damage of Reactor Pressure Vessel Steel [J]. Computer Science, 2020, 47(4): 30-35.
[8] LI Yuan-feng, LI Zhang-wei, QIN Zi-hao, HU Jun, ZHANG Gui-jun. Study on Transportation Problem Using Monte Carlo Similarity Based Genetic Algorithm [J]. Computer Science, 2020, 47(10): 215-221.
[9] WANG Xuan, MAO Ying-chi, XIE Zai-peng, HUANG Qian. Inference Task Offloading Strategy Based on Differential Evolution [J]. Computer Science, 2020, 47(10): 256-262.
[10] XIE Teng-yu,ZHOU Xiao-gen,HU Jun,ZHANG Gui-jun. Contact Map-based Residue-pair Distances Restrained Protein Structure Prediction Algorithm [J]. Computer Science, 2020, 47(1): 59-65.
[11] LUO Fei, REN Qiang, DING Wei-chao, LU Hai-feng. Heuristic One-dimensional Bin Packing Algorithm Based on Minimum Slack [J]. Computer Science, 2019, 46(9): 315-320.
[12] XIAO Peng, ZOU De-xuan, ZHANG Qiang. Efficient Dynamic Self-adaptive Differential Evolution Algorithm [J]. Computer Science, 2019, 46(6A): 124-132.
[13] WU Si-wen, LI Jing, ZHANG Shao-qiang. De Novo Transcriptome Assembly Algorithm Based on RNA-Seq Datasets [J]. Computer Science, 2018, 45(12): 308-312.
[14] ZHANG Qi-man, ZHANG Ying. Study on Monte Carlo Location Algorithm in Wireless Sensor Networks [J]. Computer Science, 2018, 45(12): 77-80.
[15] SHAN Tian-yu, GUAN Yu-yang. Differential Evolution Algorithm with Adaptive Population Size Reduction Based on Population Diversity [J]. Computer Science, 2018, 45(11A): 160-166.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!