tutorial

Multi-Objective Stochastic Search for Sampling Local Minima in the Protein Energy Surface

Authors:

Amarda ShehuAuthors Info & Claims

BCB'13: Proceedings of the International Conference on Bioinformatics, Computational Biology and Biomedical Informatics

Pages 430 - 439

https://doi.org/10.1145/2506583.2506590

Published: 22 September 2013 Publication History

Abstract

We present an evolutionary stochastic search algorithm to obtain a discrete representation of the protein energy surface in terms of an ensemble of conformations representing local minima. This objective is of primary importance in protein structure modeling, whether the goal is to obtain a broad view of potentially different structural states thermodynamically available to a protein system or to predict a single representative structure of a unique functional native state. In this paper, we focus on the latter setting, and show how approaches from evolutionary computation for effective stochastic search and multi-objective analysis can be combined to result in protein conformational search algorithms with high exploration capability. From a broad computational perspective, the contributions of this paper are on how to balance global and local search of some high-dimensional search space and how to guide the search in the presence of a noisy, inaccurate scoring function. From an application point of view, the contributions are demonstrated in the domain of template-free protein structure prediction on the primary subtask of sampling diverse low-energy decoy conformations of an amino-acid sequence. Comparison with the approach used for decoy sampling in the popular Rosetta protocol on 20 diverse protein sequences shows that the evolutionary algorithm proposed in this paper is able to access lower-energy regions with similar or better proximity to the known native structure.

References

[1]

C. B. Anfinsen. Principles that govern the folding of protein chains. Science, 181(4096):223--230, 1973.

[2]

H. M. Berman, K. Henrick, and H. Nakamura. Announcing the worldwide Protein Data Bank. Nat. Struct. Biol., 10(12):980--980, 2003.

[3]

D. D. Boehr, R. Nussinov, and P. E. Wright. The role of dynamic conformational ensembles in biomolecular recognition. Nature Chem Biol, 5(11):789--96, 2009.

[4]

P. Bradley, K. M. Misura, and D. Baker. Toward high-resolution de novo structure prediction for small proteins. Science, 309(5742):1868--1871, 2005.

[5]

T. J. Brunette and O. Brock. Guiding conformation space search with an all-atom energy potential. Proteins: Struct. Funct. Bioinf., 73(4):958--972, 2009.

[6]

J. Calvo, J. Ortega, and M. Anguita. PITAGORAS-PSP: Including domain knowledge in a multi-objective approach for protein structure prediction. Neurocomputing, 74(16):2675--2682, 2011.

[7]

C. Chira, D. Horvath, and D. Dumitrescu. An Evolutionary Model Based on Hill-Climbing Search Operators for Protein Structure Prediction. Evolutionary Computation, Machine Learning and Data Mining in Bioinformatics, pages 38--49, 2010.

Digital Library

[8]

Cutello, V, G. Morelli, G. Nicosia, M. Pavone, and G. Scollo. On discrete models and immunological algorithms for protein structure prediction. Natural Computing, 10(1):91--102, 2011.

Digital Library

[9]

R. Das. Four small puzzles that rosetta doesn't solve. PLoS ONE, 6(5):e20044, 2011.

[10]

J. DeBartolo, G. Hocky, M. Wilde, J. Xu, K. F. Freed, and T. R. Sosnick. Protein structure prediction enhanced with evolutionary diversity: SPEED. Protein Sci., 19(3):520--534, 2010.

[11]

K. F. Han and D. Baker. Global properties of the mapping between local amino acid sequence and local structure in proteins. Proc. Natl. Acad. Sci. USA, 93(12):5814--5818, 1996.

[12]

J. Handl, J. Knowles, R. Vernon, D. Baker, and S. C. Lovell. The dual role of fragments in fragment-assembly methods for de novo protein structure prediction. Proteins: Struct. Funct. Bioinf., 80(2):490--504, 2011.

[13]

J. Heglera, J. Lätzera, A. Shehu, C. Clementi, and P. Wolynes. Restriction versus guidance in protein structure prediction. PNAS, 106(36):15302--15307, 2009.

[14]

