Wang–Landau sampling of the interplay between surface adsorption and folding of HP lattice proteins

Generic features associated with the adsorption of proteins on solid surfaces are reviewed within the framework of the hydrophobic-polar (HP) lattice protein model. The thermodynamic behaviour and structural properties of various HP protein sequences interacting with attractive surfaces have been studied using extensive Wang–Landau sampling with different types of surfaces, each of which attracts either: all monomers, only hydrophobic (H) monomers or only polar (P) monomers, respectively. Consequently, different types of folding behaviour occur for varied surface strengths. Analysis of the combined patterns of various structural observables, e.g. the derivatives of the number of interaction contacts, together with the specific heat, leads to the identification of fundamental categories of folding and transition hierarchies. We also inferred a connection between the transition categories and the relative surface strengths, i.e. the ratios of the surface attractive strengths to the intra-chain attraction among H monomers. Thus, we believe that the folding hierarchies and identification scheme are generic for different HP sequences interacting with attractive surfaces, regardless of the chain length, sequence or surface attraction.     

A branch and bound algorithm for the protein folding problem in the HP lattice model

A branch and bound algorithm is proposed for the two-dimensional protein folding problem in the HP lattice model. In this algorithm, the benefit of each possible location of hydrophobic monomers is evaluated and only promising nodes are kept for further branching at each level. The proposed algorithm is compared with other well-known methods for 10 benchmark sequences with lengths ranging from 20 to 100 monomers. The results indicate that our method is a very efficient and promising tool for the protein folding problem.     

The optimal fraction of hydrophobic residues required to ensure protein collapse

The hydrophobic interaction is the main driving force for protein folding. Here, we address the question of what is the optimal fraction, f of hydrophobic (H) residues required to ensure protein collapse. For very small f (say f<0.1), the protein chain is expected to behave as a random coil, where the H residues are "wrapped" locally by polar (P) residues. However, for large enough f this local coverage cannot be achieved and the thermodynamic alternative to avoid contact with water is burying the H residues in the interior of a compact chain structure. The interior also contains P residues that are known to be clustered to optimize their electrostatic interactions. This means that the H residues are clustered as well, i.e. they effectively attract each other like the H-monomers in Dill's HP lattice model. Previously, we asked the question: assuming that the H monomers in the HP model are distributed randomly along the chain, what fraction of them is required to ensure a compact ground state? We claimed there that f approximately p(c), where p(c) is the site percolation threshold of the lattice (in a percolation experiment, each site of an initially empty lattice is visited and a particle is placed there with a probability p. The interest is in the critical (minimal) value, p(c), for which percolation occurs, i.e. a cluster connecting the opposite sides of the lattice is created). Due to the above correspondence between the HP model and real proteins (and assuming that the H residues are distributed at random) we suggest that the experimental f should lead to percolating clusters of H residues over the highly dense protein core, i.e. clusters of the core size. To check this theory, we treat a simplified model consisting of H and P residues represented by their alpha-carbon atoms only. The structure is defined by the C(alpha)-C(alpha) virtual bond lengths, angles and dihedral angles, and the X-ray structure is best-fitted onto a face-centered cubic lattice. Percolation experiments are carried out for 103 single-chain proteins using six different hydrophobic sets of residues. Indeed, on average, percolating clusters are generated, which supports our theory; however, some sets lead to a better core coverage than others. We also calculate the largest actual hydrophobic cluster of each protein and show that, on average, these clusters span the core, again in accord with our theory. We discuss the effect of protein size, deviations from the average picture, and implications of this study for defining reliable simplified models of proteins.     

Unique Optimal Foldings of Proteins on a Triangular Lattice

Background: A problem for unique protein folding was raised in 1998: are there proteins having unique optimal foldings for all lengths in the hydrophobic-hydrophilic (hydrophobic-polar; HP) model? To such a question, it was proved that on a square lattice there are (i) closed chains of monomers having unique optimal foldings for all even lengths and (ii) open monomer chains having unique optimal foldings for all lengths divisible by four. In this article, we aim to extend the previous work on a square lattice to the optimal foldings of proteins on a triangular lattice by examining the uniqueness property or stability of HP chain folding. Method: We consider this protein folding problem on a triangular lattice using graph theory. For an HP chain with length n > 13, generally it is very time-consuming to enumerate all of its possible folding conformations. Hence, one can hardly know whether or not it has a unique optimal folding. A natural problem is to determine for what value of n there is an n-node HP chain that has a unique optimal folding on a triangular lattice. Results and conclusion: Using graph theory, this article proves that there are both closed and open chains having unique optimal foldings for all lengths >19 in a triangular lattice. This result is not only general from the theoretical viewpoint, but also can be expected to apply to areas of protein structure prediction and protein design because of their close relationship with the concept of energy state and designability.     

A model study of protein nascent chain and cotranslational folding using hydrophobic-polar residues

To study protein nascent chain folding during biosynthesis, we investigate the folding behavior of models of hydrophobic and polar (HP) chains at growing length using both two-dimensional square lattice model and an optimized three-dimensional 4-state discrete off-lattice model. After enumerating all possible sequences and conformations of HP heteropolymers up to length N = 18 and N = 15 in two and three-dimensional space, respectively, we examine changes in adopted structure, stability, and tolerance to single point mutation as the nascent chain grows. In both models, we find that stable model proteins have fewer folded nascent chains during growth, and often will only fold after reaching full length. For the few occasions where partial chains of stable proteins fold, these partial conformations on average are very similar to the corresponding parts of the final conformations at full length. Conversely, we find that sequences with fewer stable nascent chains and sequences with native-like folded nascent chains are more stable. In addition, these stable sequences in general can have many more point mutations and still fold into the same conformation as the wild type sequence. Our results suggest that stable proteins are less likely to be trapped in metastable conformations during biosynthesis, and are more resistant to point-mutations. Our results also imply that less stable proteins will require the assistance of chaperone and other factors during nascent chain folding. Taken together with other reported studies, it seems that cotranslational folding may not be a general mechanism of in vivo protein folding for small proteins, and in vitro folding studies are still relevant for understanding how proteins fold biologically.     

Comparative modeling and protein-like features of hydrophobic-polar models on a two-dimensional lattice

Lattice models of proteins have been extensively used to study protein thermodynamics, folding dynamics, and evolution. Our study considers two different hydrophobic-polar (HP) models on the 2D square lattice: the purely HP model and a model where a compactness-favoring term is added. We exhaustively enumerate all the possible structures in our models and perform the study of their corresponding folds, HP arrangements in space and shapes. The two models considered differ greatly in their numbers of structures, folds, arrangements, and shapes. Despite their differences, both lattice models have distinctive protein-like features: (1) Shapes are compact in both models, especially when a compactness-favoring energy term is added. (2) The residue composition is independent of the chain length and is very close to 50% hydrophobic in both models, as we observe in real proteins. (3) Comparative modeling works well in both models, particularly in the more compact one. The fact that our models show protein-like features suggests that lattice models incorporate the fundamental physical principles of proteins. Our study supports the use of lattice models to study questions about proteins that require exactness and extensive calculations, such as protein design and evolution, which are often too complex and computationally demanding to be addressed with more detailed models.     

A quasi-physical algorithm for the structure optimization in an off-lattice protein model

Introduction Predicting the native structure of a protein from its amino acid sequence is one of the most challeng- ing problems in biophysics and bioinformatics. The difficulty of the problem comes from two aspects. One is the determination of the potential energy func- tion. The effective energy function can generally dis- tinguish the native states from non-native states of protein molecules. The other is that the potential en- ergy landscape of the system can be characterized by a multitu…     

A statistical mechanical model for hydrogen exchange in globular proteins.

