More Web Proxy on the site http://driver.im/

short-paper

A multiscale hybrid evolutionary algorithm to obtain sample-based representations of multi-basin protein energy landscapes

Authors:

Amarda ShehuAuthors Info & Claims

BCB '14: Proceedings of the 5th ACM Conference on Bioinformatics, Computational Biology, and Health Informatics

Pages 269 - 278

https://doi.org/10.1145/2649387.2649390

Published: 20 September 2014 Publication History

Abstract

The emerging picture of proteins as dynamic systems switching between structures to modulate function demands a comprehensive structural characterization only possible through an energy landscape treatment. Only sample-based representations of a protein energy landscape are viable in silico, and sampling-based exploration algorithms have to address the fundamental but challenging issue of balancing between exploration (broad view) and exploitation (going deep). We propose here a novel algorithm that achieves this balance by combining concepts from evolutionary computation and protein modeling research. The algorithm draws samples from a reduced space obtained via principal component analysis of known experimental structures. Samples are lifted from the reduced to an all-atom structure space where they are then mapped to nearby local minima in the all-atom energy landscape. From an algorithmic point of view, this paper makes several contributions, including the design of a local selection operator that is crucial to avoiding premature convergence. From an application point of view, this paper demonstrates the utility of the proposed evolutionary algorithm to advance understanding of multi-basin proteins. In particular, the proposed algorithm makes the first steps to answering the question of how sequence mutations affect function in proteins at the center of proteinopathies by providing the energy landscape as the intermediate explanatory link between protein sequence and function.

References

[1]

O. Beckstein, E. J. Denning, J. R. Perilla, and T. B. Woolf. Zipping and unzipping of adenylate kinase: atomistic insights into the ensemble of open-closed transitions. J. Mol. Biol., 394(1):160--176, 2009.

[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]

R. Clausen and A. Shehu. Exploring the structure space of wildtype ras guided by experimental data. In ACM Conf on Bioinf and Comp Biol Workshops (BCBW), pages 757--764, Washington, D. C., September 2013.

Digital Library

[5]

R. A. Conwit. Preventing familial ALS: a clinical trial may be feasible but is an efficacy trial warranted? J Neurol Sci, 251(1-2):1--2, 2006.

[6]

A. Das and S. S. Plotkins. SOD1 exhibits allosteric frustration to facilitate metal binding affinity. Proc. Natl. Acad. Sci. USA, 110(10):3871--3876, 2013.

[7]

K. A. De Jong. Evolutionary Computation: A Unified Approach. MIT Press, Cambridge, MA, 1st edition, 2006.

[8]

M. DiDonato, L. Craig, M. Huff, M. Thayer, R. Cardoso, C. Kassmann, T. Lo, C. Bruns, E. Powers, J. Kelly, E. Getzoff, and J. Tainer. Als mutants of human superoxide dismutase form fibrous aggregates via framework destabilization. J. Mol. Biol., 332(1):601--615, 2003.

[9]

K. A. Dill and H. S. Chan. From Levinthal to pathways to funnels. Nat. Struct. Biol., 4(1):10--19, 1997.

[10]

E. Z. Eisenmesser, O. Millet, W. Labeikovsky, D. M. Korzhnev, M. Wolf-Watz, D. A. Bosco, J. J. Skalicky, L. E. Kay, and D. Kern. Intrinsic dynamics of an enzyme underlies catalysis. Nature, 438(7064):117--121, 2005.

[11]

A. Fernández-Medarde and E. Santos. Ras in cancer and developmental diseases. Genes Cancer, 2(3):344--358, 2011.

[12]

D. Gront, S. Kmiecik, and A. Kolinski. Backbone building from quadrilaterals: a fast and accurate algorithm for protein backbone reconstruction from alpha carbon coordinates. J. Comput. Chem., 28(29):1593--1597, 2007.

[13]

J. Gsponer, J. Christodoulou, A. Cavalli, J. M. Bui, B. Richter, C. M. Dobson, and M. Vendruscolo. A coupled equilibrium shift mechanism in calmodulin-mediated signal transduction. Structure, 16(5):736--746, 2008.

