基于Monte Carlo局部增强的多模态优化算法

摘要/Abstract

摘要： 高维构象空间搜索是蛋白质结构从头预测领域中一个亟需解决的关键问题。基于差分进化算法框架,提出了一种多模态蛋白构象空间优化算法。算法建立基于蛋白质空间特征向量的相似性测度指标,采用排挤更新策略,避免算法早熟,对蛋白质构象空间模态进行全局搜索；设计基于Monte Carlo局部搜索的片段组装方法,实现模态增强过程,有效平衡算法的收敛速度和种群多样性。采用Rosetta粗粒度能量模型,针对5种测试蛋白的实验结果表明:Monte Carlo局部增强和蛋白质特征向量的相似性测度能够有效地提高算法的性能,与Baker小组和Shehu小组的研究成果相比,提出的算法能够达到较高的预测精度,并得到一系列的亚稳态稳定结构。

Abstract: We elucidated the native structure of a protein molecule from its sequence of amino acids.A problem known as de novo structure prediction,is a long standing challenge in molecular biology.High dimensional conformational space search is the key issue of protein structure prediction that is needed to be solved.Based on differential evolution algorithm framework,we proposed a multimodal protein conformational space optimization algorithm to address the multiple-minima problem in decoy sampling for de novo structure prediction.Algorithm builds the index of similarity measure that is based on the vectors of features of proteins,using exclusion strategy to implement global search.Local minimum search strategy with fragment assembly is able to avoid premature convergence,and can balance the convergence rate and the diversity of the population.A greedy search maps a child conformation to its nearest local minimum,and the molecular fragment replacement technique and differential evolution algorithm help child jump out of local minimum,thus the algorithm can get better search ability.Using Rosetta coarse-grained energy model,results show that the additional mini-mization and the exclusion strategy based on conformation space are key to obtaining a diverse ensemble of decoys.Compared with Baker research team and Shehu research team,the proposed algorithm can achieve better prediction accuracy.

Key words: Multimodal,De novo structure prediction,Crowding differential evolution,Vector of protein structure feature,Fragment replacement

陈先跑,张贵军,秦传庆,郝小虎. 基于Monte Carlo局部增强的多模态优化算法[J]. 计算机科学, 2015, 42(Z6): 61-66. https://doi.org/

CHEN Xian-pao, ZHANG Gui-jun, QIN Chuan-qing and HAO Xiao-hu. Local Monte Carlo Search Approach to Multimodal Problem in Protein Conformation Space Optimization[J]. Computer Science, 2015, 42(Z6): 61-66. https://doi.org/

参考文献

[1] Dill K A,MacCallum J L.The protein-folding problem,50 years on[J].Science,2012,338(6110):1042-1046
[2] Collins F,Patrinos A,Jordan E,et al.New goals for the US Human Genome Project:1998-2003 [J].Science,282(5389):682-689
[3] Mitra P,Shultis D,Zhang Y.EvoDesign:de novo protein design based on structural and evolutionary profiles[J].Nucleic acids research,2013,41(W1):W273-W280
[4] Anfinsen C B.Principles that govern the folding of proteinchains[J].Science,1973,181(4096):223-230
[5] 黄俊峰,段鹏,吴文言.基于模板的蛋白质结构预测[J].生物物理学报,2011,7(1):28-37
[6] Baker D,Sali A.Protein structure prediction and structural genomics[J].Science,2001,294(5540):93-96
[7] Bradley P,Misura K M S,Baker D.Toward high-resolution de novo structure prediction for small proteins[J].Science,2005,309(5742):1868-1871
[8] Kim D E,Blum B,Bradley P,et al.Sampling Bottlenecks in De novo Protein Structure Prediction[J].Journal of molecular bio-logy,2009,393(1):249-260
[9] Saleh S,Olson B,Shehu A.A population-based evolutionary algorithm for sampling minima in the protein energy surface[C]∥2012 IEEE International Conference on Bioinformatics and Biomedicine Workshops(BIBMW).IEEE,2012:64-71
[10] 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
[11] Tantar 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
[12] 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):558-576
[13] 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:88-99
[14] 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
[15] Lindorff-Larsen K,Trbovic N,Maragakis P,et al.Structure and dynamics of an unfolded protein examined by molecular dynami-cs simulation[J].Journal of the American Chemical Society,2012,134(8):3787-3791
[16] Scheraga H A,Khalili M,Liwo A.Protein-folding dynamics:overview of molecular simulation techniques[J].Annu.Rev.Phys.Chem.,2007,58:57-83
[17] Zhang Y,Kihara D,Skolnick J.Local energy landscape flatte-ning:parallel hyperbolic Monte Carlo sampling of protein folding[J].Proteins:Structure,Function,and Bioinformatics,2002,48(2):192-201
[18] Lee J,Lee J,Sasaki T N,et al.De novo protein structure prediction by dynamic fragment assembly and conformational space annealing[J].Proteins:Structure,Function,and Bioinformatics,2011,79(8):2403-2417
[19] 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
[20] Dotu I,Cebrian M,Van Hentenryck P,et al.On lattice protein structure prediction revisited[J].IEEE/ACM Transactions on Computational Biology and Bioinformatics,2011,8(6):1620-1632
[21] 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 computational chemistry,2012,33(31):2483-2491
[22] 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
[23] Shehu A.An Ab-initio tree-based exploration to enhance sampling of low-energy protein conformations[C]∥Robotics:Science and Systems.2009:241-248
[24] Olson B,Molloy K,Shehu A.In search of the protein native state with a probabilistic sampling approach[J].Journal of bioinformatics and computational biology,2011,9(03):383-398
[25] Bradley P,Misura K M S,Baker D.Toward high-resolution de novo structure prediction for small proteins[J].Science,2005,309(5742):1868-1871
[26] Saleh S,Olson B,Shehu A.A population-based evolutionarysearch approach to the multiple minima problem in de novo protein structure prediction[J].BMC structural biology,2013,13(Suppl 1):S4
[27] Wang G,Dunbrack R L.PISCES:a protein sequence cullingserver[J].Bioinformatics,2003,19(12):1589-1591
[28] Gront D,Kulp D W,Vernon R M,et al.Generalized fragment picking in Rosetta:design,protocols and applications[J].PloS one,2011,6(8):e23294
[29] Kolodny R,Koehl P,Guibas L,et al.Small libraries of protein fragments model native protein structures accurately[J].Journal of molecular biology,2002,323(2):297-307
[30] Handl J,Knowles J,Vernon R,et al.The dual role of fragments in fragment-assembly methods for de novo protein structure prediction[J].Proteins:Structure,Function,and Bioinformatics,2012,80(2):490-504
[31] Renfrew P D,Choi E J,Bonneau R,et al.Incorporation of noncanonical amino acids into Rosetta and use in computational protein-peptide interface design[J].PloS one,2012,7(3):e32637
[32] Ballester P J,Richards W G.Ultrafast shape recognition for simi-larity search in molecular databases[J].Proceedings of the Royal Society A:Mathematical,Physical and Engineering Science,2007,463(2081):1307-1321
[33] Storn R.Differential evolution design of anⅡR-filter [C]∥Proceedings of IEEE International Conference on Evolutionary Computation,1996.Nagoya,1996:268-173
[34] Leaver-Fay A,Tyka M,Lewis S M,et al.ROSETTA3:an object-oriented software suite for the simulation and design of macromolecules[J].Methods Enzymol,2011,487:545-574

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed