Extended HP model for protein structure prediction

Improving coarse-grained models of protein folding through weighting of polar-polar/hydrophobic-hydrophobic interactions into crowded spaces

Herein were tested 7 hydrophobic-polar sequences in two types of 2D-square space lattices, homogeneous and correlated, the latter simulating molecular crowding included as a geometric boundary restriction. Optimization of 2D structures was carried out using a variant of Dill's model, inspired by convex function, taking into account both hydrophobic (Dill's model) and polar interactions, including more structural information to reach better folding solutions. While using correlated networks, degrees of freedom in the folding of sequences were limited; as a result in all cases, more successful structural trials were found in comparison to a homogeneous lattice. The majority of employed sequences were designed by our workgroup, two of them were folded with other approaches, and another is a modified version of a previous sequence, initial forms of the other two have been employed but without taking into account polar-polar contributions. Three of them are newly proposed, intended to test the conjoint hydrophobic-hydrophobic and polar-polar contributions in crowded spaces. One sequence turned out to be the most difficult of the seven folded, this perhaps due to intrinsic (i) degrees of freedom and (ii) motifs of the expected 2D HP structure. Meanwhile two-sequence, although optimal folding was not achieved for neither of the two approaches, folding with correlated network approach not only produced better results than homogeneous space, but for them the best values found with crowding were very close to the expected optimal fitness. In general, five sequences were better folded with medium lattice units for correlated media; instead, another two sequences were better folded with a bit larger degree of lattice unit, revealing that depending on the degrees of freedom and particular folding, motifs in each sequence would require tuned crowding to achieve better folding. Therefore, the main goal herein was to obtain a modified 2D HP lattice model to mimic folding of proteins or secondary structures, like β-sheets, taking into account both hydrophobic-hydrophobic and polar-polar interactions, and fold them in a crowded environment. This simple but enough construction would be conducted to determine the needed information to fold sequences in a sort of a minimal but complete heuristic model. Finally, we claim that all folded sequences into crowded spaces achieve better results than homogeneous ones.

Thermodynamics of hydrophobic-polar model proteins on the face-centered cubic lattice

The HP model, a coarse-grained protein representation with only hydrophobic (H) and polar (P) amino acids, has already been extensively studied on the simple cubic (SC) lattice. However, this geometry severely restricts possible bond angles, and a simple improvement is to instead use the face-centered cubic (fcc) lattice. In this paper, the density of states and ground state energies are calculated for several benchmark HP sequences on the fcc lattice using the replica-exchange Wang-Landau algorithm and a powerful set of Monte Carlo trial moves. Results from the fcc lattice proteins are directly compared with those obtained from a previous lattice protein folding study with a similar methodology on the SC lattice. A thermodynamic analysis shows comparable folding behavior between the two lattice geometries, but with a greater rate of hydrophobic-core formation persisting into lower temperatures on the fcc lattice.

Contributions of topological polar-polar contacts to achieve better folding stability of 2D/3D HP lattice proteins: An in silico approach

<abstract> <p>Many of the simplistic hydrophobic-polar lattice models, such as Dill's model (called <bold>Model 1</bold> herein), are aimed to fold structures through hydrophobic-hydrophobic interactions mimicking the well-known hydrophobic collapse present in protein structures. In this work, we studied 11 designed hydrophobic-polar sequences, S₁-S₈ folded in 2D-square lattice, and S₉-S₁₁ folded in 3D-cubic lattice. And to better fold these structures we have developed <bold>Model 2</bold> as an approximation to convex function aimed to weight hydrophobic-hydrophobic but also polar-polar contacts as an augmented version of <bold>Model 1</bold>. In this partitioned approach hydrophobic-hydrophobic ponderation was tuned as <italic>α</italic>-1 and polar-polar ponderation as <italic>α</italic>. This model is centered in preserving required hydrophobic substructure, and at the same time including polar-polar interactions, otherwise absent, to reach a better folding score now also acquiring the polar-polar substructure. In all tested cases the folding trials were better achieved with <bold>Model 2</bold>, using <italic>α</italic> values of 0.05, 0.1, 0.2 and 0.3 depending of sequence size, even finding optimal scores not reached with <bold>Model 1</bold>. An important result is that the better folding score, required the lower <italic>α</italic> weighting. And when <italic>α</italic> values above 0.3 are employed, no matter the nature of the hydrophobic-polar sequence, banning of hydrophobic-hydrophobic contacts started, thus yielding misfolding of sequences. Therefore, the value of <italic>α</italic> to correctly fold structures is the result of a careful weighting among hydrophobic-hydrophobic and polar-polar contacts.</p> </abstract>

