An extremal optimization search method for the protein folding problem: the go-model example

ABSTRACT

The protein folding problem consists of predicting the functional (native)structure of the protein given its linear sequence of amino acids. Despite extensive progress made in understanding the process of protein folding, this problem still remains extremely challenging.

In this paper we introduce, implement and evaluate the Extremal Optimization method - a biologically inspired approach which has been applied very successfully to other optimization problems - for the protein folding problem using a widely studied Gō-model of folding.

Standard methods based on the variants of the Monte Carlo method have difficulty exploring low-energy regions efficiently due to the ruggedness of the search landscapes. Most computational methods in the protein folding literature do not keep track of which interactions remain unsatisfied during the search. Instead, in this paper, we propose an adaptive meta-search method which ensures that unexplored promising parts of the search landscape are visited. This is achieved by implementing an adaptive Extremal Optimization meta-search that guides a standard Monte Carlo sampling.

We demonstrate that our Extremal Optimization meta-search compares favorably with currently best-performing Replica Exchange Monte Carlo method in reaching the native state for long proteins under the Gō-model potential. Additionally, we show that our novel approach samples larger ensembles of near-native structures by plotting parts of the energy landscape sampled during the search. Furthermore, we find that it scales well with the increasing sequence length. To our best knowledge this is the first application of Extremal Optimization to the protein folding problem.

REFERENCES

• 1: E. Alm and D. Baker. Prediction of protein-folding mechanisms from free-energy landscapes derived from native structures. Proc. Natl. Acad. Sci. U.S.A., 96:11305--11310, 1999.
• 2: P. Bak and K. Sneppen. Punctuated equilibrium and criticality in a simple model of evolution. Phys. Rev. Lett., 71:4083--4086, 1993.
• 3: Stefan Boettcher, Extremal optimization: heuristics via coevolutionary avalanches, Computing in Science and Engineering, v.2 n.6, p.75-82, Nov. 2000 [doi>10.1109/5992.881710]
• 4: S. Boettcher. Extremal optimization for sherrington-kirkpatrick spin glasses. Eur. Phys. J. B, 46:501--505, 2005.
• 5: S. Boettcher and A. G. Percus. Extremal optimization: Methods derived from co-evolution. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO), pages 825--832, 1999.
• 6: S. Boettcher and A. G. Percus. Combining local search with co-evolution in a remarkably simple way. In Proceedings of the 2000 Congress on Evolutionary Computation, pages 1578--1584, 2000.
• 7: T J Brunette , Oliver Brock, Improving protein structure prediction with model-based search, Bioinformatics, v.21 n.1, p.66-74, January 2005 [doi>10.1093/bioinformatics/bti1029]
• 8: C. Clementi, H. Nymeyer, and J. N. Onuchic. Topological and energetic factors: What determines the structural details of the transition state ensemble and en-route intermediates for protein folding? an investigation for small globular proteins. J. Mol. Biol., 298:937--953, 2000.
• 9: Fred Glover , Fred Laguna, Tabu Search, Kluwer Academic Publishers, Norwell, MA, 1997
• 10: U. H. E. Hansmann. Protein folding simulations in a deformed energy landscape. Eur. Phys. J. B, 12:607--611, 1999.
• 11: J. Karanicolas and C. L. Brooks III. The origin of asymmetry in the folding transition states of protein land protein g. Protein Sci., 11:2351--2361, 2002.
• 12: A. Mitsutake, Y. Sugita, and Y. Okamoto. Generalized-ensemble algorithms for molecular simulations of biopolymers. Biopolymers (Peptide Sci.), 60:96--123, 2001.
• 13: V. Munoz and W. A. Eaton. A simple model for calculating the kinetics of protein folding from three-dimensional structures. Proc. Natl. Acad. Sci. U.S.A., 96:11311--11316, 1999.
• 14: J. T. Ngo, J. Marks, and M. Karplus. Computational complexity: Protein structure prediction and the levinthal paradox. Protein Eng., 5:313--321, 1992.
• 15: Y. Okamoto. Generalized-ensemble algorithms: Enhanced sampling techniques for monte carlo and molecular dynamic simulations. J. Mol. Graphics Modell., 22:425--439, 2004.
• 16: J. N. Onuchic, Z. Luthey-Schulten, and P. G. Wolynes. The energy landscape perspective. Annu. Rev. Phys. Chem., 48:545--600, 1997.
• 17: A. R. Ortiz, A. Kolinski, P. Rotkiewicz, B. Ilkowski, and J. Skolnick. Ab initio folding of proteins using restrains derived from evolutionary information. Proteins Suppl., 3:177--185, 1999.
• 18: E. Paci, M. Vendruscolo, and M. Karplus. Validity of go models: Comparison with a solvent-shielded empirical energy decomposition. Biophys. J., 83:3032--3038, 2002.
• 19: K. Simons, C. Kooperberg, E. Huang, and D. Baker. Assembly of protein tertiary structures from fragments with similar local sequences using simulated annealing and bayesian scoring function. J. Mol. Biol., 268:209--225, 1997.
• 20: J. Skolnick, A. Kolinski, D. Kihara, M. Betancourt, P. Rotkiewicz, and M. Boniecki. Ab initio protein structure prediction via a combination of threading, lattice folding, clustering, and structure refinement. Proteins Suppl., 5:149--156, 2001.
• 21: Y. Sugita and Y. Okamoto. Replica-exchange multicanonical algorithm and multicanonical replica-exchange method for simulating systems with rough energy landscape. Chem. Phys. Lett., 329:261--270, 2004.
• 22: S. Takada. Go-ing for the prediction of protein folding mechanisms. Proc. Natl. Acad. Sci. U.S.A., 96:11698--11700, 1999.
• 23: H. Taketomi, Y. Ueda, and N. Go. Studies on protein folding, unfolding and fluctuations by computer simulation. i. the effect of specific amino acid sequence represented by specific inter-unit interactions. Int. J. Pept. Protein Res., 7:445--459, 1975.
• 24: R. Unger and J. Moult. Finding the lowest free energy conformation of a protein is a np-hard problem: Proof and implications. Bull. Math. Biol., 55:1183--1198, 1993.
• 25: Y. Zhang, A. K. Arakaki, and J. Skolnick. Tasser: A automated method for the prediction of protein tertiary structures in casp6. Proteins Suppl., 61:91--8, 2005.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search

General Terms:
Algorithms

Keywords:
extremal optimization, go-model, protein folding