We develop a statistical mechanical theory for the mechanism of hydrogen exchange in globular proteins. Using the HP lattice model, we explore how the solvent accessibilities of chain monomers vary as proteins fluctuate from their stable native conformations. The model explains why hydrogen exchange appears to involve two mechanisms under different conditions of protein stability; (1) a “global unfolding” mechanism by which all protons exchange at a similar rate, approaching that of the denatured protein, and (2) a “stable-state” mechanism by which protons exchange at rates that can differ by many orders of magnitude. There has been some controversy about the stable-state mechanism: does exchange take place inside the protein by solvent penetration, or outside the protein by the local unfolding of a subregion? The present model indicates that the stable-state mechanism of exchange occurs through an ensemble of conformations, some of which may bear very little resemblance to the native structure. Although most fluctuations are small-amplitude motions involving solvent penetration or local unfolding, other fluctuations (the conformational distant relatives) can involve much larger transient excursions to completely different chain folds.     

The twilight zone between protein order and disorder

The amino acid composition of intrinsically disordered proteins and protein segments characteristically differs from that of ordered proteins. This observation forms the basis of several disorder prediction methods. These, however, usually perform worse for smaller proteins (or segments) than for larger ones. We show that the regions of amino acid composition space corresponding to ordered and disordered proteins overlap with each other, and the extent of the overlap (the “twilight zone”) is larger for short than for long chains. To explain this finding, we used two-dimensional lattice model proteins containing hydrophobic, polar, and charged monomers and revealed the relation among chain length, amino acid composition, and disorder. Because the number of chain configurations exponentially grows with chain length, a larger fraction of longer chains can reach a low-energy, ordered state than do shorter chains. The amount of information carried by the amino acid composition about whether a protein or segment is (dis)ordered grows with increasing chain length. Smaller proteins rely more on specific interactions for stability, which limits the possible accuracy of disorder prediction methods. For proteins in the “twilight zone”, size can determine order, as illustrated by the example of two-state homodimers.     

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.     

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.     

Application of a chaperone-based refolding method to two- and three-dimensional off-lattice protein models

A model of protein-chaperone interaction as a two-phase (unfolding/refolding) iterative annealing mechanism able to promote structural segregation of hydrophobic and hydrophilic monomers and thereby facilitate access to nativelike states has recently been applied successfully to two 22-mers of the Honeycutt and Thirumalai BLN (hydrophobic, hydrophilic, neutral) heteropolymer model. This technique is here applied to a much wider data set: 94 8-mers of the off-lattice protein model originally presented in two dimensions by Stillinger and Head-Gordon, and later extended into three dimensions by Irb?ck and Potthast; the model chaperone is shown to be equally successful, and by progressive elaboration of the chaperone model as in the earlier BLN model work, to be utilizing very similar underlying mechanisms. It is demonstrated that on average, contacts with the model chaperone give rise to a consistent movement in structure space in the direction of more nativelike structures; this method of global minimization does not therefore rely fundamentally on random search. Insofar as the responses to the chaperone of the two- and three-dimensional forms of the substrate model do differ, this can be interpreted as reflecting the different handling of hydrophilic monomers in the models-in particular, whether there is active repulsion between these and monomers of hydrophobic character. The chaperone-induced refolding method is also tested on a set of 220 9-mer chains of each version of the substrate model, where it is seen that the two-dimensional model, with its more clearly distinguished roles for the hydrophobic and hydrophilic monomers, shows a more favorable scaling behavior.     

Influence of substrate pattern on the adsorption of HP lattice proteins