M. K. Islam, M. Chetty, and M. Murshed. Novel local improvement techniques in clustered memetic algorithm for protein structure prediction. In IEEE Congress on Evol Comput (CEC), pages 1003--1011, 2011.

[15]

G. G. Krivov, M. V. Shapovalov, and R. L. J. Dunbrack. Improved prediction of protein side-chain conformations with SCWRL4. ProteinsSFB, 77(4):778--795, 2009.

[16]

A. Leaver-Fay, M. Tyka, S. M. Lewis, O. F. Lange, J. Thompson, R. Jacak, et al.ROSETTA3: an object-oriented software suite for the simulation and design of macromolecules. Methods Enzymol, 487:545--574, 2011.

[17]

J. Lee, S. Wu, and Y. Zhang. Ab initio protein structure prediction. In D. Rigden, editor, Ab Initio Protein Structure Prediction, chapter 1. Springer Science + Business Media B.V., 2009.

[18]

S. J. Lutdke, D. H. Chen, J. L. Song, D. T. Chuang, and W. Chiu. Seeing GroEL at 6 Å resolution by single particle electron cryomicroscopy. Structure, 12:1129--1136, 2004.

[19]

K. Molloy, S. Saleh, and A. Shehu. Probabilistic search and energy guidance for biased decoy sampling in ab-initio protein structure prediction. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 99(PrePrints):1, 2013.

[20]

K. Molloy and A. Shehu. Biased decoy sampling to identify near-native protein conformations. In A. Zhang, S. Ranka, T. Kahveci, M. Singh, and V. Honavar, editors, ACM Bioinf. and Comp. Biol. (BCB), pages 131--138, Orlando, FL, October 2012.

Digital Library

[21]

J. Moult, K. Fidelis, A. Kryshtafovych, and A. Tramontano. Critical assessment of methods of protein structure prediction (CASP) round IX. Proteins: Struct. Funct. Bioinf., Suppl(10):1--5, 2011.

[22]

G. Narzisi, G. Nicosia, and G. Stracquadanio. Robust Bio-active Peptide Prediction Using Multi-objective Optimization. In Int Conf on Biosciences, pages 44--50, 2010.

Digital Library

[23]

B. Olson, and A. Shehu. Populating local minima in the protein conformational space. In IEEE Intl Conf on Bioinf and Biomed (BIBM), pages 114--117, 2011.

Digital Library

[24]

B. Olson, K. De Jong, and A. Shehu. Off-lattice protein structure prediction with homologous crossover. In Proceeding of the fifteenth annual conference on Genetic and evolutionary computation conference, GECCO '13, pages 287--294, New York, NY, USA, 2013. ACM.

Digital Library

[25]

B. Olson, I. Hashmi, I. Molloy, and A. Shehu. Basin hopping as a general and versatile optimization framework for the characterization of biological macromolecules. Advances in AI J, 2012(674832), 2012.

Digital Library

[26]

B. Olson, K. Molloy, and A. Shehu. In search of the protein native state with a probabilistic sampling approach. J. Bioinf. and Comp. Biol., 9(3):383--398, 2011.

[27]

B. Olson and A. Shehu. Efficient basin hopping in the protein energy surface. In J. Gao, W. Dubitzky, C. Wu, M. Liebman, R. Alhaij, L. Ungar, A. Christianson, and X. Hu, editors, IEEE Intl Conf on Bioinf and Biomed (BIBM), pages 119--124, Philadelphia, PA, October 2012. IEEE.

Digital Library

[28]

B. Olson and A. Shehu. Evolutionary-inspired probabilistic search for enhancing sampling of local minima in the protein energy surface. Proteome Sci, 10(Suppl 1):S5, 2012.

[29]

B. Olson and A. Shehu. Rapid sampling of local minima in protein energy surface and effective reduction through a multi-objective filter. Proteome Sci, 2013. in press.

[30]

C. A. Rohl, C. E. Strauss, K. M. Misura, and D. Baker. Protein structure prediction using rosetta. Methods Enzymol., 383:66--93, 2004.

[31]

