research-article

From Optimization to Mapping: An Evolutionary Algorithm for Protein Energy Landscapes

Authors:

Emmanuel Sapin,

Kenneth A. De Jong,

Amarda ShehuAuthors Info & Claims

IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), Volume 15, Issue 3

Pages 719 - 731

https://doi.org/10.1109/TCBB.2016.2628745

Published: 01 May 2018 Publication History

Abstract

Stochastic search is often the only viable option to address complex optimization problems. Recently, evolutionary algorithms have been shown to handle challenging continuous optimization problems related to protein structure modeling. Building on recent work in our laboratories, we propose an evolutionary algorithm for efficiently mapping the multi-basin energy landscapes of dynamic proteins that switch between thermodynamically stable or semi-stable structural states to regulate their biological activity in the cell. The proposed algorithm balances computational resources between exploration and exploitation of the nonlinear, multimodal landscapes that characterize multi-state proteins via a novel combination of global and local search to generate a dynamically-updated, information-rich map of a protein's energy landscape. This new mapping-oriented EA is applied to several dynamic proteins and their disease-implicated variants to illustrate its ability to map complex energy landscapes in a computationally feasible manner. We further show that, given the availability of such maps, comparison between the maps of wildtype and variants of a protein allows for the formulation of a structural and thermodynamic basis for the impact of sequence mutations on dysfunction that may prove useful in guiding further wet-laboratory investigations of dysfunction and molecular interventions.

References

[1]

C. A. Floudas and P. M. Pardalos, Encyclopedia of Optimization. Norwell, MA, USA: Kluwer, 2001.

[2]

J. Pinter, "Nonconvex optimization and its applications," in Global Optimization: Scientific and Engineering Case Studies, P. Panos, Ed, vol. 85. New York, NY, USA: Springer, 2006.

[3]

F. Werner, "A survey of genetic algorithms for shop scheduling problems," in Mathematics and Statistics, P. Siarry, Ed. Commack, NY, USA: Nova, 2013, pp. 161-222.

[4]

D. Whitley, D. Hains, and A. E. Howe, "A hybrid genetic algorithm for the traveling salesman problem using generalized partition crossover," in Proc. 11th Int. Conf. Parallel Problem Solving Nature, Sep. 2010, pp. 566-575.

[5]

A. Grosso, A. R. Jamali, M. Locatelli, and F. Schoen, "Solving the problem of packing equal and unequal circles in a circular container," J. Global Optimization, vol. 47, no. 1, pp. 63-81, 2010.

[6]

D. Devaurs, K. Molloy, M. Vaisset, and A. Shehu, "Characterizing energy landscapes of peptides using a combination of stochastic algorithms," IEEE Trans. Nanobioscience, vol. 14, no. 5, pp. 545- 552, Jul. 2015.

[7]

B. Olson and A. Shehu, "Evolutionary-inspired probabilistic search for enhancing sampling of local minima in the protein energy surface," Proteome Sci., vol. 10, no. 10, 2012, Art. no. S5.

[8]

B. Olson and A. Shehu, "Multi-objective optimization techniques for conformational sampling in template-free protein structure prediction," presented at the Int. Conf. Bioinf. Comput. Biol., Las Vegas, NV, USA, 2014.

[9]

B. Olson, K. A. De Jong, and A. Shehu, "Off-lattice protein structure prediction with homologous crossover," in Proc. 15th Annu. Conf. Genetic Evol. Comput., 2013, pp. 287-294.

[10]

B. Olson and A. Shehu, "Multi-objective stochastic search for sampling local minima in the protein energy surface," in Proc. ACM Conf. Bioinf. Comput. Biol., Sep. 2013, pp. 430-439.

[11]

G. M. Morris, et al., "Automated docking using a Lamarckian genetic algorithm and an empirical binding free energy function," J. Comput. Chemical, vol. 19, no. 14, pp. 1639-1662, 1998.

[12]