With the highly simplified hydrophobic-polar model representation of a protein, we can study essential qualitative physics without an unnecessarily large computational overhead. Using Wang-Landau sampling in conjunction with a set of efficient Monte Carlo trial moves, we studied the adsorption of short HP lattice proteins on various simple patterned substrates and in particular for checkered patterned surfaces. A set of single-site mutated HP proteins is used to investigate the role of hydrophobicity of a protein chain and surface pattern for substrates with various pattern cell sizes relative to the protein’s native configuration. For most cases, we found that the adsorption transition occurs at a lower temperature, while the hydrophobic core formation is less affected. The flattening procedure after the HP protein is adsorbed is more sensitive to the change in surface patterns and single-site mutations. These observations stay valid for both strongly and weakly attractive surfaces.     

Enumerating Designing Sequences in the HP Model

The hydrophobic/polar HP model on the square lattice has been widely used toinvestigate basics of protein folding. In the cases where all designing sequences (sequences with unique ground states) were enumerated without restrictions on the number of contacts, the upper limit on the chain length N has been 18–20 because of the rapid exponential growth of thenumbers of conformations and sequences. We show how a few optimizations push this limit by about 5 units. Based on these calculations, we study the statistical distribution of hydrophobicity along designing sequences. We find that the average number of hydrophobic and polar clumps along the chains is larger for designing sequences than for random ones, which is in agreement with earlier findings for N 18 and with results for real enzymes. We also show that this deviation from randomness disappears if the calculations are restricted to maximally compact structures.     

How native proteins aggregate in solution: a dynamic Monte Carlo simulation

Aggregation of native proteins in solution is of fundamental importance with regard to both the processing and the utilization of proteins. In the present work, a dynamic Monte Carlo simulation has been performed to give a molecular insight into the way in which native proteins aggregate in solution and to explore means of suppressing aggregation, using two proteins of different compositions and conformations represented by a two-dimensional (2D) lattice model (HP model). It is shown that the native HP protein with accessible hydrophobic beads on its surface is prone to aggregation. The aggregation of this protein is intensified when the solution conditions favor the partially unfolded conformation as opposed to either the native or fully unfolded conformations. In this case, the partially unfolded proteins form the cores of aggregates, which may also encapsulate the native protein. One way to inhibit protein aggregation is to introduce polymers of appropriate hydrophobicity and chain length into the solution, such that these polymer molecules wrap around the hydrophobic regions of both the unfolded and folded proteins, thereby segregating the protein molecules. Our simulation is consistent with experimental observations reported elsewhere and provides a molecular basis for the behavior of proteins in liquid environments.     

Efficient algorithms for protein sequence design and the analysis of certain evolutionary fitness landscapes.

Protein sequence design is a natural inverse problem to protein structure prediction: given a target structure in three dimensions, we wish to design an amino acid sequence that is likely fold to it. A model of Sun, Brem, Chan, and Dill casts this problem as an optimization on a space of sequences of hydrophobic (H) and polar (P) monomers; the goal is to find a sequence that achieves a dense hydrophobic core with few solvent-exposed hydrophobic residues. Sun et al. developed a heuristic method to search the space of sequences, without a guarantee of optimality or near-optimality; Hart subsequently raised the computational tractability of constructing an optimal sequence in this model as an open question. Here we resolve this question by providing an efficient algorithm to construct optimal sequences; our algorithm has a polynomial running time, and performs very efficiently in practice. We illustrate the implementation of our method on structures drawn from the Protein Data Bank. We also consider extensions of the model to larger amino acid alphabets, as a way to overcome the limitations of the binary H/P alphabet. We show that for a natural class of arbitrarily large alphabets, it remains possible to design optimal sequences efficiently. Finally, we analyze some of the consequences of this sequence design model for the study of evolutionary fitness landscapes. A given target structure may have many sequences that are optimal in the model of Sun et al.; following a notion raised by the work of J. Maynard Smith, we can ask whether these optimal sequences are "connected" by successive point mutations. We provide a polynomial-time algorithm to decide this connectedness property, relative to a given target structure. We develop the algorithm by first solving an analogous problem expressed in terms of submodular functions, a fundamental object of study in combinatorial optimization.     

Exploring zipping and assembly as a protein folding principle

