Fitting protein chains to cubic lattice is NP-complete

It is known that folding a protein chain into a cubic lattice is an NP-complete problem. We consider a seemingly easier problem: given a three-dimensional (3D) fold of a protein chain (coordinates of its C(alpha) atoms), we want to find the closest lattice approximation of this fold. This problem has been studied under names such as "lattice approximation of a protein chain", "the protein chain fitting problem", and "building of protein lattice models". We show that this problem is NP-complete for the cubic lattice with side close to 3.8 A and coordinate root mean square deviation.     

Routes are trees: the parsing perspective on protein folding

An important puzzle in structural biology is the question of how proteins are able to fold so quickly into their unique native structures. There is much evidence that protein folding is hierarchic. In that case, folding routes are not linear, but have a tree structure. Trees are commonly used to represent the grammatical structure of natural language sentences, and chart parsing algorithms efficiently search the space of all possible trees for a given input string. Here we show that one such method, the CKY algorithm, can be useful both for providing novel insight into the physical protein folding process, and for computational protein structure prediction. As proof of concept, we apply this algorithm to the HP lattice model of proteins. Our algorithm identifies all direct folding route trees to the native state and allows us to construct a simple model of the folding process. Despite its simplicity, our model provides an account for the fact that folding rates depend only on the topology of the native state but not on sequence composition.     

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.     

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.     

对预测蛋白质结构的拟物算法的分析和改进

对预测蛋白质空间结构的拟物算法的有效性进行理论分析,证明用该拟物算法求得合法的结构存在较大的随机性;给出折叠结构发生冲突的判断条件和提高拟物算法有效性的一些修正方案。     

Exploration of compact protein conformations using the guided replication monte carlo method

We have studied the use of a new Monte Carlo (MC) chain generation algorithm, introduced by T. Garel and H. Orland[(1990) Journal of Physics A, Vol. 23, pp. L621–L626], for examining the thermodynamics of protein folding transitions and for generating candidate C^αbackbone structures as starting points for a de now protein structure paradigm. This algorithm, termed the guided replication Monte Carlo method, allows a rational approach to the introduction of known “native” folded characteristics as constraints in the chain generation process. We have shown this algorithm to be computationally very efficient in generating large ensembles of candidate C^αchains on the face centered cubic lattice, and illustrate its use by calculating a number of thermodynamic quantities related to protein folding characteristics. In particular, we have used this static MC algorithm to compute such temperature-dependent quantities as the ensemble mean energy, ensemble mean free energy, the heat capacity, and the mean-square radius of gyration. We also demonstrate the use of several simple “guide fields” for introducing protein-specific constraints into the ensemble generation process. Several extensions to our current model are suggested, and applications of the method to other folding related problems are discussed. © 1995 John Wiley & Sons, Inc.     

An effective evolutionary algorithm for protein folding on 3D FCC HP model by lattice rotation and generalized move sets

Background

Proteins are essential biological molecules which play vital roles in nearly all biological processes. It is the tertiary structure of a protein that determines its functions. Therefore the prediction of a protein's tertiary structure based on its primary amino acid sequence has long been the most important and challenging subject in biochemistry, molecular biology and biophysics. In the past, the HP lattice model was one of the ab initio methods that many researchers used to forecast the protein structure. Although these kinds of simplified methods could not achieve high resolution, they provided a macrocosm-optimized protein structure. The model has been employed to investigate general principles of protein folding, and plays an important role in the prediction of protein structures.

Methods

In this paper, we present an improved evolutionary algorithm for the protein folding problem. We study the problem on the 3D FCC lattice HP model which has been widely used in previous research. Our focus is to develop evolutionary algorithms (EA) which are robust, easy to implement and can handle various energy functions. We propose to combine three different local search methods, including lattice rotation for crossover, K-site move for mutation, and generalized pull move; these form our key components to improve previous EA-based approaches.

Results

We have carried out experiments over several data sets which were used in previous research. The results of the experiments show that our approach is able to find optimal conformations which were not found by previous EA-based approaches.

Conclusions

We have investigated the geometric properties of the 3D FCC lattice and developed several local search techniques to improve traditional EA-based approaches to the protein folding problem. It is known that EA-based approaches are robust and can handle arbitrary energy functions. Our results further show that by extensive development of local searches, EA can also be very effective for finding optimal conformations on the 3D FCC HP model. Furthermore, the local searches developed in this paper can be integrated with other approaches such as the Monte Carlo and Tabu searches to improve their performance.

     

An evolutionary strategy for all-atom folding of the 60-amino-acid bacterial ribosomal protein l20

