A reliable prediction of 3D protein structures from sequence data remains a big challenge due to both theoretical and computational difficulties. We have previously shown that our kinetostatic compliance method (KCM) implemented into the Protofold package can overcome some of the key difficulties faced by other de novo structure prediction methods, such as the very small time steps required by the molecular dynamics (MD) approaches or the very large number of samples needed by the Monte Carlo (MC) sampling techniques. In this article, we improve the free energy formulation used in Protofold by including the typically underrated entropic effects, imparted due to differences in hydrophobicity of the chemical groups, which dominate the folding of most water-soluble proteins. In addition to the model enhancement, we revisit the numerical implementation by redesigning the algorithms and introducing efficient data structures that reduce the expected complexity from quadratic to linear. Moreover, we develop and optimize parallel implementations of the algorithms on both central and graphics processing units (CPU GPU) achieving speed-ups up to two orders of magnitude on the GPU. Our simulations are consistent with the general behavior observed in the folding process in aqueous solvent, confirming the effectiveness of model improvements. We report on the folding process at multiple levels; namely, the formation of secondary structural elements and tertiary interactions between secondary elements or across larger domains. We also observe significant enhancements in running times that make the folding simulation tractable for large molecules.
Sampling methods generate numerous samples in the conformation space, followed by an evaluation of their free energies. Different search algorithms are used to find the unchallenged global minimum of the free energy, assumed to be associated with the native structure according to the thermodynamic hypothesis' @cite_82 . These search methods include simulated annealing @cite_70 @cite_18 , basin hopping @cite_67 @cite_15 @cite_9 @cite_47 , evolutionary algorithms @cite_32 @cite_71 @cite_37 and MC simulation with biased moves @cite_50 @cite_75 @cite_44 . A review of conformation sampling methods for protein folding can be found in @cite_69 . Sampling methods have two major limitations, namely 1) they do not provide any information about the biological pathway; and 2) finding the global minimum is not guaranteed because of the finite number of samples.
@cite_18 @cite_67 @cite_47 @cite_37 @cite_69 @cite_70 @cite_9 @cite_32 @cite_44 @cite_71 @cite_50 @cite_15 @cite_75 @cite_82
2154106236 2013785414 1979591743 2145874860 2088270506 2150672210 2124106603 2024844609 1993018469 2049650691 2027638447 1986602910 2078204120 78256357
We explore the ability of a simple simulated annealing procedure to assemble native-like structures from fragments of unrelated protein structures with similar local sequences using Bayesian scoring functions. Environment and residue pair specific contributions to the scoring functions appear as the first two terms in a series expansion for the residue probability distributions in the protein database; the decoupling of the distance and environment dependencies of the distributions resolves the major problems with current database-derived scoring functions noted by Thomas and Dill. The simulated annealing procedure rapidly and frequently generates native-like structures for small helical proteins and better than random structures for small b sheet containing proteins. Most of the simulated structures have native-like solvent accessibility and secondary structure patterns, and thus ensembles of these structures provide a particularly challenging set of decoys for evaluating scoring functions. We investigate the effects of multiple sequence information and different types of conformational constraints on the overall performance of the method, and the ability of a variety of recently developed scoring functions to recognize the native-like conformations in the ensembles of simulated structures. # 1997 Academic Press Limited Abstract A Monte Carlo-minimization method has been developed to overcome the multiple-minima problem. The Metropolis Monte Carlo sampling, assisted by energy minimization, surmounts intervening barriers in moving through successive discrete local minima in the multidimensional energy surface. The method has located the lowest-energy minimum thus far reported for the brain pentapeptide [Met5]enkephalin in the absence of water. Presumably it is the global minimum-energy structure. This supports the concept that protein folding may be a Markov process. In the presence of water, the molecules appear to exist as an ensemble of different conformations. Associative memory Hamiltonian structure prediction potentials are not overly rugged, thereby suggesting their landscapes are like those of actual proteins. In the present contribution we show how basin-hopping global optimization can identify low-lying minima for the corresponding mildly frustrated energy landscapes. For small systems the basin-hopping algorithm succeeds in locating both lower minima and conformations closer to the experimental structure than does molecular dynamics with simulated annealing. For large systems the efficiency of basin-hopping decreases for our initial implementation, where the steps consist of random perturbations to the Cartesian coordinates. We implemented umbrella sampling using basin-hopping to further confirm when the global minima are reached. We have also improved the energy surface by employing bioinformatic techniques for reducing the roughness or variance of the energy surface. Finally, the basin-hopping calculations have guided improvements in the excluded volume of the Hamiltonian, producing better structures. These results suggest a novel and transferable optimization scheme for future energy function development. The search for efficient and predictive methods to describe the protein folding process at the all-atom level remains an important grand-computational challenge. The development of multi-teraflop architectures, such as the IBM BlueGene used in this study, has been motivated in part by the large computational requirements of such studies. Here we report the predictive all-atom folding of the forty-amino acid HIV accessory protein using an evolutionary stochastic optimization technique. We implemented the optimization method as a master-client model on an IBM BlueGene, where the algorithm scales near perfectly from 64 to 4096 processors in virtual processor mode. Starting from a completely extended conformation, we optimize a population of 64 conformations of the protein in our all-atom free-energy model PFF01. Using 2048 processors the algorithm predictively folds the protein to a near-native conformation with an RMS deviation of 3.43 A in <24 h. © 2007 Wiley Periodicals, Inc. J Comput Chem, 2007 Abstract In the last decades biomolecular simulation has made tremendous inroads to help elucidate biomolecular processes in-silico. Despite enormous advances in molecular dynamics techniques and the available computational power, many problems involve long time scales and large-scale molecular rearrangements that are still difficult to sample adequately. In this review we therefore summarise recent efforts to fundamentally improve this situation by decoupling the sampling of the energy landscape from the description of the kinetics of the process. Recent years have seen the emergence of many advanced sampling techniques, which permit efficient characterisation of the relevant family of molecular conformations by dispensing with the details of the short-term kinetics of the process. Because these methods generate thermodynamic information at best, they must be complemented by techniques to reconstruct the kinetics of the process using the ensemble of relevant conformations. Here we review recent advances for both types of methods and discuss their perspectives to permit efficient and accurate modelling of large-scale conformational changes in biomolecules. This article is part of a Special Issue entitled: Protein Dynamics: Experimental and Computational Approaches. We compare a few variants of the recently proposed multicanonical method with the well known simulated annealing for the effectiveness in search of the energy global minimum of a biomolecular system. For this we study in detail Met-enkephalin, one of the simplest peptides. We show that the new method not only outperforms simulated annealing in the search of the energy groundstate but also provides more statistical-mechanical information about the system. A comparison of two methods for surmounting the multiple-minima problem, Simulated Annealing (SA) and Monte Carlo with Minimization (MCM), is presented with applications to [Met]-enkephalin in the absence and in the presence of water. SA explores a continuous space of internal variables, while MCM explores a discrete space consisting of the local energy minima on that space. Starting from random conformations chosen from the whole conformational space in both cases, it is found that, while SA converges to low-energy structures significantly faster than MCM, the former does not converge to a unique minimum whereas the latter does. Furthermore, the behavior of the RMS deviations with respect to the apparent global minimum (for enkephalin in the absence of water) shows no correlation with the observed overall energy decrease in the case of SA, whereas such a correlation is quite evident with MCM; this implies that, even though the potential energy decreases in the annealing process, the Monte Carlo SA trajectory does not proceed towards the global minimum. Possible reasons for these differences between the two methods are discussed. It is concluded that, while SA presents attractive prospects for possibly improving or refining given structures, it must be considered inferior to MCM, at least in problems where little or no structural information is available for the molecule of interest. We report the predictive all-atom folding of the 60 amino acid four-helix bacterial ribosomal protein (BRP) L20 with a stochastic evolutionary optimization method in a free-energy force field. The energetically best, as well as six of the 10 lowest conformations, converge to a near-native structure. All of the 10 best energy conformations share the secondary structure elements of the native conformation, but differ in their tertiary alignment. The best conformation has a backbone root-mean-square deviation of 4.6 A to the native conformation and reproduces most distance constraints of the NMR experiment to 1.5 A resolution. Starting from random initial conditions, the native content of the simulated population increases more than 60-fold in the course of the simulation. These data demonstrate the feasibility of predictive unbiased all-atom protein folding with present day computational resources for the BRP L20. The results of basin-hopping global optimization simulations are presented for four small, α-helical proteins described by a coarse-grained potential. A step-taking scheme that incorporates the local conformational preferences extracted from a large number of high-resolution protein structures is compared with an unbiased scheme. In addition, the discrete path sampling method is used to investigate the folding of one of the proteins, namely, the villin headpiece subdomain. Folding times from kinetic Monte Carlo simulations and iterative calculations based on a Markovian first-step analysis for the resulting stationary-point database are in good mutual agreement, but differ significantly from the experimental values, probably because the native state is not the global free energy minimum for the potential employed. 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. Abstract Two major components are required for a successful prediction of the three-dimensional structure of peptides and proteins: an efficient global optimization procedure which is capable of finding an appropriate local minimum for the strongly anisotropic function of hundreds of variables, and a set of free energy components for a protein molecule in solution which are computationally inexpensive enough to be used in the search procedure, yet sufficiently accurate to ensure the uniqueness of the native conformation. We here found an efficient way to make a random step in a Monte Carlo procedure given knowledge of the energy or statistical properties of conformational subspaces (e.g. φ-ψ zones or side-chain torsion angles). This biased probability Monte Carlo (BPMC) procedure randomly selects the subspace first, then makes a step to a new random position independent of the previous position, but according to the predefined continuous probability distribution. The random step is followed by a local minimization in torsion angle space. The positions, sizes and preferences for high-probability zones on φ-ψ maps and χ-angle maps were calculated for different residue types from the representative set of 191 and 161 protein 3D-structures, respectively. A fast and precise method to evaluate the electrostatic energy of a protein in solution is developed and combined with the BPMC procedure. The method is based on the modified spherical image charge approximation, efficiently projected onto a molecule of arbitrary shape. Comparison with the finite-difference solutions of the Poisson-Boltzmann equation shows high accuracy for our approach. The BPMC procedure is applied successfully to the structure prediction of 12- and 16-residue synthetic peptides and the determination of protein structure from NMR data, with the immunoglobulin binding domain of streptococcal protein G as an example. The BPMC runs display much better convergence properties than the non-biased simulations. The advantage of a true global optimization procedure for NMR structure determination is its ability to cope with local minima originating from data errors and ambiguities in NMR data. We describe a global optimization technique using “basin-hopping” in which the potential energy surface is transformed into a collection of interpenetrating staircases. This method has been designed to exploit the features that recent work suggests must be present in an energy landscape for efficient relaxation to the global minimum. The transformation associates any point in configuration space with the local minimum obtained by a geometry optimization started from that point, effectively removing transition state regions from the problem. However, unlike other methods based upon hypersurface deformation, this transformation does not change the global minimum. The lowest known structures are located for all Lennard-Jones clusters up to 110 atoms, including a number that have never been found before in unbiased searches. Prediction of three-dimensional structures of proteins and peptides by global optimization of the free energy estimate has been attempted without much success for over thirty years. The key problems were the insufficient accuracy of the free energy estimate and the giant size of the conformational space. Global optimization of the free energy function of a peptide in internal coordinate space is a powerful method of structure prediction that outperforms both Molecular Dynamics, bound by the continuity requirement, and Monte Carlo, bound by the Boltzmann ensemble generation requirement. We demonstrate that stochastic global optimization algorithms of the first order, i.e., with local minimization after each iteration (e.g., Monte Carlo-Minimization), have a greater chance of finding the global minimum after a fixed number of function evaluations. Recently, the principle of optimal bias was mathematically justified and the Optimal-Bias Monte Carlo-Minimization algorithm (a.k.a. Biased Probability Monte Carlo-minimization) was successfully applied to theoreticalab initiofolding of several peptides, resulting in more than a 10-fold increase in efficiency compared to the Monte Carlo-Minimization method. The square-root bias is shown to be comparable in performance with the previously derived linear bias. A 23-residue peptide of beta-beta-alpha structure can be predicted from any random starting conformation. Stanford Moore, William Stein, and Anfinsen were awarded the Nobel Prize in Chemistry in 1972 for "their contribution to the understanding of the connection between chemical structure and catalytic activity of the active center of the ribonuclease molecule." In his Nobel Lecture, Anfinsen provided a sketch of the rich history of research that provided the foundation for his work on protein folding and the "Thermodynamic Hypothesis," and outlined potential avenues of current and future scientific exploration.