S. Saleh, B. Olson, and A. Shehu. A population-based evolutionary algorithm for sampling minima in the protein energy surface. In J. He, A. Shehu, N. Haspel, and C. B., editors, IEEE Intl Conf on Bioinf and Biomed Workshops, pages 48--55, Philadelphia, PA, October 2012.

Digital Library

[32]

S. Saleh, B. Olson, and A. Shehu. A population-based evolutionary search approach to the multiple minima problem in de novo protein structure prediction. BMC Struct Biol., 2013. in press.

[33]

A. Shehu. An ab-initio tree-based exploration to enhance sampling of low-energy protein conformations. In Robot: Sci. and Sys., pages 241--248, Seattle, WA, USA, 2009.

[34]

A. Shehu. Conformational search for the protein native state. In H. Rangwala and G. Karypis, editors, Protein Structure Prediction: Method and Algorithms, chapter 21. Wiley Book Series on Bioinformatics, Fairfax, VA, 2010.

[35]

A. Shehu. Probabilistic search and optimization for protein energy landscapes. In A. Srinivas and M. Singh, editors, Handbook of Computational Molecular Biology. Chapman & Hall/CRC Computer & Information Science Series, 2 edition, 2013.

[36]

A. Shmygelska and M. Levitt. Generalized ensemble methods for de novo structure prediction. Proc. Natl. Acad. Sci. USA, 106(5):94305--95126, 2009.

[37]

V. N. Uversky. Intrinsic disorder in proteins associated with neurodegenerative diseases. Front Biosci, 14:5188--5238, 2009.

[38]

D. Xu and Y. Zhang. Ab initio protein structure assembly using continuous structure fragments and optimized knowledge-based force field. Proteins: Struct. Funct. Bioinf., 80(7):1715--1735, 2012.

[39]

M. Zhang and L. E. Kavraki. A new method for fast and accurate derivation of molecular conformations. Chem. Inf. Comput. Sci., 42(1):64--70, 2002.

[40]

Y. Zhang. Progress and challenges in protein structure prediction. Curr. Opinion Struct. Biol., 18(3):342--348, 2008.

Cited By

Zaman AInan TDe Jong KShehu A(2022)Adaptive Stochastic Optimization to Improve Protein Conformation SamplingIEEE/ACM Transactions on Computational Biology and Bioinformatics10.1109/TCBB.2021.3134103(1-1)Online publication date: 2022
https://doi.org/10.1109/TCBB.2021.3134103
Peng CZhou XZhang G(2022)De novo Protein Structure Prediction by Coupling Contact With Distance ProfileIEEE/ACM Transactions on Computational Biology and Bioinformatics10.1109/TCBB.2020.300075819:1(395-406)Online publication date: 1-Jan-2022
https://doi.org/10.1109/TCBB.2020.3000758
Xia YPeng CZhou XZhang G(2021)A sequential niche multimodal conformational sampling algorithm for protein structure predictionBioinformatics10.1093/bioinformatics/btab50037:23(4357-4365)Online publication date: 10-Jul-2021
https://doi.org/10.1093/bioinformatics/btab500
Show More Cited By

Index Terms

Multi-Objective Stochastic Search for Sampling Local Minima in the Protein Energy Surface
1. Applied computing
  1. Life and medical sciences
2. Mathematics of computing
  1. Probability and statistics

Recommendations

A population-based evolutionary algorithm for sampling minima in the protein energy surface
BIBMW '12: Proceedings of the 2012 IEEE International Conference on Bioinformatics and Biomedicine Workshops (BIBMW)

Obtaining a structural characterization of the biologically active (native) state of a protein is a long standing problem in computational biology. The high dimensionality of the conformational space and ruggedness of the associated energy surface are ...
Enhanced bounding techniques to reduce the protein conformational search space
GLOBAL OPTIMIZATION

The complexity and enormous size of the conformational space that must be explored for the protein tertiary structure prediction problem has led to the development of a wide assortment of algorithmic approaches. In this study, we apply state-of-the-art ...
Populating Local Minima in the Protein Conformational Space
BIBM '11: Proceedings of the 2011 IEEE International Conference on Bioinformatics and Biomedicine