A benchmark of optimally folded protein structures using integer programming and the 3D-HP-SC model

The Protein Structure Prediction (PSP) problem comprises, among other issues, forecasting the three-dimensional native structure of proteins using only their primary structure information. Most computational studies in this area use synthetic data instead of real biological data. However, the closer to the real-world, the more the impact of results and their applicability. This work presents 17 real protein sequences extracted from the Protein Data Bank for a benchmark to the PSP problem using the tri-dimensional Hydrophobic-Polar with Side-Chains model (3D-HP-SC). The native structure of these proteins was found by maximizing the number of hydrophobic contacts between the side-chains of amino acids. The problem was treated as an optimization problem and solved by means of an Integer Programming approach. Although the method optimally solves the problem, the processing time has an exponential trend. Therefore, due to computational limitations, the method is a proof-of-concept and it is not applicable to large sequences. For unknown sequences, an upper bound of the number of hydrophobic contacts (using this model) can be found, due to a linear relationship with the number of hydrophobic residues. The comparison between the predicted and the biological structures showed that the highest similarity between them was found with distance thresholds around 5.2-8.2 Å. Both the dataset and the programs developed will be freely available to foster further research in the area.

In silico minimalist approach to study 2D HP protein folding into an inhomogeneous space mimicking osmolyte effect: First trial in the search of foldameric backbones

We have employed our bioinformatics workbench, named Evolution, a Multi-Agent System based architecture with lattice-bead-models, evolutionary-algorithms, and correlated-networks as inhomogeneous spaces, with different correlation lengths, mimicking osmolyte effect (molecular crowding), to in silico survey protein folding. Resolution is with hydrophobic-polar (H-P) sequences in inhomogeneous 2D square lattices, since general biophysicochemical trends consider i) that the backbone is one of the major components responsible for protein folding and ii) osmolyte effect plays an important role to better folding kinetics and reach deeper optima. We have designed foldamers, as square n × n (n = 3, 4, 5, 6) arrays of hydrophobic cores stabilized by H⋯H contacts, attached through short PP (P₂) or long PPPP (P₄) loops, giving rise to 8 sequences (S₁ to S₈) with known optimal scores. Designed sequences were folded into different inhomogeneous spaces and indeed crowded media induced deeper optima, being crowding necessary to best fold, but the space should be enough constrained to induce folding without banning chain movement. The constrained space plays an important role to reach the optimal structure, depending on designed foldamer sequence size, for an optimal correlation length, implying that media affects the folding pathways as happens in real systems. Designed structures were found, moreover, they undergo to degenerated states, both folding states could survey considering i) backbone information and ii) osmolyte effect. In nature, the proteins fold in different structures aiming to reach a global minimum, but a local minimum could be enough to the protein to be functional or dysfunctional.

A Novel Framework for Ab Initio Coarse Protein Structure Prediction

Hydrophobic-Polar model is a simplified representation of Protein Structure Prediction (PSP) problem. However, even with the HP model, the PSP problem remains NP-complete. This work proposes a systematic and problem specific design for operators of the evolutionary program which hybrids with local search hill climbing, to efficiently explore the search space of PSP and thereby obtain an optimum conformation. The proposed algorithm achieves this by incorporating the following novel features: (i) new initialization method which generates only valid individuals with (rather than random) better fitness values; (ii) use of probability-based selection operators that limit the local convergence; (iii) use of secondary structure based mutation operator that makes the structure more closely to the laboratory determined structure; and (iv) incorporating all the above-mentioned features developed a complete two-tier framework. The developed framework builds the protein conformation on the square and triangular lattice. The test has been performed using benchmark sequences, and a comparative evaluation is done with various state-of-the-art algorithms. Moreover, in addition to hypothetical test sequences, we have tested protein sequences deposited in protein database repository. It has been observed that the proposed framework has shown superior performance regarding accuracy (fitness value) and speed (number of generations needed to attain the final conformation). The concepts used to enhance the performance are generic and can be used with any other population-based search algorithm such as genetic algorithm, ant colony optimization, and immune algorithm.

A Computational Approach to Studying Protein Folding Problems Considering the Crucial Role of the Intracellular Environment