J. Esquivel-Rodriguez, Y. D. Yang, and D. Kihara, "Multi-LZerD: Multiple protein docking for asymmetric complexes," Proteins: Structure Function Bioinf., vol. 80, no. 7, pp. 1818- 1833, 2012.

[13]

I. Hashmi and A. Shehu, "idDock+: Integrating machine learning in probabilistic search for protein-protein docking," J. Comput. Biol., vol. 22, no. 9, pp. 1-18, 2015.

[14]

I. Hashmi and A. Shehu, "HopDock: A probabilistic search algorithm for decoy sampling in protein-protein docking," Proteome Sci., vol. 11, no. Suppl 1, 2013, Art. no. S6.

[15]

M. Rusu and S. Birmanns, "Evolutionary tabu search strategies for the simultaneous registration of multiple atomic structures in cryo-EM reconstructions," J. Structure Biol., vol. 170, no. 1, pp. 164-171, 2010.

[16]

A. Shehu, "A review of evolutionary algorithms for computing functional conformations of protein molecules," in Computer-Aided Drug Discovery, W. Zhang, Ed. Berlin, Germany: Springer Verlag, 2015.

[17]

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

[18]

T. Maximova, R. Moffatt, B. Ma, R. Nussinov, and A. Shehu, "Principles and overview of sampling methods for modeling macromolecular structure and dynamics," PLoS Comput. Biol., vol. 12, no. 4, 2016, Art. no. e1004619.

[19]

P. Stadler, "Fitness landscapes," Appl. Math. Comput., vol. 117, pp. 187-207, 2002.

[20]

H. M. Berman, K. Henrick, and H. Nakamura, "Announcing the worldwide Protein Data Bank," Nature Structure Biol., vol. 10, no. 12, pp. 980-980, 2003.

[21]

D. D. Boehr, R. Nussinov, and P. E. Wright, "The role of dynamic conformational ensembles in biomolecular recognition," Nature Chemical Biol., vol. 5, no. 11, pp. 789-96, 2009.

[22]

D. Russel, K. Lasker, J. Phillips, D. Schneidman-Duhovny, J. A. Veláquez-Muriel, and A. Sali, "The structural dynamics of macromolecular processes," Current Opinion Cell Biol., vol. 21, no. 1, pp. 97-108, 2009.

[23]

B. Ma, S. Kumar, C. Tsai, and R. Nussinov, "Folding funnels and binding mechanisms," Protein Eng., vol. 12, no. 9, pp. 713-720, 1999.

[24]

B. J. Grant, A. A. Gorfe, and A. McCammon, "Large conformational changes in proteins: Signaling and other functions," Current Opinion Structure Biol., vol. 20, no. 2, pp. 142-147, 2010.

[25]

E. Babini, I. Bertini, F. Capozzi, C. Luchinat, A. Quattrone, and M. Turano, "Principal component analysis of the conformational freedom within the EF-hand superfamily," J. Proteome Res., vol. 4, no. 6, pp. 1961-1971, 2005.

[26]

A. A. Gorfe, B. J. Grant, and J. A. McCammon, "Mapping the nucleotide and isoform-dependent structural and dynamical features of Ras proteins," Structure, vol. 16, no. 6, pp. 885-896, 2008.

[27]

B. J. Grant, A. A. Gorfe, and J. A. McCammon, "Ras conformational switching: Simulating nucleotide-dependent conformational transitions with accelerated molecular dynamics," PLoS Comput. Biol., vol. 5, no. 3, 2009, Art. no. e1000325.

[28]

C. C. David and D. J. Jacobs, "Principal component analysis: A method for determining the essential dynamics of proteins," in Protein Dynamics. New York, NY, USA: Humana Press, 2013, pp. 193-226.

[29]

M. Gur, J. D. Madura, and I. Bahar, "Global transitions of proteins explored by a multiscale hybrid methodology: Application to adenylate kinase," Biophysical J., vol. 105, no. 7, pp. 1643-1652, 2013.

[30]