Protein Modeling conceptualizes the protein energy landscape as a funnel with the native structure at the low-energy minimum. Current protein structure prediction algorithms seek the global minimum by searching for low-energy conformations in the hope ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

BCB'13: Proceedings of the International Conference on Bioinformatics, Computational Biology and Biomedical Informatics

September 2013

987 pages

ISBN:9781450324342

DOI:10.1145/2506583

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGBio: ACM Special Interest Group on Bioinformatics

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 September 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Tutorial
Research
Refereed limited

Conference

BCB'13

Sponsor:

SIGBio

BCB'13: ACM-BCB2013

September 22 - 25, 2013

Wshington DC, USA

Acceptance Rates

BCB'13 Paper Acceptance Rate 43 of 148 submissions, 29%;

Overall Acceptance Rate 254 of 885 submissions, 29%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

33
Total Citations
View Citations
129
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)0

Reflects downloads up to 29 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zaman AInan TDe Jong KShehu A(2022)Adaptive Stochastic Optimization to Improve Protein Conformation SamplingIEEE/ACM Transactions on Computational Biology and Bioinformatics10.1109/TCBB.2021.3134103(1-1)Online publication date: 2022
https://doi.org/10.1109/TCBB.2021.3134103
Peng CZhou XZhang G(2022)De novo Protein Structure Prediction by Coupling Contact With Distance ProfileIEEE/ACM Transactions on Computational Biology and Bioinformatics10.1109/TCBB.2020.300075819:1(395-406)Online publication date: 1-Jan-2022
https://doi.org/10.1109/TCBB.2020.3000758
Xia YPeng CZhou XZhang G(2021)A sequential niche multimodal conformational sampling algorithm for protein structure predictionBioinformatics10.1093/bioinformatics/btab50037:23(4357-4365)Online publication date: 10-Jul-2021
https://doi.org/10.1093/bioinformatics/btab500
Zaman AKamranfar PDomeniconi CShehu A(2020)Reducing Ensembles of Protein Tertiary Structures Generated De Novo via ClusteringMolecules10.3390/molecules2509222825:9(2228)Online publication date: 9-May-2020
https://doi.org/10.3390/molecules25092228
Akhter NChennupati GDjidjev HShehu A(2020)Decoy selection for protein structure prediction via extreme gradient boosting and rankingBMC Bioinformatics10.1186/s12859-020-3523-921:S1Online publication date: 9-Dec-2020
https://doi.org/10.1186/s12859-020-3523-9
Tadepalli SAkhter NBarbara DShehu A(2020)Anomaly Detection-Based Recognition of Near-Native Protein StructuresIEEE Transactions on NanoBioscience10.1109/TNB.2020.299064219:3(562-570)Online publication date: Jul-2020
https://doi.org/10.1109/TNB.2020.2990642
Kabir KHassan LRajabi ZAkhter NShehu A(2019)Graph-Based Community Detection for Decoy Selection in Template-Free Protein Structure PredictionMolecules10.3390/molecules2405085424:5(854)Online publication date: 28-Feb-2019
https://doi.org/10.3390/molecules24050854
Kandathil SGarza-Fabre MHandl JLovell S(2019)Reliable Generation of Native-Like Decoys Limits Predictive Ability in Fragment-Based Protein Structure PredictionBiomolecules10.3390/biom91006129:10(612)Online publication date: 15-Oct-2019
https://doi.org/10.3390/biom9100612
Zaman AShehu A(2019)Balancing multiple objectives in conformation sampling to control decoy diversity in template-free protein structure predictionBMC Bioinformatics10.1186/s12859-019-2794-520:1Online publication date: 25-Apr-2019
https://doi.org/10.1186/s12859-019-2794-5
Zaman ADe Jong KShehu AAuger AStützle T(2019)Using subpopulation EAs to map molecular structure landscapesProceedings of the Genetic and Evolutionary Computation Conference10.1145/3321707.3321777(960-967)Online publication date: 13-Jul-2019
https://dl.acm.org/doi/10.1145/3321707.3321777
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents