Optimal HP configurations of proteins by combining local search with elastic net algorithm

The prediction of protein conformation from its amino-acid sequence is one of the most prominent problems in computational biology. But it is NP-hard. Here, we focus on an abstraction widely studied of this problem, the two-dimensional hydrophobic-polar protein folding problem (2D HP PFP). Mathematical optimal model of free energy of protein is established. Native conformations are often sought using stochastic sampling methods, but which are slow. The elastic net (EN) algorithm is one of fast deterministic methods as travelling salesman problem (TSP) strategies. However, it cannot be applied directly to protein folding problem, because of fundamental differences in the two types of problems. In this paper, how the 2D HP protein folding problem can be framed in terms of TSP is shown. Combination of the modified elastic net algorithm and novel local search method is adopted to solve this problem. To our knowledge, this is the first application of EN algorithm to 2D HP model. The results indicate that our approach can find more optimal conformations and is simple to implement, computationally efficient and fast.     

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 ant colony optimisation algorithm for the 2D and 3D hydrophobic polar protein folding problem

Background  

The protein folding problem is a fundamental problems in computational molecular biology and biochemical physics. Various optimisation methods have been applied to formulations of the ab-initio folding problem that are based on reduced models of protein structure, including Monte Carlo methods, Evolutionary Algorithms, Tabu Search and hybrid approaches. In our work, we have introduced an ant colony optimisation (ACO) algorithm to address the non-deterministic polynomial-time hard (NP-hard) combinatorial problem of predicting a protein's conformation from its amino acid sequence under a widely studied, conceptually simple model – the 2-dimensional (2D) and 3-dimensional (3D) hydrophobic-polar (HP) model.     

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.     

蚂蚁群落优化算法在蛋白质折叠二维亲-疏水格点模型中的应用

氨基酸的亲疏水格点模型是研究蛋白质折叠的一种重要的简化模型,其优化问题是一个非确定型的多项式问题。采用蚂蚁群落优化算法对这一问题进行了研究,对测试数据的计算结果表明,在一定规模下,此算法能够有效地获得亲-疏水格点模型的最优解,其效率优于传统的Monte Carlo仿真等方法。     

Hydrophobic Core Formation and Dehydration in Protein Folding Studied by Generalized-Ensemble Simulations

Despite its small size, chicken villin headpiece subdomain HP36 folds into the native structure with a stable hydrophobic core within several microseconds. How such a small protein keeps up its conformational stability and fast folding in solution is an important issue for understanding molecular mechanisms of protein folding. In this study, we performed multicanonical replica-exchange simulations of HP36 in explicit water, starting from a fully extended conformation. We observed at least five events of HP36 folding into nativelike conformations. The smallest backbone root mean-square deviation from the crystal structure was 1.1 Å. In the nativelike conformations, the stably formed hydrophobic core was fully dehydrated. Statistical analyses of the simulation trajectories show the following sequential events in folding of HP36: 1), Helix 3 is formed at the earliest stage; 2), the backbone and the side chains near the loop between Helices 2 and 3 take nativelike conformations; and 3), the side-chain packing at the hydrophobic core and the dehydration of the core side chains take place simultaneously at the later stage of folding. This sequence suggests that the initial folding nucleus is not necessarily the same as the hydrophobic core, consistent with a recent experimental ϕ-value analysis.     

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