It has been proposed that proteins fold by a process called "Zipping and Assembly" (Z&A). Zipping refers to the growth of local substructures within the chain, and assembly refers to the coming together of already-formed pieces. Our interest here is in whether Z&A is a general method that can fold most of sequence space, to global minima, efficiently. Using the HP model, we can address this question by enumerating full conformation and sequence spaces. We find that Z&A reaches the global energy minimum native states, even though it searches only a very small fraction of conformational space, for most sequences in the full sequence space. We find that Z&A, a mechanism-based search, is more efficient in our tests than the replica exchange search method. Folding efficiency is increased for chains having: (a) small loop-closure steps, consistent with observations by Plaxco et al. 1998;277;985-994 that folding rates correlate with contact order, (b) neither too few nor too many nucleation sites per chain, and (c) assembly steps that do not occur too early in the folding process. We find that the efficiency increases with chain length, although our range of chain lengths is limited. We believe these insights may be useful for developing faster protein conformational search algorithms.     

一种在格点模型上模拟蛋白质折叠结构的优化算法

蛋白质折叠问题是生物信息学中一个经典的多项式复杂程度的非确定性(non-deterministic polynomial,NP)难度问题.势能曲面变平法(ELP)是一种启发式的全局优化算法.通过对ELP方法中的直方图函数提出一种新的更新机制,并将基于贪心策略的初始构象的产生,基于牵引移动的邻域搜索策略与ELP方法相结合,为面心立方体(FCC)格点模型的蛋白质折叠问题提出一种改进的势能曲面变平(ELP+)算法.采用文献中9条常用序列作为测试集.对于每条序列,ELP+算法均能找到与文献中的算法所得到的最低能量相等或更低的能量.实验结果表明,ELP+算法是求解FCC格点模型的蛋白质折叠问题的一种有效算法.     

Enhanced hybrid search algorithm for protein structure prediction using the 3D-HP lattice model

The problem of protein structure prediction in the hydrophobic-polar (HP) lattice model is the prediction of protein tertiary structure. This problem is usually referred to as the protein folding problem. This paper presents a method for the application of an enhanced hybrid search algorithm to the problem of protein folding prediction, using the three dimensional (3D) HP lattice model. The enhanced hybrid search algorithm is a combination of the particle swarm optimizer (PSO) and tabu search (TS) algorithms. Since the PSO algorithm entraps local minimum in later evolution extremely easily, we combined PSO with the TS algorithm, which has properties of global optimization. Since the technologies of crossover and mutation are applied many times to PSO and TS algorithms, so enhanced hybrid search algorithm is called the MCMPSO-TS (multiple crossover and mutation PSO-TS) algorithm. Experimental results show that the MCMPSO-TS algorithm can find the best solutions so far for the listed benchmarks, which will help comparison with any future paper approach. Moreover, real protein sequences and Fibonacci sequences are verified in the 3D HP lattice model for the first time. Compared with the previous evolutionary algorithms, the new hybrid search algorithm is novel, and can be used effectively to predict 3D protein folding structure. With continuous development and changes in amino acids sequences, the new algorithm will also make a contribution to the study of new protein sequences.     

Structure optimization in a three-dimensional off-lattice protein model

We studied a three-dimensional off-lattice AB model with two species of monomers, hydrophobic (A) and hydrophilic (B), and present two optimization algorithms: face-centered-cubic (FCC)-lattice pruned-enriched-Rosenbluth method (PERM) and subsequent conjugate gradient (PERM++) minimization and heuristic conjugate gradient (HCG) simulation based on "off-trap" strategy. In PERM++, we apply the PERM to the FCC-lattice to produce the initial conformation, and conjugate gradient minimization is then used to reach the minimum energy state. Both algorithms have been tested in the three-dimensional AB model for all sequences with lengths 13 < or = n < or = 55. The numerical results show that the proposed methods are very promising for finding the ground states of proteins. In several cases, we renew the putative ground states energy values.