A test of lattice protein folding algorithms

Secondary-structure-favored hydrophobic-polar lattice model of protein folding

Protein folding is studied using a two-dimensional lattice model with the Hamiltonian including both hydrophobic interactions and main chain hydrogen bond interactions of amino acids. Since compact conformations have different designabilities and only highly designable conformations can act as native structural candidates [H. Li, R. Helling, C. Tang, and N. Wingreen, Science 273, 666 (1996)], it is shown that hydrophobic interaction alone is insufficient to explain the appearance of a high proportion of regular secondary structures, especially beta sheets whose content decreases with increasing designability, but interactions of main chain hydrogen bonds can account for this. Thus the emergence of only a small number of structure types (folds) among all possible structures can be understood to some extent.

Kinetics and thermodynamics of protein adsorption: a generalized molecular theoretical approach

The thermodynamics and kinetics of protein adsorption are studied using a molecular theoretical approach. The cases studied include competitive adsorption from mixtures and the effect of conformational changes upon adsorption. The kinetic theory is based on a generalized diffusion equation in which the driving force for motion is the gradient of chemical potentials of the proteins. The time-dependent chemical potentials, as well as the equilibrium behavior of the system, are obtained using a molecular mean-field theory. The theory provides, within the same theoretical formulation, the diffusion and the kinetic (activated) controlled regimes. By separation of ideal and nonideal contributions to the chemical potential, the equation of motion shows a purely diffusive part and the motion of the particles in the potential of mean force resulting from the intermolecular interactions. The theory enables the calculation of the time-dependent surface coverage of proteins, the dynamic surface tension, and the structure of the adsorbed layer in contact with the approaching proteins. For the case of competitive adsorption from a solution containing a mixture of large and small proteins, a variety of different adsorption patterns are observed depending upon the bulk composition, the strength of the interaction between the particles, and the surface and size of the proteins. It is found that the experimentally observed Vroman sequence is predicted in the case that the bulk solution is at a composition with an excess of the small protein, and that the interaction between the large protein and the surface is much larger than that of the smaller protein. The effect of surface conformational changes of the adsorbed proteins in the time-dependent adsorption is studied in detail. The theory predicts regimes of constant density and dynamic surface tension that are long lived but are only intermediates before the final approach to equilibrium. The implications of the findings to the interpretation of experimental observations is discussed.

Folding simulations of a three-dimensional protein model with a nonspecific hydrophobic energy function

We show that a nonspecific hydrophobic energy function can produce protein-like folding behavior of a three-dimensional protein model of 40 monomers in the cubic lattice when the native conformation is chosen judiciously. We confirm that monomer inside/outside segregation is a powerful criterion for the selection of appropriate structures, an idea that was recently proposed with basis on a general theoretical analysis and simulations of much simpler two-dimensional models.

Matching simulation and experiment: a new simplified model for simulating protein folding

Simulations of simplified protein folding models have provided much insight into solving the protein folding problem. We propose here a new off-lattice bead model, capable of simulating several different fold classes of small proteins. We present the sequence for an alpha/beta protein resembling the IgG-binding proteins L and G. The thermodynamics of the folding process for this model are characterized using the multiple multihistogram method combined with constant-temperature Langevin simulations. The folding is shown to be highly cooperative, with chain collapse nearly accompanying folding. Two parallel folding pathways are shown to exist on the folding free energy landscape. One pathway contains an intermediate--similar to experiments on protein G, and one pathway contains no intermediates-similar to experiments on protein L. The folding kinetics are characterized by tabulating mean-first passage times, and we show that the onset of glasslike kinetics occurs at much lower temperatures than the folding temperature. This model is expected to be useful in many future contexts: investigating questions of the role of local versus nonlocal interactions in various fold classes, addressing the effect of sequence mutations affecting secondary structure propensities, and providing a computationally feasible model for studying the role of solvation forces in protein folding.

De novo design and structural characterization of proteins and metalloproteins