We have investigated an evolutionary algorithm for de novo all-atom folding of the bacterial ribosomal protein L20. We report results of two simulations that converge to near-native conformations of this 60-amino-acid, four-helix protein. We observe a steady increase of "native content" in both simulated ensembles and a large number of near-native conformations in their final populations. We argue that these structures represent a significant fraction of the low-energy metastable conformations, which characterize the folding funnel of this protein. These data validate our all-atom free-energy force field PFF01 for tertiary structure prediction of a previously inaccessible structural family of proteins. We also compare folding simulations of the evolutionary algorithm with the basin-hopping technique for the Trp-cage protein. We find that the evolutionary algorithm generates a dynamic memory in the simulated population, which leads to faster overall convergence.     

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

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

Use of machine learning algorithms to classify binary protein sequences as highly-designable or poorly-designable

Background

By using a standard Support Vector Machine (SVM) with a Sequential Minimal Optimization (SMO) method of training, Naïve Bayes and other machine learning algorithms we are able to distinguish between two classes of protein sequences: those folding to highly-designable conformations, or those folding to poorly- or non-designable conformations.

Results

First, we generate all possible compact lattice conformations for the specified shape (a hexagon or a triangle) on the 2D triangular lattice. Then we generate all possible binary hydrophobic/polar (H/P) sequences and by using a specified energy function, thread them through all of these compact conformations. If for a given sequence the lowest energy is obtained for a particular lattice conformation we assume that this sequence folds to that conformation. Highly-designable conformations have many H/P sequences folding to them, while poorly-designable conformations have few or no H/P sequences. We classify sequences as folding to either highly – or poorly-designable conformations. We have randomly selected subsets of the sequences belonging to highly-designable and poorly-designable conformations and used them to train several different standard machine learning algorithms.

Conclusion

By using these machine learning algorithms with ten-fold cross-validation we are able to classify the two classes of sequences with high accuracy – in some cases exceeding 95%.

     

Exploring the kinetic requirements for enhancement of protein folding rates in the GroEL cavity

The chaperonin system, GroEL and GroES of Escherichia coli enable certain proteins to fold under conditions when spontaneous folding is prohibitively slow as to compete with other non-productive channels such as aggregation. We investigated the plausible mechanisms of GroEL-mediated folding using simple lattice models. In particular, we have investigated protein folding in a confined environment, such as those offered by the GroEL, to decipher whether rate and yield enhancement can occur when the substrate protein is allowed to fold within the cavity of the chaperonins. The GroEL cavity is modeled as a cubic box and a simple bead model is used to represent the substrate chain. We consider three distinct characteristic of the confining environment. First, the cavity is taken to be a passive Anfinsen cage in which the walls merely reduce the available conformation space. We find that at temperatures when the native conformation is stable, the folding rate is retarded in the Anfinsen cage. We then assumed that the interior of the wall is hydrophobic. In this case the folding times exhibit a complex behavior. When the strength of the interaction between the polypeptide chain and the cavity is too strong or too weak we find that the rates of folding are retarded compared to spontaneous folding. There is an optimum range of the interaction strength that enhances the rates. Thus, above this value there is an inverse correlation between the folding rates and the strength of the substrate-cavity interactions. The optimal hydrophobic walls essentially pull the kinetically trapped states which leads to a smoother the energy landscape. It is known that upon addition of ATP and GroES the interior cavity of GroEL offers a hydrophilic-like environment to the substrate protein. In order to mimic this within the context of the dynamic Anfinsen cage model, we allow for changes in the hydrophobicity of the walls of the cavity. The duration for which the walls remain hydrophobic during one cycle of ATP hydrolysis is allowed to vary. These calculations show that frequent cycling of the wall hydrophobicity can dramatically reduce the folding times and increase the yield as well under non-permissive conditions. Examination of the structures of the substrate proteins before and after the change in hydrophobicity indicates that there is global unfolding involved. In addition, it is found that a fraction of the molecules kinetically partition to the native state in accordabce with the iterative annealing mechanism. Thus, frequent "unfoldase" activity of chaperonins leading to global unfolding of the polypeptide chain results in enhancement of the folding rates and yield of the folded protein. We suggest that chaperonin efficiency can be greatly enhanced if the cycling time is reduced. The calculations are used to interpret a few experiments on chaperonin-mediated protein folding.     

Improving genetic algorithms for protein folding simulations by systematic crossover

To improve protein folding simulations, we investigated a new search strategy in combination with the simple genetic algorithm on a two-dimensional lattice model. This search strategy, we called systematic crossover, couples the best individuals, tests every possible crossover point, and takes the two best individuals for the next generation. We compared the standard genetic algorithm with and without this new implementation for various chain lengths and showed that this strategy finds local minima with better energy values and is significantly faster in identifying the global minimum than the standard genetic algorithm.     

Minimum energy configurations of the 2-dimensional HP-model of proteins by self-organizing networks.

