Investigation of the three-dimensional lattice HP protein folding model using a genetic algorithm

Finding the needle in the haystack: towards solving the protein-folding problem computationally

Prediction of protein tertiary structures from amino acid sequence and understanding the mechanisms of how proteins fold, collectively known as "the protein folding problem," has been a grand challenge in molecular biology for over half a century. Theories have been developed that provide us with an unprecedented understanding of protein folding mechanisms. However, computational simulation of protein folding is still difficult, and prediction of protein tertiary structure from amino acid sequence is an unsolved problem. Progress toward a satisfying solution has been slow due to challenges in sampling the vast conformational space and deriving sufficiently accurate energy functions. Nevertheless, several techniques and algorithms have been adopted to overcome these challenges, and the last two decades have seen exciting advances in enhanced sampling algorithms, computational power and tertiary structure prediction methodologies. This review aims at summarizing these computational techniques, specifically conformational sampling algorithms and energy approximations that have been frequently used to study protein-folding mechanisms or to de novo predict protein tertiary structures. We hope that this review can serve as an overview on how the protein-folding problem can be studied computationally and, in cases where experimental approaches are prohibitive, help the researcher choose the most relevant computational approach for the problem at hand. We conclude with a summary of current challenges faced and an outlook on potential future directions.

Protein Folding Prediction in a Cubic Lattice in Hydrophobic-Polar Model

The tertiary structure of the proteins determines their functions. Therefore, the predicting of protein's tertiary structure, based on the primary amino acid sequence from long time, is the most important and challenging subject in biochemistry, molecular biology, and biophysics. One of the most popular protein structure prediction methods, called Hydrophobic-Polar (HP) model, is based on the observation that in polar environment hydrophobic amino acids are in the core of the molecule-in contact between them and more polar amino acids are in contact with the polar environment. In this study, we present a new mixed integer programming formulation, exact algorithm, and two heuristic algorithms to solve the protein folding problem stated as a combinatorial optimization problem in a simple cubic lattice. The results from computational runs on a set of benchmarks are favorably compared to known algorithms for solving the 3D lattice HP model as genetic algorithms, ant colony optimization algorithm, and Monte Carlo algorithm.

The Noncompacted Folding of Proteins by Modified Elastic Net Algorithm

In this article, a protein sequence of length n is embedded in a two-dimensional lattice with m (>n) points. Thus the obtained minimal energy configurations are expected to have flexible shapes in contrast to the compact rectangular conformations. To fulfill this extension, the elastic net algorithm is modified to deal with the difficulty brought by the unsymmetrical relationship between amino acids and lattice points. New set partition strategy in the embedding phase is introduced, and two local search methods are applied to overcome the multimapping phenomena. Several HP benchmark examples with up to 48 amino acids are tested to verify the effectiveness of the proposed approach.

Emergent protein folding modeled with evolved neural cellular automata using the 3D HP model

We used cellular automata (CA) for the modeling of the temporal folding of proteins. Unlike the focus of the vast research already done on the direct prediction of the final folded conformations, we will model the temporal and dynamic folding process. To reduce the complexity of the interactions and the nature of the amino acid elements, lattice models like HP were used, a model that categorizes the amino acids regarding their hydrophobicity. Taking into account the restrictions of the lattice model, the CA model defines how the amino acids interact through time to obtain a folded conformation. We extended the classical CA models using artificial neural networks for their implementation (neural CA), and we used evolutionary computing to automatically obtain the models by means of Differential Evolution. As the iterative folding also provides the final folded conformation, we can compare the results with those from direct prediction methods of the final protein conformation. Finally, as the neural CA that provides the iterative folding process can be evolved using several protein sequences and used as operators in the folding of another protein with different length, this represents an advantage over the NP-hard complexity of the original problem of the direct prediction.

Heuristic energy landscape paving for protein folding problem in the three-dimensional HP lattice model

The protein folding problem, i.e., the prediction of the tertiary structures of protein molecules from their amino acid sequences is one of the most important problems in computational biology and biochemistry. However, the extremely difficult optimization problem arising from energy function is a key challenge in protein folding simulation. The energy landscape paving (ELP) method has already been applied very successfully to off-lattice protein models and other optimization problems with complex energy landscape in continuous space. By improving the ELP method, and subsequently incorporating the neighborhood strategy with the pull-move set into the improved ELP method, a heuristic ELP algorithm is proposed to find low-energy conformations of 3D HP lattice model proteins in the discrete space. The algorithm is tested on three sets of 3D HP benchmark instances consisting 31 sequences. For eleven sequences with 27 monomers, the proposed method explores the conformation surfaces more efficiently than other methods, and finds new lower energies in several cases. For ten 48-monomer sequences, we find the lowest energies so far. With the achieved results, the algorithm converges rapidly and efficiently. For all ten 64-monomer sequences, the algorithm finds lower energies within comparable computation times than previous methods. Numeric results show that the heuristic ELP method is a competitive tool for protein folding simulation in 3D lattice model. To the best of our knowledge, this is the first application of ELP to the 3D discrete space.