De novo protein design has recently emerged as an attractive approach for studying the structure and function of proteins. This approach critically tests our understanding of the principles of protein folding; only in de novo design must one truly confront the issue of how to specify a protein's fold and function. If we truly understand proteins, it should be possible to design receptors, enzymes, and ion channels from scratch. Further, as this understanding evolves and is further refined, it should be possible to design proteins and biomimetic polymers with properties unprecedented in nature.

Modeling study on the validity of a possibly simplified representation of proteins

The folding characteristics of sequences reduced with a possibly simplified representation of five types of residues are shown to be similar to their original ones with the natural set of residues (20 types or 20 letters). The reduced sequences have a good foldability and fold to the same native structure of their optimized original ones. A large ground state gap for the native structure shows the thermodynamic stability of the reduced sequences. The general validity of such a five-letter reduction is further studied via the correlation between the reduced sequences and the original ones. As a comparison, a reduction with two letters is found not to reproduce the native structure of the original sequences due to its homopolymeric features.

Designing protein beta-sheet surfaces by Z-score optimization

Studies of lattice models of proteins have suggested that the appropriate energy expression for protein design may include nonthermodynamic terms to accommodate negative design concerns. One method, developed in lattice model studies, maximizes a quantity known as the " Z-score," which compares the lowest energy sequence whose ground state structure is the target structure to an ensemble of random sequences. Here we show that, in certain circumstances, the technique can be applied to real proteins. The resulting energy expression is used to design the beta-sheet surfaces of two real proteins. We find experimentally that the designed proteins are stable and well folded, and in one case is even more thermostable than the wild type.

A polar, solvent-exposed residue can be essential for native protein structure

BACKGROUND

A large energy gap between the native state and the non-native folded states is required for folding into a unique three-dimensional structure. The features that define this energy gap are not well understood, but can be addressed using de novo protein design. Previously, alpha(2)D, a dimeric four-helix bundle, was designed and shown to adopt a native-like conformation. The high-resolution solution structure revealed that this protein adopted a bisecting U motif. Glu7, a solvent-exposed residue that adopts many conformations in solution, might be involved in defining the unique three-dimensional structure of alpha(2)D.

RESULTS

A variety of hydrophobic and polar residues were substituted for Glu7 and the dynamic and thermodynamic properties of the resulting proteins were characterized by analytical ultracentrifugation, circular dichroism spectroscopy, and nuclear magnetic resonance spectroscopy. The majority of substitutions at this solvent-exposed position had little affect on the ability to fold into a dimeric four-helix bundle. The ability to adopt a unique conformation, however, was profoundly modulated by the residue at this position despite the similar free energies of folding of each variant.

CONCLUSIONS

Although Glu7 is not involved directly in stabilizing the native state of alpha(2)D, it is involved indirectly in specifying the observed fold by modulating the energy gap between the native state and the non-native folded states. These results provide experimental support for hypothetical models arising from lattice simulations of protein folding, and underscore the importance of polar interfacial residues in defining the native conformations of proteins.

Statistical theory of combinatorial libraries of folding proteins: energetic discrimination of a target structure

A self-consistent theory is presented that can be used to estimate the number and composition of sequences satisfying a predetermined set of constraints. The theory is formulated so as to examine the features of sequences having a particular value of Delta=E(f)-<E>(u), where E(f) is the energy of sequences when in a target structure and <E>(u) is an average energy of non-target structures. The theory yields the probabilities w(i)(alpha) that each position i in the sequence is occupied by a particular monomer type alpha. The theory is applied to a simple lattice model of proteins. Excellent agreement is observed between the theory and the results of exact enumerations. The theory provides a quantitative framework for the design and interpretation of combinatorial experiments involving proteins, where a library of amino acid sequences is searched for sequences that fold to a desired structure.

De novo protein design. I. In search of stability and specificity