[14]

M. Hough, J. Grossmann, S. Antonyuk, R. Strange, P. Doucette, J. Rodriguez, L. Whitson, P. Hart, L. Hayward, J. Valentine, and S. Hasnain. Dimer destabilization in superoxide dismutase may result in disease-causing properties: structures of motor neuron disease mutants. Proc. Natl. Acad. Sci. USA, 101(16):5976--5981, 2004.

[15]

W. Humphrey, A. Dalke, and K. Schulten. VMD - Visual Molecular Dynamics. J. Mol. Graph. Model., 14(1):33--38, 1996. http://www.ks.uiuc.edu/Research/vmd/.

[16]

K. Jenzler-Wildman and D. Kern. Dynamic personalities of proteins. Nature, 450:964--972, 2007.

[17]

K. W. Kaufmann, G. H. Lemmon, S. L. DeLuca, J. H. Sheehan, and J. Meiler. Practically useful: What the rosetta protein modeling suite can do for you. Biochemistry, 49(14):2987--2998, 2010.

[18]

D. Kern and E. R. Zuiderweg. The role of dynamics in allosteric regulation. Curr. Opinion Struct. Biol., 13(6):748--757, 2003.

[19]

Y. Li, I. Rata, and E. Jakobsson. Improving predicted protein loop structure ranking using a pareto-optimality consensus method. BMC Struct Biol, 10(22):1--14, 2010.

[20]

Y. Li and A. Yaseen. Pareto-based optimal sampling method and its applications in protein structural conformation sampling. In BOOKTITLE = AAAI Workshop, pages 32--37, Bellevue, Washington, July 2013.

[21]

Q. Lu and J. Wang. Single molecule conformational dynamics of adenylate kinase: energy landscape, structural correlations, and transition state ensembles. J. Am. Chem. Soc., 130(14):4772--4783, 2008.

[22]

M. Magrane and the UniProt consortium. UniProt knowledgebase: a hub of integrated protein data. Database, 2011(bar009):1--13, 2011.

[23]

A. D. McLachlan. A mathematical procedure for superimposing atomic coordinates of proteins. Acta Crystallogr. A., 26(6):656--657, 1972.

[24]

O. J. Mengshoel and D. E. Goldberg. The crowding approach to niching in genetic algorithms. Evol Comput, 16(3):315--354, 2008.

Digital Library

[25]

K. Molloy, R. Clausen, and A. Shehu. On the stochastic roadmap to model functionally-related structural transitions in wildtype and variant proteins. In Robotics: Science and Systems (RSS) Workshop, pages 1--6, Berkeley, CA, 2014.

[26]

K. Okazaki, N. Koga, S. Takada, J. N. Onuchic, and P. G. Wolynes. Multiple-basin energy landscapes for large-amplitude conformational motions of proteins: Structure-based molecular dynamics simulations. Proc. Natl. Acad. Sci. USA, 103(32):11844--11849, 2006.

[27]

B. Olson and A. Shehu. Efficient basin hopping in the protein energy surface. In IEEE Intl Conf on Bioinf and Biomed, Philadelphia, PA, October 2012. 119--124.

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(10):S5, 2012.

[29]

B. Olson and A. Shehu. An evolutionary-inspired algorithm to guide stochastic search for near-native protein conformations with multiobjective analysis. In AAAI Workshop, pages 32--37, Bellevue, Washington, July 2013.

[30]

B. Olson and A. Shehu. Multi-objective stochastic search for sampling local minima in the protein energy surface. In ACM Conf on Bioinf and Comp Biol (BCB), pages 430--439, Washington, D. C., September 2013.

Digital Library

[31]

B. Olson and A. Shehu. Multi-objective optimization techniques for conformational sampling in template-free protein structure prediction. In Intl Conf on Bioinf and Comp Biol (BICoB), Las Vegas, NV, 2014.

[32]

J. N. Onuchic, Z. Luthey-Schulten, and P. G. Wolynes. Theory of protein folding: the energy landscape perspective. Annual Review of Physical Chemistry, 48:545--600, 1997.

[33]

T. Ratovitski, L. Corson, J. Strain, P. Wong, D. Cleveland, V. Culotta, and D. Borchelt. Variation in the biochemical/biophysical properties of mutant superoxide dismutase 1 enzymes and the rate of disease progression in familial amyotrophic lateral sclerosis kindreds. Hum. Mol. Genet., 8(8):1451--1460, 1999.

[34]

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

[35]

A. Shehu, L. E. Kavraki, and C. Clementi. Multiscale characterization of protein conformational ensembles. Proteins: Struct. Funct. Bioinf., 76(4):837--851, 2009.

[36]

C. Soto. Protein misfolding and neurodegeneration. JAMA Neurology, 65(2):184--189, 2008.

[37]

R. W. Strange, S. Antonyuk, M. A. Hough, P. A. Doucette, J. A. Rodriguez, P. Hart, L. J. Hayward, J. S. Valentine, and S. Hasnain. The structure of holo and metal-deficient wild-type human cu, zn superoxide dismutase and its relevance to familial amyotrophic lateral sclerosis. J. Mol. Biol., 328(4):877--891, 2003.

[38]

M. Teodoro and L. E. Kavraki. Understanding protein flexibility through dimensionality reduction. J Comput Biol, 10(3-4):617--634, 2003.

[39]

M. Vendruscolo and C. M. Dobson. Dynamic visions of enzymatic reactions. Science, 313(5793):1586--1587, 2006.

[40]

J. Xu and Y. Zhang. How significant is a protein structure similarity with TM-score = 0.5? Bioinformatics, 26(7):889--895, 2010.

Digital Library

[41]

K. Yap, T. Yuan, H. Mal, T. K. AMD Vogel, and M. Ikura. Structural basis for simultaneous binding of two carboxy-terminal peptides of plant glutamate decarboxylase to calmodulin. J. Mol. Biol., 328(1):193--204, 2003.

[42]

Y. Zhang and J. Skolnick. Scoring function for automated assessment of protein structure template quality. Proteins: Structure, Function, and Bioinformatics, 57(4):702--710, 2004.

Cited By

Lian YBodian DShehu A(2024)Elucidating the Role of Wildtype and Variant FGFR2 Structural Dynamics in (Dys)Function and DisorderInternational Journal of Molecular Sciences10.3390/ijms2508452325:8(4523)Online publication date: 20-Apr-2024
https://doi.org/10.3390/ijms25084523
Zhang GXie TZhou XWang LHu J(2021)Protein Structure Prediction Using Population-Based Algorithm Guided by Information EntropyIEEE/ACM Transactions on Computational Biology and Bioinformatics10.1109/TCBB.2019.292195818:2(697-707)Online publication date: 1-Mar-2021
https://doi.org/10.1109/TCBB.2019.2921958
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
Show More Cited By

Index Terms

A multiscale hybrid evolutionary algorithm to obtain sample-based representations of multi-basin protein energy landscapes
1. Applied computing
  1. Life and medical sciences
2. Mathematics of computing
  1. Probability and statistics
    1. Probabilistic algorithms
    2. Probabilistic reasoning algorithms
      1. Markov-chain Monte Carlo methods
      2. Sequential Monte Carlo methods

Recommendations

Evolutionary search strategies for efficient sample-based representations of multiple-basin protein energy landscapes
BIBM '15: Proceedings of the 2015 IEEE International Conference on Bioinformatics and Biomedicine (BIBM)

Protein function is the result of a complex yet precise relationship between protein structure and dynamics. The ability of a protein to assume different structural states is key to biomolecular recognition and function modulation. Protein modeling ...
Using holey fitness landscapes to counteract premature convergence in evolutionary algorithms
GECCO '08: Proceedings of the 10th annual conference companion on Genetic and evolutionary computation

Premature convergence is a persisting problem in evolutionary optimisation, in particular - genetic algorithms. While a number of methods exist to approach this issue, they usually require problem specific calibration or only partially resolve the issue,...
Statistical Analysis of Computed Energy Landscapes to Understand Dysfunction in Pathogenic Protein Variants
ACM-BCB '17: Proceedings of the 8th ACM International Conference on Bioinformatics, Computational Biology,and Health Informatics