Intracellular protein folding (PF) is performed in a highly inhomogeneous, crowded, and correlated environment. Due to this inherent complexity, the study and understanding of PF phenomena is a fundamental issue in the field of computational systems biology. In particular, it is important to use a modeled medium that accurately reflects PF in natural systems. In the current study, we present a simulation wherein PF is carried out within an inhomogeneous modeled medium. Simulation resources included a two-dimensional hydrophobic-polar (HP) model, evolutionary algorithms, and the dual site-bond model. The dual site-bond model was used to develop an environment where HP beads could be folded. Our modeled medium included correlation lengths and fractal-like behavior, which were selected according to HP sequence lengths to induce folding in a crowded environment. Analysis of three benchmark HP sequences showed that the modeled inhomogeneous space played an important role in deeper energy folding and obtained better performance and convergence compared with homogeneous environments. Our computational approach also demonstrated that our correlated network provided a better space for PF. Thus, our approach represents a major advancement in PF simulations, not only for folding but also for understanding functional chemical structure and physicochemical properties of proteins in crowded molecular systems, which normally occur in nature.

Simulating the folding of HP-sequences with a minimalist model in an inhomogeneous medium

The phenomenon of protein folding is a fundamental issue in the field of the computational molecular biology. The protein folding inside the cells is performed in a highly inhomogeneous, tortuous, and correlated environment. Therefore, it is important to include in the theoretical studies the medium where the protein folding is developed. In this work we present the combination of three models to mimic the protein folding inside of an inhomogeneous medium. The models used here are Hydrophobic-Polar (HP) in 2D square arrangement, Evolutionary Algorithms (EA), and the Dual Site Bond Model (DSBM). The DSBM model is used to simulate the environment where the HP beads are folded; in this case the medium is correlated and is fractal-like. The analysis of five benchmark HP sequences shows that the inhomogeneous space provided with a given correlation length and fractal dimension plays an important role for correct folding of these sequences, which does not occur in a homogeneous space.

toyLIFE: a computational framework to study the multi-level organisation of the genotype-phenotype map

The genotype-phenotype map is an essential object to understand organismal complexity and adaptability. However, its experimental characterisation is a daunting task. Thus, simple models have been proposed and investigated. They have revealed that genotypes differ in their robustness to mutations; phenotypes are represented by a broadly varying number of genotypes, and simple point mutations suffice to navigate the space of genotypes while maintaining a phenotype. Nonetheless, most current models focus only on one level of the map (folded molecules, gene regulatory networks, or networks of metabolic reactions), so that many relevant questions cannot be addressed. Here we introduce toyLIFE, a multi-level model for the genotype-phenotype map based on simple genomes and interaction rules from which a complex behaviour at upper levels emerges -remarkably plastic gene regulatory networks and metabolism. toyLIFE is a tool that permits the investigation of how different levels are coupled, in particular how and where mutations affect phenotype or how the presence of certain metabolites determines the dynamics of toyLIFE gene regulatory networks. The model can easily incorporate evolution through more complex mutations, recombination, or gene duplication and deletion, thus opening an avenue to explore extended genotype-phenotype maps.

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.

Exact methods for lattice protein models

Lattice protein models are well-studied abstractions of globular proteins. By discretizing the structure space and simplifying the energy model over regular proteins, they enable detailed studies of protein structure formation and evolution. However, even in the simplest lattice protein models, the prediction of optimal structures is computationally difficult. Therefore, often, heuristic approaches are applied to find such conformations. Commonly, heuristic methods find only locally optimal solutions. Nevertheless, there exist methods that guarantee to predict globally optimal structures. Currently, only one such exact approach is publicly available, namely the constraint-based protein structure prediction method and variants. Here, we review exact approaches and derived methods. We discuss fundamental concepts like hydrophobic core construction and their use in optimal structure prediction, as well as possible applications like combinations of different energy models.

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.

Twin removal in genetic algorithms for protein structure prediction using low-resolution model

This paper presents the impact of twins and the measures for their removal from the population of genetic algorithm (GA) when applied to effective conformational searching. It is conclusively shown that a twin removal strategy for a GA provides considerably enhanced performance when investigating solutions to complex ab initio protein structure prediction (PSP) problems in low-resolution model. Without twin removal, GA crossover and mutation operations can become ineffectual as generations lose their ability to produce significant differences, which can lead to the solution stalling. The paper relaxes the definition of chromosomal twins in the removal strategy to not only encompass identical, but also highly correlated chromosomes within the GA population, with empirical results consistently exhibiting significant improvements solving PSP problems.