We have developed a fully automated protein design strategy that works on the entire sequence of the protein and uses a full atom representation. At each step of the procedure, an all-atom model of the protein is built using the template protein structure and the current designed sequence. The energy of the model is used to drive a Monte Carlo optimization in sequence space: random moves are either accepted or rejected based on the Metropolis criterion. We rely on the physical forces that stabilize native protein structures to choose the optimum sequence. Our energy function includes van der Waals interactions, electrostatics and an environment free energy. Successful protein design should be specific and generate a sequence compatible with the template fold and incompatible with competing folds. We impose specificity by maintaining the amino acid composition constant, based on the random energy model. The specificity of the optimized sequence is tested by fold recognition techniques. Successful sequence designs for the B1 domain of protein G, for the lambda repressor and for sperm whale myoglobin are presented. We show that each additional term of the energy function improves the performance of our design procedure: the van der Waals term ensures correct packing, the electrostatics term increases the specificity for the correct native fold, and the environment solvation term ensures a correct pattern of buried hydrophobic and exposed hydrophilic residues. For the globin family, we show that we can design a protein sequence that is stable in the myoglobin fold, yet incompatible with the very similar hemoglobin fold.

Folding protein models with a simple hydrophobic energy function: the fundamental importance of monomer inside/outside segregation

The present study explores a "hydrophobic" energy function for folding simulations of the protein lattice model. The contribution of each monomer to conformational energy is the product of its "hydrophobicity" and the number of contacts it makes, i.e., E(h,c) = -Sigma N/i=1 c(i)h(i) = -(h.c) is the negative scalar product between two vectors in N-dimensional cartesian space: h = (h1,., hN), which represents monomer hydrophobicities and is sequence-dependent; and c = (c(1),., c(N)), which represents the number of contacts made by each monomer and is conformation-dependent. A simple theoretical analysis shows that restrictions are imposed concomitantly on both sequences and native structures if the stability criterion for protein-like behavior is to be satisfied. Given a conformation with vector c, the best sequence is a vector h on the direction upon which the projection of c - c is maximal, where c is the diagonal vector with components equal to c, the average number of contacts per monomer in the unfolded state. Best native conformations are suggested to be not maximally compact, as assumed in many studies, but the ones with largest variance of contacts among its monomers, i.e., with monomers tending to occupy completely buried or completely exposed positions. This inside/outside segregation is reflected on an apolar/polar distribution on the corresponding sequence. Monte Carlo simulations in two dimensions corroborate this general scheme. Sequences targeted to conformations with large contact variances folded cooperatively with thermodynamics of a two-state transition. Sequences targeted to maximally compact conformations, which have lower contact variance, were either found to have degenerate ground state or to fold with much lower cooperativity.

Origin of the designability of protein structures

We examined what determines the designability of two-letter codes (H and P) lattice proteins from three points of view. First, whether the native structure is searched within all possible structures or within maximally compact structures. Second, whether the structure of the used lattice is bipartite or not. Third, the effect of the length of the chain, namely, the number of monomers on the chain. We found that the bipartiteness of the lattice structure is not a main factor that determines the designability. Our results suggest that highly designable structures will be found when the length of the chain is sufficiently long to make the hydrophobic core consisting of a large enough number of monomers.

The importance of hydration for the kinetics and thermodynamics of protein folding: simplified lattice models

BACKGROUND

Recent studies have proposed various sources for the origin of cooperativity in simplified protein folding models. Important contributions to cooperativity that have been discussed include backbone hydrogen bonding, sidechain packing and hydrophobic interactions. Related work has also focused on which interactions are responsible for making the free energy of the native structure a pronounced global minimum in the free energy landscape. In addition, two-flavor bead models have been found to exhibit poor folding cooperativity and often lack unique native structures. We propose a simple multibody description of hydration with expectations that it might modify the free energy surface in such a way as to increase the cooperativity of folding and improve the performance of two-flavor models.

RESULTS

We study the thermodynamics and kinetics of folding for designed 36-mer sequences on a cubic lattice using both our solvation model and the corresponding model without solvation terms. Degeneracies of the native states are studied by enumerating the maximally compact states. The histogram Monte Carlo method is used to obtain folding temperatures, densities of states and heat capacity curves. Folding kinetics are examined by accumulating mean first-passage times versus temperature. Sequences in the proposed solvation model are found to have more unique ground states, fold faster and fold with more cooperativity than sequences in the nonsolvation model.

CONCLUSIONS