The energy landscape underscores the inherent nature of proteins as dynamic systems interconverting between structures with varying energies. The protein energy landscape contains much of the information needed to characterize protein equilibrium ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

BCB '14: Proceedings of the 5th ACM Conference on Bioinformatics, Computational Biology, and Health Informatics

September 2014

851 pages

ISBN:9781450328944

DOI:10.1145/2649387

General Chairs:
Pierre Baldi
University of California, Irvine
,
Wei Wang
University of California, Los Angeles

Copyright © 2014 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: 20 September 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Short-paper

Funding Sources

Conference

BCB '14

Sponsor:

SIGBio

BCB '14: ACM-BCB '14

September 20 - 23, 2014

California, Newport Beach

Acceptance Rates

Overall Acceptance Rate 254 of 885 submissions, 29%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
60
Total Downloads

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

Reflects downloads up to 19 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lian YBodian DShehu A(2024)Elucidating the Role of Wildtype and Variant FGFR2 Structural Dynamics in (Dys)Function and DisorderInternational Journal of Molecular Sciences10.3390/ijms2508452325:8(4523)Online publication date: 20-Apr-2024
https://doi.org/10.3390/ijms25084523
Zhang GXie TZhou XWang LHu J(2021)Protein Structure Prediction Using Population-Based Algorithm Guided by Information EntropyIEEE/ACM Transactions on Computational Biology and Bioinformatics10.1109/TCBB.2019.292195818:2(697-707)Online publication date: 1-Mar-2021
https://doi.org/10.1109/TCBB.2019.2921958
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
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
Akhter NHassan LRajabi ZBarbará DShehu A(2019)Learning Organizations of Protein Energy Landscapes: An Application on Decoy Selection in Template-Free Protein Structure PredictionProtein Supersecondary Structures10.1007/978-1-4939-9161-7_8(147-171)Online publication date: 4-Apr-2019
https://doi.org/10.1007/978-1-4939-9161-7_8
Hassan LRajabi ZAkhter NShehu AShehu AWu CBoucher CLi JLiu HPop M(2018)Community Detection for Decoy Selection in Template-free Protein Structure PredictionProceedings of the 2018 ACM International Conference on Bioinformatics, Computational Biology, and Health Informatics10.1145/3233547.3233703(621-627)Online publication date: 15-Aug-2018
https://dl.acm.org/doi/10.1145/3233547.3233703
Sapin EDe Jong KShehu A(2018)From Optimization to MappingIEEE/ACM Transactions on Computational Biology and Bioinformatics10.1109/TCBB.2016.262874515:3(719-731)Online publication date: 1-May-2018
https://dl.acm.org/doi/10.1109/TCBB.2016.2628745
Qiao WMaximova TPlaku EShehu AHaspel NCowen LShehu AKahveci TPozzi G(2017)Statistical Analysis of Computed Energy Landscapes to Understand Dysfunction in Pathogenic Protein VariantsProceedings of the 8th ACM International Conference on Bioinformatics, Computational Biology,and Health Informatics10.1145/3107411.3107499(679-684)Online publication date: 20-Aug-2017
https://dl.acm.org/doi/10.1145/3107411.3107499
Hao XZhang GZhou X(2017)Conformational Space Sampling Method Using Multi-Subpopulation Differential Evolution for De novo Protein Structure PredictionIEEE Transactions on NanoBioscience10.1109/TNB.2017.274924316:7(618-633)Online publication date: Oct-2017
https://doi.org/10.1109/TNB.2017.2749243
Sapin EDe Jong KShehu ANeumann FSutton A(2016)A Novel EA-based Memetic Approach for Efficiently Mapping Complex Fitness LandscapesProceedings of the Genetic and Evolutionary Computation Conference 201610.1145/2908812.2908829(85-92)Online publication date: 20-Jul-2016
https://dl.acm.org/doi/10.1145/2908812.2908829
Show More Cited By

View Options

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