We use self-organizing maps (SOM) as an efficient tool to find the minimum energy configurations of the 2-dimensional HP-models of proteins. The usage of the SOM for the protein folding problem is similar to that for the Traveling Salesman Problem. The lattice nodes represent the cities whereas the neurons in the network represent the amino acids moving towards the closest cities, subject to the HH interactions. The valid path that maximizes the HH contacts corresponds to the minimum energy configuration of the protein. We report promising results for the cases when the protein completely fills a lattice and discuss the current problems and possible extensions. In all the test sequences up to 36 amino acids, the algorithm was able to find the global minimum and its degeneracies.     

Lattice simulations of aggregation funnels for protein folding.

A computer model of protein aggregation competing with productive folding is proposed. Our model adapts techniques from lattice Monte Carlo studies of protein folding to the problem of aggregation. However, rather than starting with a single string of residues, we allow independently folding strings to undergo collisions and consider their interactions in different orientations. We first present some background into the nature and significance of protein aggregation and the use of lattice Monte Carlo simulations in understanding other aspects of protein folding. The results of a series of simulation experiments involving simple versions of the model illustrate the importance of considering aggregation in simulations of protein folding and provide some preliminary understanding of the characteristics of the model. Finally, we discuss the value of the model in general and of our particular design decisions and experiments. We conclude that computer simulation techniques developed to study protein folding can provide insights into protein aggregation, and that a better understanding of aggregation may in turn provide new insights into and constraints on the more general protein folding problem.     

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.     

Fast tree search for a triangular lattice model of protein folding

Using a triangular lattice model to study the designability of protein folding, we overcame the parity problem of previous cubic lattice model and enumerated all the sequences and compact structures on a simple two-dimensional triangular lattice model of size 4 5 6 5 4. We used two types of amino acids, hydrophobic and polar, to make up the sequences, and achieved 223W212 different sequences excluding the reverse symmetry sequences. The total string number of distinct compact structures was 219,093, excluding reflection symmetry in the self-avoiding path of length 24 triangular lattice model. Based on this model, we applied a fast search algorithm by constructing a cluster tree. The algorithm decreased the computation by computing the objective energy of non-leaf nodes. The parallel experiments proved that the fast tree search algorithm yielded an exponential speed-up in the model of size 4 5 6 5 4. Designability analysis was performed to understand the search result.     

Backbone dynamics, fast folding, and secondary structure formation in helical proteins and peptides

We discuss the construction of a simple, off-lattice model protein with a comparatively detailed representation of the protein backbone, and use it to address some general aspects of the folding kinetics of a small helical protein and two peptide fragments. The model makes use of an associative memory hamiltonian to smoothly interpolate between the limits of a native contact only, or Go, potential and a statistical pair potential derived from a database of known structures. We have observed qualitatively different behavior in these two limits. In the Go limit, we see apparently barrier-less folding. As we increase the roughness of the model energy landscape, we can observe the emergence of the characteristic activated temperature dependence previously seen in lattice studies and analytical theories. We are also able to study the dependence of the folding kinetics on local interactions such as hydrogen bonds, and we discuss the implications of these results for the formation of secondary structure at intermediate stages of the folding reaction.     

Structural analysis of protein folding by the long-chain archaeal chaperone FKBP26

In the cell, protein folding is mediated by folding catalysts and chaperones. The two functions are often linked, especially when the catalytic module forms part of a multidomain protein, as in Methanococcus jannaschii peptidyl-prolyl cis/trans isomerase FKBP26. Here, we show that FKBP26 chaperone activity requires both a 50-residue insertion in the catalytic FKBP domain, also called ‘Insert-in-Flap’ or IF domain, and an 80-residue C-terminal domain. We determined FKBP26 structures from four crystal forms and analyzed chaperone domains in light of their ability to mediate protein-protein interactions. FKBP26 is a crescent-shaped homodimer. We reason that folding proteins are bound inside the large crescent cleft, thus enabling their access to inward-facing peptidyl-prolyl cis/trans isomerase catalytic sites and ipsilateral chaperone domain surfaces. As these chaperone surfaces participate extensively in crystal lattice contacts, we speculate that the observed lattice contacts reflect a proclivity for protein associations and represent substrate interactions by FKBP26 chaperone domains. Finally, we find that FKBP26 is an exceptionally flexible molecule, suggesting a mechanism for nonspecific substrate recognition.     

A replica exchange Monte Carlo algorithm for protein folding in the HP model

Background  

The ab initio protein folding problem consists of predicting protein tertiary structure from a given amino acid sequence by minimizing an energy function; it is one of the most important and challenging problems in biochemistry, molecular biology and biophysics. The ab initio protein folding problem is computationally challenging and has been shown to be -hard even when conformations are restricted to a lattice. In this work, we implement and evaluate the replica exchange Monte Carlo (REMC) method, which has already been applied very successfully to more complex protein models and other optimization problems with complex energy landscapes, in combination with the highly effective pull move neighbourhood in two widely studied Hydrophobic Polar (HP) lattice models.