We find that the addition of a multibody description of solvation can improve the poor performance of two-flavor lattice models and provide an additional source for more cooperative folding. Our results suggest that a better description of solvation will be important for future theoretical protein folding studies.

Protein design: a perspective from simple tractable models

Recent progress in computational approaches to protein design builds on advances in statistical mechanical protein folding theory. Here, the number of sequences folding into a given conformation is evaluated and a simple condition for a protein model's designability is outlined.

Structure-based design of model proteins

A structure-based, sequence-design procedure is proposed in which one considers a set of decoy structures that compete significantly with the target structure in being low energy conformations. The decoy structures are chosen to have strong overlaps in contacts with the putative native state. The procedure allows the design of sequences with large and small stability gaps in a random-bond heteropolymer model in both two and three dimensions by an appropriate assignment of the contact energies to both the native and nonnative contacts. The design procedure is also successfully applied to the two-dimensional HP model.

Theory of protein folding: the energy landscape perspective

The energy landscape theory of protein folding is a statistical description of a protein's potential surface. It assumes that folding occurs through organizing an ensemble of structures rather than through only a few uniquely defined structural intermediates. It suggests that the most realistic model of a protein is a minimally frustrated heteropolymer with a rugged funnel-like landscape biased toward the native structure. This statistical description has been developed using tools from the statistical mechanics of disordered systems, polymers, and phase transitions of finite systems. We review here its analytical background and contrast the phenomena in homopolymers, random heteropolymers, and protein-like heteropolymers that are kinetically and thermodynamically capable of folding. The connection between these statistical concepts and the results of minimalist models used in computer simulations is discussed. The review concludes with a brief discussion of how the theory helps in the interpretation of results from fast folding experiments and in the practical task of protein structure prediction.

Statistical mechanics of simple models of protein folding and design

It is now believed that the primary equilibrium aspects of simple models of protein folding are understood theoretically. However, current theories often resort to rather heavy mathematics to overcome some technical difficulties inherent in the problem or start from a phenomenological model. To this end, we take a new approach in this pedagogical review of the statistical mechanics of protein folding. The benefit of our approach is a drastic mathematical simplification of the theory, without resort to any new approximations or phenomenological prescriptions. Indeed, the results we obtain agree precisely with previous calculations. Because of this simplification, we are able to present here a thorough and self contained treatment of the problem. Topics discussed include the statistical mechanics of the random energy model (REM), tests of the validity of REM as a model for heteropolymer freezing, freezing transition of random sequences, phase diagram of designed ("minimally frustrated") sequences, and the degree to which errors in the interactions employed in simulations of either folding and design can still lead to correct folding behavior.

How are model protein structures distributed in sequence space?

The figure-to-structure maps for all uniquely folding sequences of short hydrophobic polar (HP) model proteins on a square lattice is analyzed to investigate aspects considered relevant to evolution. By ranking structures by their frequencies, few very frequent and many rare structures are found. The distribution can be empirically described by a generalized Zipf's law. All structures are relatively compact, yet the most compact ones are rare. Most sequences falling to the same structure belong to "neutral nets." These graphs in sequence space are connected by point mutations and centered around prototype sequences, which tolerate the largest number (up to 55%) of neutral mutations. Profiles have been derived from these homologous sequences. Frequent structures conserve hydrophobic cores only while rare ones are sensitive to surface mutations as well. Shape space covering, i.e., the ability to transform any structure into most others with few point mutations, is very unlikely. It is concluded that many characteristic features of the sequence-to-structure map of real proteins, such as the dominance of few folds, can be explained by the simple HP model. In analogy to protein families, nets are dense and well separated in sequence space. Potential implications in better understanding the evolution of proteins and applications to improving database searches are discussed.

Progress in protein structure prediction

If protein structure prediction methods are to make any impact on the impending onerous task of analyzing the large numbers of unknown protein sequences generated by the ongoing genome-sequencing projects, it is vital that they make the difficult transition from computational 'gedankenexperiments' to practical software tools. This has already happened in the field of comparative modelling and is currently happening in the threading field. Unfortunately, there is little evidence of this transition happening in the field of ab initio tertiary-structure prediction.

Nucleation mechanisms in protein folding