Protein-folding simulations of the hydrophobic-hydrophilic model by combining pull moves with energy landscape paving

The energy landscape paving (ELP) method is a class of heuristic global optimization algorithms based on Monte Carlo sampling. By incorporating the generation of an initial conformation based on a greedy strategy, the conformation update mechanism based on pull moves, and some heuristic off-trap strategies into an improved ELP method, we propose an alternative version of the ELP method, called the ELP-pull move method. We test the ELP-pull move method on both two-dimensional (2D) and 3D hydrophobic-hydrophilic protein-folding models. For ten 2D benchmark sequences of length ranging from 20 to 100, the proposed algorithm finds the lowest energies so far. Within the achieved results, the algorithm converges more rapidly and efficiently than previous methods. For all ten 3D sequences with a length of 64, the ELP-pull move method finds lower energies within comparable computational times. The numerical results demonstrate that our algorithm is a powerful method to study the lattice protein-folding model.

Protein folding simulations of 2D HP model by the genetic algorithm based on optimal secondary structures

In this paper, based on the evolutionary Monte Carlo (EMC) algorithm, we have made four points of ameliorations and propose a so-called genetic algorithm based on optimal secondary structure (GAOSS) method to predict efficiently the protein folding conformations in the two-dimensional hydrophobic-hydrophilic (2D HP) model. Nine benchmarks are tested to verify the effectiveness of the proposed approach and the results show that for the listed benchmarks GAOSS can find the best solutions so far. It means that reasonable, effective and compact secondary structures (SSs) can avoid blind searches and can reduce time consuming significantly. On the other hand, as examples, we discuss the diversity of protein GSC for the 24-mer and 85-mer sequences. Several GSCs have been found by GAOSS and some of the conformations are quite different from each other. It would be useful for the designing of protein molecules. GAOSS would be an efficient tool for the protein structure predictions (PSP).

Protein structure prediction with the 3D-HP side-chain model using a master–slave parallel genetic algorithm

This work presents a master-slave parallel genetic algorithm for the protein folding problem, using the 3D-HP side-chain model (3D-HP-SC). This model is sparsely studied in the literature, although more expressive than other lattice models. The fitness function proposed includes information not only about the free-energy of the conformation, but also compactness of the side-chains. Since there is no benchmark available to date for this model, a set of 15 sequences was used, based on a simpler model. Results show that the parallel GA achieved a good level of efficiency and obtained biologically coherent results, suggesting the adequacy of the methodology. Future work will include new biologically-inspired genetic operators and more experiments to create new benchmarks.

The simulation of the three-dimensional lattice hydrophobic-polar protein folding

One of the most prominent problems in computational biology is to predict the natural conformation of a protein from its amino acid sequence. This paper focuses on the three-dimensional hydrophobic-polar (HP) lattice model of this problem. The modified elastic net (EN) algorithm is applied to solve this nonlinear programming hard problem. The lattice partition strategy and two local search methods (LS(1) and LS(2)) are proposed to improve the performance of the modified EN algorithm. The computation and analysis of 12 HP standard benchmark instances are also involved in this paper. The results indicate that the hybrid of modified EN algorithm, lattice partition strategy, and local search methods has a greater tendency to form a globular state than genetic algorithm does. The results of noncompact model are more natural in comparison with that of compact model.

Exploration of two-dimensional hydrophobic-polar lattice model by combining local search with elastic net algorithm

Determining the functional conformation of a protein from its amino acid sequence remains a central problem in computational biology. In this paper, we establish the mathematical optimal model of protein folding problem (PFP) on two-dimensional space based on the minimal energy principle. A novel hybrid of elastic net algorithm and local search method (ENLS) is applied successfully to simulations of protein folding on two-dimensional hydrophobic-polar (HP) lattice model. Eight HP benchmark instances with up to 64 amino acids are tested to verify the effectiveness of proposed approach and model. In several cases, the ENLS method finds new lower energy states. The numerical results show that it is drastically superior to other methods in finding the ground state of a protein.