Annealing contour Monte Carlo algorithm for structure optimization in an off-lattice protein model

Protein structure optimization using improved simulated annealing algorithm on a three-dimensional AB off-lattice model

This paper proposed an improved simulated annealing (ISA) algorithm for protein structure optimization based on a three-dimensional AB off-lattice model. In the algorithm, we provided a general formula used for producing initial solution, and designed a multivariable disturbance term, relating to the parameters of simulated annealing and a tuned constant, to generate neighborhood solution. To avoid missing optimal solution, storage operation was performed in searching process. We applied the algorithm to test artificial protein sequences from literature and constructed a benchmark dataset consisting of 10 real protein sequences from the Protein Data Bank (PDB). Otherwise, we generated C_α space-filling model to represent protein folding conformation. The results indicate our algorithm outperforms the five methods before in searching lower energies of artificial protein sequences. In the testing on real proteins, our method can achieve the energy conformations with C_α-RMSD less than 3.0 Å from the PDB structures. Moreover, C_α space-filling model may simulate dynamic change of protein folding conformation at atomic level.

Size-guided multi-seed heuristic method for geometry optimization of clusters: Application to benzene clusters

Since searching for the global minimum on the potential energy surface of a cluster is very difficult, many geometry optimization methods have been proposed, in which initial geometries are randomly generated and subsequently improved with different algorithms. In this study, a size-guided multi-seed heuristic method is developed and applied to benzene clusters. It produces initial configurations of the cluster with n molecules from the lowest-energy configurations of the cluster with n - 1 molecules (seeds). The initial geometries are further optimized with the geometrical perturbations previously used for molecular clusters. These steps are repeated until the size n satisfies a predefined one. The method locates putative global minima of benzene clusters with up to 65 molecules. The performance of the method is discussed using the computational cost, rates to locate the global minima, and energies of initial geometries. © 2018 Wiley Periodicals, Inc.

Two Perturbations for Geometry Optimization of Off-lattice Bead Protein Models

Referring to the optimization algorithm previously developed for atomic clusters, the present author develops an efficient method for geometry optimization of a coarse-grained protein model expressed with two kinds of beads (hydrophilic and hydrophobic ones). In the method, two types of geometrical perturbations, center-directed bead move and one bead rotation, are used to explore new configurations and local optimizations are performed after the perturbations. The center-directed bead move is used for hydrophobic beads and the one bead rotation is performed for both hydrophobic and hydrophilic beads. The optimization method was applied to protein models consisting of 13, 20, 21, and 34 beads. The present method produced the global minima of the 13-, 21-, and 34-bead models reported in the literature and updated the lowest energies of the protein models with 20 beads. These results indicate that the present method is efficient for searching for optimal structures of proteins.

Protein structure prediction with local adjust tabu search algorithm

Background

Protein folding structure prediction is one of the most challenging problems in the bioinformatics domain. Because of the complexity of the realistic protein structure, the simplified structure model and the computational method should be adopted in the research. The AB off-lattice model is one of the simplification models, which only considers two classes of amino acids, hydrophobic (A) residues and hydrophilic (B) residues.

Results

The main work of this paper is to discuss how to optimize the lowest energy configurations in 2D off-lattice model and 3D off-lattice model by using Fibonacci sequences and real protein sequences. In order to avoid falling into local minimum and faster convergence to the global minimum, we introduce a novel method (SATS) to the protein structure problem, which combines simulated annealing algorithm and tabu search algorithm. Various strategies, such as the new encoding strategy, the adaptive neighborhood generation strategy and the local adjustment strategy, are adopted successfully for high-speed searching the optimal conformation corresponds to the lowest energy of the protein sequences. Experimental results show that some of the results obtained by the improved SATS are better than those reported in previous literatures, and we can sure that the lowest energy folding state for short Fibonacci sequences have been found.

Conclusions

Although the off-lattice models is not very realistic, they can reflect some important characteristics of the realistic protein. It can be found that 3D off-lattice model is more like native folding structure of the realistic protein than 2D off-lattice model. In addition, compared with some previous researches, the proposed hybrid algorithm can more effectively and more quickly search the spatial folding structure of a protein chain.

A balance-evolution artificial bee colony algorithm for protein structure optimization based on a three-dimensional AB off-lattice model

Protein structure prediction is a fundamental issue in the field of computational molecular biology. In this paper, the AB off-lattice model is adopted to transform the original protein structure prediction scheme into a numerical optimization problem. We present a balance-evolution artificial bee colony (BE-ABC) algorithm to address the problem, with the aim of finding the structure for a given protein sequence with the minimal free-energy value. This is achieved through the use of convergence information during the optimization process to adaptively manipulate the search intensity. Besides that, an overall degradation procedure is introduced as part of the BE-ABC algorithm to prevent premature convergence. Comprehensive simulation experiments based on the well-known artificial Fibonacci sequence set and several real sequences from the database of Protein Data Bank have been carried out to compare the performance of BE-ABC against other algorithms. Our numerical results show that the BE-ABC algorithm is able to outperform many state-of-the-art approaches and can be effectively employed for protein structure optimization.

STUDIES OF FINDING LOW ENERGY CONFIGURATIONS IN OFF-LATTICE PROTEIN MODELS

We studied two three-dimensional off-lattice protein models with two species of monomers, hydrophobic and hydrophilic. Low energy configurations in both models were optimized using the energy landscape paving (ELP) method and subsequent gradient descent. The numerical results show that the proposed methods are very promising for finding the ground states of proteins. For all sequences with lengths 13 ≤ n ≤ 55, the algorithm finds states with lower energy than previously proposed putative ground states.

Effective 3D protein structure prediction with local adjustment genetic-annealing algorithm

The protein folding problem consists of predicting protein tertiary structure from a given amino acid sequence by minimizing the energy function. The protein folding structure prediction is computationally challenging and has been shown to be NP-hard problem when the 3D off-lattice AB model is employed. In this paper, the local adjustment genetic-annealing (LAGA) algorithm was used to search the ground state of 3D offlattice AB model for protein folding structure. The algorithm included an improved crossover strategy and an improved mutation strategy, where a local adjustment strategy was also used to enhance the searching ability. The experiments were carried out with the Fibonacci sequences. The experimental results demonstrate that the LAGA algorithm appears to have better performance and accuracy compared to the previous methods.

Structure optimization of the two-dimensional off-lattice hydrophobic-hydrophilic model

A two-dimensional off-lattice protein model with two species of monomers, hydrophobic and hydrophilic, was studied. Low-energy configurations in the model were optimized using the improved energy landscape paving (ELP+) method. In ELP+, the energy landscape paving (ELP) was first applied to search for the low-energy states. After the ELP led to the basins of the local energy minima, the additional degree-of-freedom of bond length was introduced, and the gradient descent method was then used to search for lower energy states near the local minima. Numerical results show that the proposed methods are quite effective for finding the ground states of proteins. A comparison between ELP+ and other methods is made.

Re-examination of structure optimization of off-lattice protein AB models by conformational space annealing

The global structural optimization is carried out for off-lattice protein AB models in two and three dimensions by conformational space annealing. The models consist of hydrophobic and hydrophilic monomers in Fibonacci sequences. To accelerate the convergence, we have introduced a shift operator in the internal coordinate system, and effectively reduced the search space by forming a quotient space. With this, we significantly improve our previous results on AB models, and provide new low energy conformations. This work provides insights on exploring complicated energy landscapes by exploiting the advantages and limitations of CSA.

Simulation via direct computation of partition functions

In this paper, we demonstrate the efficiency of simulations via direct computation of the partition function under various macroscopic conditions, such as different temperatures or volumes. The method can compute partition functions by flattening histograms, through, for example, the Wang-Landau recursive scheme, outside the energy space. This method offers a more general and flexible framework for handling various types of ensembles, especially ones in which computation of the density of states is not convenient. It can be easily scaled to large systems, and it is flexible in incorporating Monte Carlo cluster algorithms or molecular dynamics. High efficiency is shown in simulating large Ising models, in finding ground states of simple protein models, and in studying the liquid-vapor phase transition of a simple fluid. The method is very simple to implement and we expect it to be efficient in studying complex systems with rugged energy landscapes, e.g., biological macromolecules.

Structure optimization and folding mechanisms of off-lattice protein models using statistical temperature molecular dynamics simulation: Statistical temperature annealing

The recently proposed statistical temperature molecular dynamics (STMD) algorithm [Kim, Phys. Rev. Lett. 97, 050601 (2006)] is used as the core of an optimization algorithm, statistical temperature annealing (STA), for finding low-lying energy minima of complex potential energy landscapes. Since STMD realizes a random walk in energy, the idea is simply to initiate repeated minimizations from configurations in the low-energy segments of STMD trajectories. STA is tested in structural optimization of various off-lattice AB and extended AB protein models in two and three dimensions with different chain lengths. New putative ground states were found for the two- and three-dimensional AB 55-mer, and for the three-dimensional extended AB 21-mer and 55-mer. The distinct folding features of the models are analyzed in terms of the statistical temperature and other representations of the structure of the potential energy landscape. It is shown that the characteristic behavior of the statistical temperature undergoes a qualitative change with the inclusion of a torsional potential in the extended AB model, as the more rigid backbone makes the potential energy landscape more funnel-like.

Identification of characteristic protein folding channels in a coarse-grained hydrophobic-polar peptide model

Folding channels and free-energy landscapes of hydrophobic-polar heteropolymers are discussed on the basis of a minimalistic off-lattice coarse-grained model. We investigate how rearrangements of hydrophobic and polar monomers in a heteropolymer sequence lead to completely different folding behaviors. Studying three exemplified sequences with the same content of hydrophobic and polar residues, we can reproduce within this simple model two-state folding, folding through intermediates, as well as metastability.

A knowledge-based move set for protein folding