Y. Liu and I. Bahar, "Sequence evolution correlates with structural dynamics," Mol. Biol. Evol., vol. 29, no. 9, pp. 2253-2263, 2014.

[31]

L. Skjaerven, X. Q. Yao, G. Scarabelli, and B. J. Grant, "Integrating protein structural dynamics and evolutionary analysis with Bio3D," BMC Bioinf., vol. 15, no. 399, pp. 1-11, 2014.

[32]

R. Clausen and A. Shehu, "Exploring the structure space of wildtype Ras guided by experimental data," in Proc. ACM Conf. Bioinf. Comput. Biol. Workshops, Sep. 2013, pp. 757-764.

[33]

R. Clausen, E. Sapin, K. A. De Jong, and A. Shehu, "Evolution strategies for exploring protein energy landscapes," in Proc. Annu. Conf. Genetic Evol. Comput., Jul. 2015, pp. 217-224.

[34]

R. Clausen and A. Shehu, "A multiscale hybrid evolutionary algorithm to obtain sample-based representations of multi-basin protein energy landscapes," in Proc. 5th ACM Conf. Bioinf. Comput. Biol. Health Inform., Sep. 2014, pp. 269-278.

[35]

R. Clausen and A. Shehu, "A data-driven evolutionary algorithm for mapping multi-basin protein energy landscapes," J. Comput. Biol., vol. 22, no. 9, pp. 844-860, 2015.

[36]

R. Clausen, B. Ma, R. Nussinov, and A. Shehu, "Mapping the conformation space of wildtype and mutant H-Ras with a memetic, cellular, and multiscale evolutionary algorithm," PLoS Comput. Biol., vol. 11, no. 9, 2015, Art. no. e1004470.

[37]

E. Sapin, K. A. De Jong, and A. Shehu, "Evolutionary search strategies for efficient sample-based representations of multiple-basin protein energy landscapes," in Proc. IEEE Int. Conf. Bioinf. Biomed., 2015, pp. 13-20.

[38]

E. Anderson, et al., "LAPACK: A portable linear algebra library for high-performance computers," in Proc. ACM/IEEE Conf. Supercomputing, 1990, pp. 2-11.

[39]

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, vol. 49, no. 14, pp. 2987-2998, 2010.

[40]

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., vol. 28, no. 29, pp. 1593-1597, 2007.

[41]

M. W. Chang, "Computational structure-based methods to anticipate HIV drug resistance evolution and accelerate inhibitor discovery," Ph.D. dissertation, Department of Bioinformatics, Univ. California, San Diego, 2008.

[42]

C. Tsai, B. Ma, and R. Nussinov, "Folding and binding cascades: Shifts in energy landscapes," Proc. Nat. Academy Sci. United States America, vol. 96, no. 18, pp. 9970-9972, 1999.

[43]

J. Gsponer, et al., "A coupled equilibrium shift mechanism in calmodulin-mediated signal transduction," Structure, vol. 16, no. 5, pp. 736-746, 2008.

[44]

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., vol. 328, no. 1, pp. 193-204, 2003.

[45]

B. W. Zhang, D. Jasnow, and D. M. Zuckermann, "Efficient and verified simulation of a path ensemble for conformational change in a united-residue model of calmodulin," Proc. Nat. Acad. Sci. United States America, vol. 104, no. 46, pp. 18043-18048, 2007.

[46]

M. V. Milburn, et al., "Molecular switch for signal transduction: Structural differences between active and inactive forms of protooncogenic Ras proteins," Science, vol. 247, no. 4945, pp. 939-945, 1990.

[47]

A. J. Scheidig, C. Burmester, and R. S. Goody, "The pre-hydrolysis state of p21(Ras) in complex with GTP: New insights into the role of water molecules in the GTP hydrolysis reaction of Ras-like proteins," Structure, vol. 7, no. 11, pp. 1311-1324, 1999.

[48]

M. Teodoro, G. N. J. Phillips, and L. E. Kavraki, "Understanding protein flexibility through dimensionality reduction," J. Comput. Biol., vol. 10, no. 3-4, pp. 617-634, 2003.