Experiment and theory are converging on the importance of nucleation mechanisms in protein folding. These mechanisms do not use classic nuclei, which are well formed elements of structure present in ground states, but they use diffuse, extended regions, which are observed in transition states.

Theoretical studies of protein-folding thermodynamics and kinetics

Recently, protein-folding models have advanced to the point where folding simulations of protein-like chains of reasonable length (up to 125 amino acids) are feasible, and the major physical features of folding proteins, such as cooperativity in thermodynamics and nucleation mechanisms in kinetics, can be reproduced. This has allowed deep insight into the physical mechanism of folding, including the solution of the so-called 'Levinthal paradox'.

How to derive a protein folding potential? A new approach to an old problem

In this paper we introduce a novel method of deriving a pairwise potential for protein folding. The potential is obtained by an optimization procedure that simultaneously maximizes thermodynamic stability for all proteins in the database. When applied to the representative dataset of proteins and with the energy function taken in pairwise contact approximation, our potential scored somewhat better than existing ones. However, the discrimination of the native structure from decoys is still not strong enough to make the potential useful for ab initio folding. Our results suggest that the problem lies with pairwise amino acid contact approximation and/or simplified presentation of proteins rather than with the derivation of potential. We argue that more detail of protein structure and energetics should be taken into account to achieve energy gaps. The suggested method is general enough to allow us to systematically derive parameters for more sophisticated energy functions. The internal control of validity for the potential derived by our method is convergence to a unique solution upon addition of new proteins to the database. The method is tested on simple model systems where sequences are designed, using the preset "true" potential, to have low energy in a dataset of structures. Our procedure is able to recover the potential with correlation r approximately 91% with the true one and we were able to fold all model structures using the recovered potential. Other statistical knowledge-based approaches were tested using this model and the results indicate that they also can recover the true potential with high degree of accuracy.

A fast conformational search strategy for finding low energy structures of model proteins

We describe a new computer algorithm for finding low-energy conformations of proteins. It is a chain-growth method that uses a heuristic bias function to help assemble a hydrophobic core. We call it the Core-directed chain Growth method (CG). We test the CG method on several well-known literature examples of HP lattice model proteins [in which proteins are modeled as sequences of hydrophobic (H) and polar (P) monomers], ranging from 20-64 monomers in two dimensions, and up to 88-mers in three dimensions. Previous nonexhaustive methods--Monte Carlo, a Genetic Algorithm, Hydrophobic Zippers, and Contact Interactions--have been tried on these same model sequences. CG is substantially better at finding the global optima, and avoiding local optima, and it does so in comparable or shorter times. CG finds the global minimum energy of the longest HP lattice model chain for which the global optimum is known, a 3D 88-mer that has only been reachable before by the CHCC complete search method. CG has the potential advantage that it should have nonexponential scaling with chain length. We believe this is a promising method for conformational searching in protein folding algorithms.

How optimization of potential functions affects protein folding

The relationship between the optimization of the potential function and the foldability of theoretical protein models is studied based on investigations of a 27-mer cubic-lattice protein model and a more realistic lattice model for the protein crambin. In both the simple and the more complicated systems, optimization of the energy parameters achieves significant improvements in the statistical-mechanical characteristics of the systems and leads to foldable protein models in simulation experiments. The foldability of the protein models is characterized by their statistical-mechanical properties--e.g., by the density of states and by Monte Carlo folding simulations of the models. With optimized energy parameters, a high level of consistency exists among different interactions in the native structures of the protein models, as revealed by a correlation function between the optimized energy parameters and the native structure of the model proteins. The results of this work are relevant to the design of a general potential function for folding proteins by theoretical simulations.

Comparing folding codes for proteins and polymers

Proteins fold to unique compact native structures. Perhaps other polymers could be designed to fold in similar ways. The chemical nature of the monomer "alphabet" determines the "energy matrix" of monomer interactions-which defines the folding code, the relationship between sequence and structure. We study two properties of energy matrices using two-dimensional lattice models: uniqueness, the number of sequences that fold to only one structure, and encodability, the number of folds that are unique lowest-energy structures of certain monomer sequences. For the simplest model folding code, involving binary sequences of H (hydrophobic) and P (polar) monomers, only a small fraction of sequences fold uniquely, and not all structures can be encoded. Adding strong repulsive interactions results in a folding code with more sequences folding uniquely and more designable folds. Some theories suggest that the quality of a folding code depends only on the number of letters in the monomer alphabet, but we find that the energy matrix itself can be at least as important as the size of the alphabet. Certain multi-letter codes, including some with 20 letters, may be less physical or protein-like than codes with smaller numbers of letters because they neglect correlations among inter-residue interactions, treat only maximally compact conformations, or add arbitrary energies to the energy matrix.

Folding proteins with a simple energy function and extensive conformational searching

We describe a computer algorithm for predicting the three-dimensional structures of proteins using only their amino acid sequences. The method differs from others in two ways: (1) it uses very few energy parameters, representing hydrophobic and polar interactions, and (2) it uses a new "constraint-based exhaustive" searching method, which appears to be among the fastest and most complete search methods yet available for realistic protein models. It finds a relatively small number of low-energy conformations, among which are native-like conformations, for crambin (1CRN), avian pancreatic polypeptide (1PPT), melittin (2MLT), and apamin. Thus, the lowest-energy states of very simple energy functions may predict the native structures of globular proteins.

Contact interactions method: a new algorithm for protein folding simulations

Computer simulations of simple exact lattice models are an aid in the study of protein folding process; they have sometimes resulted in predictions experimentally proved. The contact interactions (CI) method is here proposed as a new algorithm for the conformational search in the low-energy regions of protein chains modeled as copolymers of hydrophobic and polar monomers configured as self-avoiding walks on square or cubic lattices. It may be regarded as an extension of the standard Monte Carlo method improved by the concept of cooperativity deriving from nonlocal contact interactions. A major difference with respect to other algorithms is that criteria for the acceptance of new conformations generated during the simulations are not based on the energy of the entire molecule, but cooling factors associated with each residue define regions of the model protein with higher or lower mobility. Nine sequences of length ranging from 20 to 64 residues were used on the square lattice and 15 sequences of length ranging from 46 to 136 residues were used on the cubic lattice. The CI algorithm proved very efficient both in two and three dimensions, and allowed us to localize energy minima not localized by other searching algorithms described in the literature. Use of this algorithm is not limited to the conformational search, because it allows the exploration of thermodynamic and kinetic behavior of model protein chains.

Fast protein folding in the hydrophobic-hydrophilic model within three-eighths of optimal

We present performance-guaranteed approximation algorithms for the protein folding problem in the hydrophobic-hydrophilic model (Dill, 1985). Our algorithms are the first approximation algorithms in the literature with guaranteed performance for this model (Dill, 1994). The hydrophobic-hydrophilic model abstracts the dominant force of protein folding: the hydrophobic interaction. The protein is modeled as a chain of amino acids of length n that are of two types; H (hydrophobic, i.e., nonpolar) and P (hydrophilic, i.e., polar). Although this model is a simplification of more complex protein folding models, the protein folding structure prediction problem is notoriously difficult for this model. Our algorithms have linear (3n) or quadratic time and achieve a three-dimensional protein conformation that has a guaranteed free energy no worse than three-eighths of optimal. This result answers the open problem of Ngo et al. (1994) about the possible existence of an efficient approximation algorithm with guaranteed performance for protein structure prediction in any well-studied model of protein folding. By achieving speed and near-optimality simultaneously, our algorithms rigorously capture salient features of the recently proposed framework of protein folding by Sali et al. (1994). Equally important, the final conformations of our algorithms have significant secondary structure (antiparallel sheets, beta-sheets, compact hydrophobic core). Furthermore, hypothetical folding pathways can be described for our algorithms that fit within the framework of diffusion-collision protein folding proposed by Karplus and Weaver (1979). Computational limitations of algorithms that compute the optimal conformation have restricted their applicability to short sequences (length < or = 90). Because our algorithms trade computational accuracy for speed, they can construct near-optimal conformations in linear time for sequences of any size.