The free energy landscape of protein folding is rugged, occasionally characterized by compact, intermediate states of low free energy. In computational folding, this landscape leads to trapped, compact states with incorrect secondary structure. We devised a residue-specific, protein backbone move set for efficient sampling of protein-like conformations in computational folding simulations. The move set is based on the selection of a small set of backbone dihedral angles, derived from clustering dihedral angles sampled from experimental structures. We show in both simulated annealing and replica exchange Monte Carlo (REMC) simulations that the knowledge-based move set, when compared with a conventional move set, shows statistically significant improved ability at overcoming kinetic barriers, reaching deeper energy minima, and achieving correspondingly lower RMSDs to native structures. The new move set is also more efficient, being able to reach low energy states considerably faster. Use of this move set in determining the energy minimum state and for calculating thermodynamic quantities is discussed.

Two-state folding, folding through intermediates, and metastability in a minimalistic hydrophobic-polar model for proteins

Within the frame of an effective, coarse-grained hydrophobic-polar protein model, we employ multicanonical Monte Carlo simulations to investigate free-energy landscapes and folding channels of exemplified heteropolymer sequences, which are permutations of each other. Despite the simplicity of the model, the knowledge of the free-energy landscape in dependence of a suitable system order parameter enables us to reveal complex folding characteristics known from real bioproteins and synthetic peptides, such as two-state folding, folding through weakly stable intermediates, and glassy metastability.

Energy optimization for off-lattice protein folding

Two three-dimensional AB off-lattice protein models consisting of hydrophobic and hydrophilic monomers are studied in this paper. By incorporating an extra energy contribution into the original energy function, the protein folding is converted from a constraint optimization problem into an unconstrained one which can be solved by the well-known gradient method. From the initial configurations randomly generated by the heuristic strategy proposed in this paper, our algorithm can find better results than those by nPERM for the four Fibonacci sequences. Based on the initial configurations obtained by energy landscape paving (ELP) routine, some of our results for the lowest energies are better than the best values reported in the literature.

Statistical-temperature Monte Carlo and molecular dynamics algorithms

A simulation method is presented that achieves a flat energy distribution by updating the statistical temperature instead of the density of states in Wang-Landau sampling. A novel molecular dynamics algorithm (STMD) applicable to complex systems and a Monte Carlo algorithm are developed from this point of view. Accelerated convergence for large energy bins, essential for large systems, is demonstrated in tests on the Ising model, the Lennard-Jones fluid, and bead models of proteins. STMD shows a superior ability to find local minima in proteins and new global minima are found for the 55 bead AB model in two and three dimensions. Calculations of the occupation probabilities of individual protein inherent structures provide new insights into folding and misfolding.

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.

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

In this paper, we study an off-lattice protein AB model with two species of monomers, hydrophobic and hydrophilic, and present a heuristic quasi-physical algorithm. First, by elaborately simulating the movement of the smooth solids in the physical world, we find low-energy conformations for a given monomer chain. A subsequent off-trap strategy is then proposed to trigger a jump for a stuck situation in order to get out of the local minima. The algorithm has been tested in the three-dimensional AB model for all sequences with lengths of 13-55 monomers. In several cases, we renew the putative ground state energy values. The numerical results show that the proposed methods are very promising for finding the ground states of proteins.

Structure optimization by conformational space annealing in an off-lattice protein model

The optimization results by conformational space annealing are presented for an off-lattice protein model consisting of hydrophobic and hydrophilic residues in Fibonacci sequences. The ground-state energies found are lower than those reported in the literature. In addition, the ground-state conformations in three dimensions exhibit the important aspect of forming a single hydrophobic core in real proteins. The energy landscape for the population of local minima is also investigated.

Evidence Evaluation for Bayesian Neural Networks Using Contour Monte Carlo

Bayesian neural networks play an increasingly important role in modeling and predicting nonlinear phenomena in scientific computing. In this article, we propose to use the contour Monte Carlo algorithm to evaluate evidence for Bayesian neural networks. In the new method, the evidence is dynamically learned for each of the models. Our numerical results show that the new method works well for both the regression and classification multilayer perceptrons. It often leads to an improved estimate, in terms of overall accuracy, for the evidence of multiple MLPs in comparison with the reversible-jump Markov chain Monte Carlo method and the gaussian approximation method. For the simulated data, it can identify the true models, and for the real data, it can produce results consistent with those published in the literature.

Multicanonical study of coarse-grained off-lattice models for folding heteropolymers

We have performed multicanonical simulations of hydrophobic-hydrophilic heteropolymers with two simple effective, coarse-grained off-lattice models to study the influence of specific interactions in the models on conformational transitions of selected sequences with 20 monomers. Another aspect of the investigation was the comparison with the purely hydrophobic homopolymer and the study of general conformational properties induced by the "disorder" in the sequence of a heteropolymer. Furthermore, we applied an optimization algorithm to sequences with up to 55 monomers and compared the global-energy minimum found with lowest-energy states identified within the multicanonical simulation. This was used to find out how reliable the multicanonical method samples the free-energy landscape, in particular for low temperatures.