蛋白质折叠问题是生物信息学中一个经典的多项式复杂程度的非确定性(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.     

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.     

Analysis on folding of misgurin using two-dimensional HP model

Misgurin is an antimicrobial peptide from the loach, while the hydrophobic-polar (HP) model is a way to study the folding conformations and native states in peptide and protein although several amino acids cannot be classified either hydrophobic or polar. Practically, the HP model requires extremely intensive computations, thus it has yet to be used widely. In this study, we use the two-dimensional HP model to analyze all possible folding conformations and native states of misgurin with conversion of natural amino acids according to the normalized amino acid hydrophobicity index as well as the shortest benchmark HP sequence. The results show that the conversion of misgurin into HP sequence with glycine as hydrophobic amino acid at pH 2 has 1212 folding conformations with the same native state of minimal energy -6; the conversion of glycine as polar amino acid at pH 2 has 13,386 folding conformations with three native states of minimal energy -5; the conversion of glycine as hydrophobic amino acid at pH 7 has 2538 folding conformations with three native states of minimal energy -5; and the conversion of glycine as polar amino acid at pH 7 has 12,852 folding conformations with three native states of minimal energy -4. Those native states can be ranked according to the normalized amino acid hydrophobicity index. The detailed discussions suggest two ways to modify misgurin.     

Protein folding on the hexagonal lattice in the HP model

In this paper, we introduce the 2D hexagonal lattice as a biologically meaningful alternative to the standard square lattice for the study of protein folding in the HP model. We show that the hexagonal lattice alleviates the "sharp turn" problem and models certain aspects of the protein secondary structure more realistically. We present a 1/6-approximation and a clustering heuristic for protein folding on the hexagonal lattice. In addition to these two algorithms, we also implement a Monte Carlo Metropolis algorithm and a branch-and-bound partial enumeration algorithm, and conduct experiments to compare their effectiveness.     

基于HP模型的大麻素受体CB2折叠研究

Cannabinoid receptor Type 2(简称CB2)是大麻素受体的一种亚型,因为其无中枢神经副作用,不会产生成瘾性及耐受性,显示出了非常好的开发前景和潜在的应用价值。其作为免疫调节剂、神经保护剂和抗癌药等将具有巨大市场价值。目前,CB2蛋白的空间结构还未被测定出来,对于CB2的折叠问题研究也开展的较少,为了研究大麻素受体亚型蛋白CB2的折叠问题以及方便更多的研究人员对CB2空间结构和相关药理特性的研究,本文提出了一种基于HP模型的折叠求解方法。通过使用回溯机制和蒙特卡罗方法对此优化问题进行求解,算法可有效的在全局范围内进行寻找最优解,避免了掉入局部最优问题。实验结果表明,本文方法获取的CB2蛋白空间构象具有较低的能量值,折叠情况较好。     

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.     

Protein folding in the landscape perspective: Chevron plots and non-arrhenius kinetics

We use two simple models and the energy landscape perspective to study protein folding kinetics. A major challenge has been to use the landscape perspective to interpret experimental data, which requires ensemble averaging over the microscopic trajectories usually observed in such models. Here, because of the simplicity of the model, this can be achieved. The kinetics of protein folding falls into two classes: multiple-exponential and two-state (single-exponential) kinetics. Experiments show that two-state relaxation times have “chevron plot” dependences on denaturant and non-Arrhenius dependences on temperature. We find that HP and HP+ models can account for these behaviors. The HP model often gives bumpy landscapes with many kinetic traps and multiple-exponental behavior, whereas the HP+ model gives more smooth funnels and two-state behavior. Multiple-exponential kinetics often involves fast collapse into kinetic traps and slower barrier climbing out of the traps. Two-state kinetics often involves entropic barriers where conformational searching limits the folding speed. Transition states and activation barriers need not define a single conformation; they can involve a broad ensemble of the conformations searched on the way to the native state. We find that unfolding is not always a direct reversal of the folding process. Proteins 30:2–33, 1998. © 1998 Wiley-Liss, Inc.     

基于HP模型的蛋白质折叠问题的研究

基于蛋白质二维HP模型提出改进的遗传算法对真实蛋白质进行计算机折叠模拟。结果显示疏水能量函数最小值的蛋白质构象对应含疏水核心的稳定结构,疏水作用在蛋白质折叠中起主要作用。研究表明二维HP模型在蛋白质折叠研究中是可行的和有效的并为进一步揭示蛋白质折叠机理提供重要参考信息。     

Structure-approximating inverse protein folding problem in the 2D HP model.

The inverse protein folding problem is that of designing an amino acid sequence which has a particular native protein fold. This problem arises in drug design where a particular structure is necessary to ensure proper protein-protein interactions. In this paper, we show that in the 2D HP model of Dill it is possible to solve this problem for a broad class of structures. These structures can be used to closely approximate any given structure. One of the most important properties of a good protein (in drug design) is its stability--the aptitude not to fold simultaneously into other structures. We show that for a number of basic structures, our sequences have a unique fold.     

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.     

Protein side-chain packing problem: a maximum edge-weight clique algorithmic approach

"Protein Side-chain Packing" has an ever-increasing application in the field of bio-informatics, dating from the early methods of homology modeling to protein design and to the protein docking. However, this problem is computationally known to be NP-hard. In this regard, we have developed a novel approach to solve this problem using the notion of a maximum edge-weight clique. Our approach is based on efficient reduction of protein side-chain packing problem to a graph and then solving the reduced graph to find the maximum clique by applying an efficient clique finding algorithm developed by our co-authors. Since our approach is based on deterministic algorithms in contrast to the various existing algorithms based on heuristic approaches, our algorithm guarantees of finding an optimal solution. We have tested this approach to predict the side-chain conformations of a set of proteins and have compared the results with other existing methods. We have found that our results are favorably comparable or better than the results produced by the existing methods. As our test set contains a protein of 494 residues, we have obtained considerable improvement in terms of size of the proteins and in terms of the efficiency and the accuracy of prediction.     

Protein structure prediction in a 210-type lattice model: parameter optimization in the genetic algorithm using orthogonal array

We have applied the orthogonal array method to optimize the parameters in the genetic algorithm of the protein folding problem. Our study employed a 210-type lattice model to describe proteins, where the orientation of a residue relative to its neighboring residue is described by two angles. The statistical analysis and graphic representation show that the two angles characterize protein conformations effectively. Our energy function includes a repulsive energy, an energy for the secondary structure preference, and a pairwise contact potential. We used orthogonal array to optimize the parameters of the population, mating factor, mutation factor, and selection factor in the genetic algorithm. By designing an orthogonal set of trials with representative combinations of these parameters, we efficiently determined the optimal set of parameters through a hierarchical search. The optimal parameters were obtained from the protein crambin and applied to the structure prediction of cytochrome B562. The results indicate that the genetic algorithm with the optimal parameters reduces the computing time to reach a converged energy compared to nonoptimal parameters. It also has less chance to be trapped in a local energy minimum, and predicts a protein structure which is closer to the experimental one. Our method may also be applicable to many other optimization problems in computational biology.