[49]

A. E. Karnoub and R. A. Weinberg, "Ras oncogenes: Split personalities," Nature Rev. Mol. Cell Biol., vol. 9, no. 7, pp. 517-531, 2008.

[50]

A. Fernández-Medarde and E. Santos, "Ras in cancer and developmental diseases," Genes Cancer, vol. 2, no. 3, pp. 344-358, 2011.

[51]

E. F. Pettersen, et al., "UCSF Chimera-a visualization system for exploratory research and analysis," J. Comput. Chem., vol. 25, no. 13, pp. 1605-1612, 2004.

[52]

B. E. Hall, D. Bar-Sagi, and N. Nassar, "The structural basis for the transition from Ras-GTP to Ras-GDP," Proc. Nat. Academy Sci. United States America, vol. 99, no. 19, pp. 12138-12142, 2002.

[53]

B. J. Grant, et al., "Novel allosteric sites on Ras for lead generation," PLoS One, vol. 6, no. 10, 2011, Art. no. e25711.

Cited By

Zaman AInan TDe Jong KShehu A(2023)Adaptive Stochastic Optimization to Improve Protein Conformation SamplingIEEE/ACM Transactions on Computational Biology and Bioinformatics10.1109/TCBB.2021.313410320:5(2759-2771)Online publication date: 1-Sep-2023
https://dl.acm.org/doi/10.1109/TCBB.2021.3134103
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
Alam FRahman TShehu AShi XBuck MMa JVeltri P(2019)Learning Reduced Latent Representations of Protein Structure DataProceedings of the 10th ACM International Conference on Bioinformatics, Computational Biology and Health Informatics10.1145/3307339.3343866(592-597)Online publication date: 4-Sep-2019
https://dl.acm.org/doi/10.1145/3307339.3343866

From Optimization to Mapping: An Evolutionary Algorithm for Protein Energy Landscapes
1. Applied computing
  1. Life and medical sciences

Recommendations

Improved biogeography-based optimisation

Biogeography-based optimisation (BBO) is one of the popular evolutionary algorithms, inspired by the theory of island biogeography. It has been successfully applied in various real world optimisation problems such as image segmentation, data clustering, ...
Artificial physics optimisation algorithm guided by diversity

In order to avoid the stagnation evolution of APO population, the thinking of dissipative structure theory and population diversity are combined in APO. Firstly, a chaos factor is introduced to judge whether the individuals doing dissipative movement or ...
Mapping the peaks: Fitness landscapes of the fittest and the flattest

Populations exposed to a high mutation rate harbor abundant deleterious genetic variation, leading to depressed mean fitness. This reduction in mean fitness presents an opportunity for selection to restore fitness through the evolution of mutational ...

Comments

Information & Contributors

Information

Published In

IEEE/ACM Transactions on Computational Biology and Bioinformatics Volume 15, Issue 3

May 2018

348 pages

ISSN:1545-5963

Issue’s Table of Contents

Copyright © 2018.

Publisher

IEEE Computer Society Press

Washington, DC, United States

Publication History

Published: 01 May 2018

Published in TCBB Volume 15, Issue 3

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
51
Total Downloads

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

Reflects downloads up to 24 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zaman AInan TDe Jong KShehu A(2023)Adaptive Stochastic Optimization to Improve Protein Conformation SamplingIEEE/ACM Transactions on Computational Biology and Bioinformatics10.1109/TCBB.2021.313410320:5(2759-2771)Online publication date: 1-Sep-2023
https://dl.acm.org/doi/10.1109/TCBB.2021.3134103
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
Alam FRahman TShehu AShi XBuck MMa JVeltri P(2019)Learning Reduced Latent Representations of Protein Structure DataProceedings of the 10th ACM International Conference on Bioinformatics, Computational Biology and Health Informatics10.1145/3307339.3343866(592-597)Online publication date: 4-Sep-2019
https://dl.acm.org/doi/10.1145/3307339.3343866

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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents