Protein structure prediction using a combination of sequence homology and global energy minimization I. Global energy minimization of surface loops

A procedure has been developed for global energy minimization of surface loops of proteins in the presence of a fixed core. The ECEPP potential function has been modified to allow more accurate representations of hydrogen bond interactions and intrinsic torsional energies. A computationally efficient representation of hydration free energy has been introduced. A local minimization procedure has been developed that uses a cutoff distance, minimization with respect to subsets of degrees of freedom, analytical second derivatives, and distance constraints between rigid segments to achieve efficiency in applications to surface loops. Efficient procedures have been developed for deforming segments of the initial backbone structure and for removing overlaps. Global energy minimization of a surface loop is accomplished by generating a sequence (or a trajectory) of local minima, the component steps of which are generated by searching collections of local minima obtained by deforming seven-residue segments of the surface loop. The search at each component step consists of the following calculations: (1) A large collection of backbone structures is generated by deforming a seven-residue segment of the initial backbone structure. (2) A collection of low-energy backbone structures is generated by applying local energy minimization to the resulting collection of backbone structures (interactions involving side chains that will be searched in this component step are not included in the energy). (3) One low-energy side-chain structure is generated for each of the resulting low-energy backbone structures. (4) A collection of low-energy local minima is generated by applying local energy minimization to the resulting collection of structures. (5) The local minimum with the lowest energy is retained as the next point of the trajectory. Applications of our global search procedure to surface segments of bovine pancreatic trypsin inhibitor (BPTI) and bovine trypsin suggest that component-step searches are reasonably complete. The computational efficiency of component-step searches is such that trajectories consisting of about 10 component steps are feasible using an FPS-5200 array processor. Our procedure for global energy minimization of surface loops is being used to identify and correct problems with the potential function and to calculate protein structure using a combination of sequence homology and global energy minimization.     

A new method for the gradient‐based optimization of molecular complexes

We present a novel method for the local optimization of molecular complexes. This new approach is especially suited for usage in molecular docking. In molecular modeling, molecules are often described employing a compact representation to reduce the number of degrees of freedom. This compact representation is realized by fixing bond lengths and angles while permitting changes in translation, orientation, and selected dihedral angles. Gradient‐based energy minimization of molecular complexes using this representation suffers from well‐known singularities arising during the optimization process. We suggest an approach new in the field of structure optimization that allows to employ gradient‐based optimization algorithms for such a compact representation. We propose to use exponential mapping to define the molecular orientation which facilitates calculating the orientational gradient. To avoid singularities of this parametrization, the local minimization algorithm is modified to change efficiently the orientational parameters while preserving the molecular orientation, i.e. we perform well‐defined jumps on the objective function. Our approach is applicable to continuous, but not necessarily differentiable objective functions. We evaluated our new method by optimizing several ligands with an increasing number of internal degrees of freedom in the presence of large receptors. In comparison to the method of Solis and Wets in the challenging case of a non‐differentiable scoring function, our proposed method leads to substantially improved results in all test cases, i.e. we obtain better scores in fewer steps for all complexes. © 2008 Wiley Periodicals, Inc. J Comput Chem, 2009     

Optimization and dynamics of protein-protein complexes using B-splines

A moving-grid approach for optimization and dynamics of protein-protein complexes is introduced, which utilizes cubic B-spline interpolation for rapid energy and force evaluation. The method allows for the efficient use of full electrostatic potentials joined smoothly to multipoles at long distance so that multiprotein simulation is possible. Using a recently published benchmark of 58 protein complexes, we examine the performance and quality of the grid approximation, refining cocrystallized complexes to within 0.68 A RMSD of interface atoms, close to the optimum 0.63 A produced by the underlying MMFF94 force field. We quantify the theoretical statistical advantage of using minimization in a stochastic search in the case of two rigid bodies, and contrast it with the underlying cost of conjugate gradient minimization using B-splines. The volumes of conjugate gradient minimization basins of attraction in cocrystallized systems are generally orders of magnitude larger than well volumes based on energy thresholds needed to discriminate native from nonnative states; nonetheless, computational cost is significant. Molecular dynamics using B-splines is doubly efficient due to the combined advantages of rapid force evaluation and large simulation step sizes. Large basins localized around the native state and other possible binding sites are identifiable during simulations of protein-protein motion. In addition to providing increased modeling detail, B-splines offer new algorithmic possibilities that should be valuable in refining docking candidates and studying global complex behavior.     

Population-based local search for protein folding simulation in the MJ energy model and cubic lattices

We present experimental results on benchmark problems in 3D cubic lattice structures with the Miyazawa–Jernigan energy function for two local search procedures that utilise the pull-move set: (i) population-based local search (PLS) that traverses the energy landscape with greedy steps towards (potential) local minima followed by upward steps up to a certain level of the objective function; (ii) simulated annealing with a logarithmic cooling schedule (LSA). The parameter settings for PLS are derived from short LSA-runs executed in pre-processing and the procedure utilises tabu lists generated for each member of the population. In terms of the total number of energy function evaluations both methods perform equally well, however, PLS has the potential of being parallelised with an expected speed-up in the region of the population size. Furthermore, both methods require a significant smaller number of function evaluations when compared to Monte Carlo simulations with kink-jump moves.     

Analysis of the genetic algorithm method of molecular conformation determination

Many important problems in chemistry require knowledge of the 3-D conformation of a molecule. A commonly used computational approach is to search for a variety of low-energy conformations. Here, we study the behavior of the genetic algorithm (GA) method as a global search technique for finding these low-energy conformations. Our test molecule is cyclic hexaglycine. The goal of this study is to determine how to best utilize GAs to find low-energy populations of conformations given a fixed amount of CPU time. Two measures are presented that help monitor the improvement in the GA populations and their loss of diversity. Different hybrid methods that combine coarse GA global search with local gradient minimization are evaluated. We present several specific recommendations about trade-offs when choosing GA parameters such as population size, number of generations, rate of interaction between subpopulations, and combinations of GA and gradient minimization. In particular, our results illustrate why approaches that emphasize convergence of the GA can actually decrease its effectiveness as a global conformation search method. © John Wiley & Sons, Inc.     

用于真实蛋白质结构预测的一种新的优化方法

用"相对熵"作为优化函数,提出了一个有效快速的折叠预测优化算法.使用了非格点模型,预测只关心蛋白质主链的走向.其中只用到了蛋白质主链上的两两连续的Cα原子间的距离信息以及20种氨基酸的接触势的一个扩展形式.对几个真实蛋白质做了算法测试,预测的初始结构都为比较大的去折叠态,预测构象相对于它们天然结构的均方根偏差(RMSD)为5～7 A.从原理上讲,该方法是对能量优化的改进.     

An analysis of the structural and energetic properties of deoxyribose by potential energy methods

We discuss the three fundamental issues of a computational approach in structure prediction by potential energy minimization, and analyze them for the nucleic acid component deoxyribose. Predicting the conformation of deoxyribose is important not only because of the molecule's central conformational role in the nucleotide backbone, but also because energetic and geometric discrepancies from experimental data have exposed some underlying uncertainties in potential energy calculations. The three fundamental issues examined here are: (i) choice of coordinate system to represent the molecular conformation; (ii) construction of the potential energy function; and (iii) choice of the minimization technique. For our study, we use the following combination. First, the molecular conformation is represented in cartesian coordinate space with the full set of degrees of freedom. This provides an opportunity for comparison with the pseudorotation approximation. Second, the potential energy function is constructed so that all the interactions other than the nonbonded terms are represented by polynomials of the coordinate variables. Third, two powerful Newton methods that are globally and quadratically convergent are implemented: Gill and Murray's Modified Newton method and a Truncated Newton method, specifically developed for potential energy minimization. These strategies have produced the two experimentally-observed structures of deoxyribose with geometric data (bond angles and dihedral angles) in very good agreement with experiment. More generally, the application of these modeling and minimization techniques to potential energy investigations is promising. The use of cartesian variables and polynomial representation of bond length, bond angle and torsional potentials promotes efficient second-derivative computation and, hence, application of Newton methods. The truncated Newton, in particular, is ideally suited for potential energy minimization not only because the storage and computational requirements of Newton methods are made manageable, but also because it contains an important algorithmic adaptive feature: the minimization search is diverted from regions where the function is nonconvex and is directed quickly toward physically interesting regions.     

Comparison of line search minimization algorithms for exploring topography of multidimensional potential energy surfaces: Mg+Arn case

The most robust numerical algorithms for unconstrained optimization that involve a line search are tested in the problem of locating stable structures and transition states of atomic microclusters. Specifically, the popular quenching technique is compared with conjugate gradient and variable metric algorithms in the Mg⁺Ar_n clusters. It is found that the variable metric method BFGS combined with an approximate line minimization routine is the most efficient, and it shows global convergence properties. This technique is applied to find a few hundred stationary points of Mg⁺Ar₁₂ and to locate isomerization paths between the two most stable icosahedral structures found for Mg⁺Ar₁₂. The latter correspond to a solvated and a nonsolvated ion, respectively. © 1997 John Wiley & Sons, Inc. J Comput Chem 18 :1011–1022, 1997     

Ab initio crystal structure prediction-I. Rigid molecules

A new methodology for the prediction of molecular crystal structures using only the atomic connectivity of the molecule under consideration is presented. The approach is based on the global minimization of the lattice enthalpy of the crystal. The modeling of the electrostatic interactions is accomplished through a set of distributed charges that are optimally and automatically selected and positioned based on results of quantum mechanical calculations. A four-step global optimization algorithm is used for the identification of the local minima of the lattice enthalpy surface. A parallelized implementation of the algorithm permits a much more extensive search of the solution space than has hitherto been possible, allowing the identification of crystal structures in less frequently occurring space groups and with more than one molecule in the asymmetric unit. The algorithm has been applied successfully to the prediction of the crystal structures of 3-aza-bicyclo(3.3.1)nonane-2,4-dione (P2(1)/a, Z' = 1), allopurinol (P2(1)/c, Z' = 1), 1,3,4,6,7,9-hexa-azacycl(3.3.3)azine (Pbca, Z' = 2), and triethylenediamine (P6(3)/m, Z' = 1). In all cases, the experimentally known structure is among the most stable predicted structures, but not necessarily the global minimum.     

Conformational search using a molecular dynamics–minimization procedure: Applications to clusters of coulombic charges,Lennard–Jones particles,and waters

A new conformational search method, molecular dynamics–minimization (MDM), is proposed, which combines a molecular dynamics sampling strategy with energy minimizations in the search for low-energy molecular structures. This new method is applied to the search for low energy configurations of clusters of coulombic charges on a unit sphere, Lennard–Jones clusters, and water clusters. The MDM method is shown to be efficient in finding the lowest energy configurations of these clusters. A closer comparison of MDM with alternative conformational search methods on Lennard–Jones clusters shows that, although MDM is not as efficient as the Monte Carlo–minimization method in locating the global energy minima, it is more efficient than the diffusion equation method and the method of minimization from randomly generated structures. Given the versatility of the molecular dynamics sampling strategy in comparison to Monte Carlo in treating molecular complexes or molecules in explicit solution, one anticipates that the MDM method could be profitably applied to conformational search problems where the number of degrees of freedom is much greater. © 1998 John Wiley & Sons, Inc. J Comput Chem 19: 60–70, 1998     

Fast computation,rotation, and comparison of low resolution spherical harmonic molecular surfaces

A procedure that rapidly generates an approximate parametric representation of macromolecular surface shapes is described. The parametrization is expressed as an expansion of real spherical harmonic basis functions. The advantage of using a parametric representation is that a pair of surfaces can be matched by using a quasi-Newton algorithm to minimize a suitably chosen objective function. Spherical harmonics are a natural and convenient choice of basis function when the task is one of search in a rotational search space. In particular, rotations of a molecular surface can be simulated by rotating only the harmonic expansion coefficients. This rotational property is applied for the first time to the 3-dimensional molecular similarity problem in which a pair of similar macromolecular surfaces are to be maximally superposed. The method is demonstrated with the superposition of antibody heavy chain variable domains. Special attention is given to computational efficiency. The spherical harmonic expansion coefficients are determined using fast surface sampling and integration schemes based on the tessellation of a regular icosahedron. Low resolution surfaces can be generated and displayed in under 10 s and a pair of surfaces can be maximally superposed in under 3 s on a contemporary workstation. ©1999 John Wiley & Sons, Inc. J Comput Chem 20: 383–395, 1999     

A powerful truncated Newton method for potential energy minimization

With advances in computer architecture and software, Newton methods are becoming not only feasible for large-scale nonlinear optimization problems, but also reliable, fast and efficient. Truncated Newton methods, in particular, are emerging as a versatile subclass. In this article we present a truncated Newton algorithm specifically developed for potential energy minimization. The method is globally convergent with local quadratic convergence. Its key ingredients are: (1) approximation of the Newton direction far away from local minima, (2) solution of the Newton equation iteratively by the linear Conjugate Gradient method, and (3) preconditioning of the Newton equation by the analytic second-derivative components of the “local” chemical interactions: bond length, bond angle and torsional potentials. Relaxation of the required accuracy of the Newton search direction diverts the minimization search away from regions where the function is nonconvex and towards physically interesting regions. The preconditioning strategy significantly accelerates the iterative solution for the Newton search direction, and therefore reduces the computation time for each iteration. With algorithmic variations, the truncated Newton method can be formulated so that storage and computational requirements are comparable to those of the nonlinear Conjugate Gradient method. As the convergence rate of nonlinear Conjugate Gradient methods is linear and performance less predictable, the application of the truncated Newton code to potential energy functions is promising.     

A new Lamarckian genetic algorithm for flexible ligand‐receptor docking

We present a Lamarckian genetic algorithm (LGA) variant for flexible ligand‐receptor docking which allows to handle a large number of degrees of freedom. Our hybrid method combines a multi‐deme LGA with a recently published gradient‐based method for local optimization of molecular complexes. We compared the performance of our new hybrid method to two non gradient‐based search heuristics on the Astex diverse set for flexible ligand‐receptor docking. Our results show that the novel approach is clearly superior to other LGAs employing a stochastic optimization method. The new algorithm features a shorter run time and gives substantially better results, especially with increasing complexity of the ligands. Thus, it may be used to dock ligands with many rotatable bonds with high efficiency. © 2010 Wiley Periodicals, Inc. J Comput Chem, 2010     

Gradient gravitational search: An efficient metaheuristic algorithm for global optimization

The adaptation of novel techniques developed in the field of computational chemistry to solve the concerned problems for large and flexible molecules is taking the center stage with regard to efficient algorithm, computational cost and accuracy. In this article, the gradient‐based gravitational search (GGS) algorithm, using analytical gradients for a fast minimization to the next local minimum has been reported. Its efficiency as metaheuristic approach has also been compared with Gradient Tabu Search and others like: Gravitational Search, Cuckoo Search, and Back Tracking Search algorithms for global optimization. Moreover, the GGS approach has also been applied to computational chemistry problems for finding the minimal value potential energy of two‐dimensional and three‐dimensional off‐lattice protein models. The simulation results reveal the relative stability and physical accuracy of protein models with efficient computational cost. © 2015 Wiley Periodicals, Inc.     

Efficiency of simulated annealing for peptides with increasing geometrical restrictions

Simulated annealing (SA) is a popular global minimizer that can conveniently be applied to complex macromolecular systems. Thus, a molecular dynamics or a Monte Carlo simulation starts at high temperature, which is decreased gradually, and the system is expected to reach the low-energy region on the potential energy surface of the molecule. However, in many cases this process is not efficient. Alternatively, the low-energy region can be reached more effectively by minimizing the energy of selected molecular structures generated along the simulation pathway. The efficiency of SA to locate energy-minimized structures within 5 kcal/mol above the global energy minimum is studied as applied to three peptide models with increasing geometrical restrictions: (1) The linear pentapeptide Leu-enkephalin described by the ECEPP potential, (2) a cyclic hexapeptide described by the GROMOS force field energy E_GRO alone, and (3) the same cyclic peptide with E_GRO combined with a restraining potential based on 31 proton–proton restraints obtained from nuclear magnetic resonance (NMR) experiments. The efficiency of SA is compared to that of the Monte Carlo minimization (MCM) method of Li and Scheraga, and to our local torsional deformations (LTD) method for the conformational search of cyclic molecules. The results for the linear peptide show that SA provides a relatively weak guidance towards the most stable energy region; as expected, this guidance increases for the cyclic peptide and the cyclic peptide with NMR restraints. However, in general, MCM and LTD are significantly more efficient than SA as generators of low-energy minimized structures. This suggests that LTD might provide a better search tool than SA in structure determination of protein regions for which a relatively small number of restraints are provided by NMR. ©1999 John Wiley & Sons, Inc. J Comput Chem 20: 1659–1670, 1999     

A simple computational scheme for obtaining localized bonding schemes and their weights from a CASSCF wave function

We devise and apply a simple computational scheme for obtaining localized bonding schemes and their weights from a CASSCF wave function. These bonding schemes are close to resonance structures drawn by chemists. Firstly, a CASSCF wave function is computed. Secondly, the CASSCF computation is repeated but now the delocalized complete active space MOs are substituted by Weinhold's localized natural atomic orbitals. In this way the original CASSCF wave function is represented by a sequence of Slater determinants composed of localized natural atomic orbitals. Thus, a standard CASSCF wave function can be reinterpreted in terms of a local picture. To test the method we obtain localized bonding schemes and their weights for the ground and the pi-pi* excited state of ethylene. Moreover, bonding schemes and their weights are derived for the ground, the 1(1)B(u), and the 2(1)Ag pi-pi* excited states of trans-butadiene. The large weight bonding schemes are shown to be a qualitative indicator for the known photochemistry of butadiene. The remarkable stability of the Arduengo carbene is discussed by obtaining bonding schemes that indicate a stabilizing delocalization of the pi electrons. We illustrate that the large weight bonding schemes are in line with the observed reactivity of the Arduengo carbene.     

Sampling multiple scoring functions can improve protein loop structure prediction accuracy

Accurately predicting loop structures is important for understanding functions of many proteins. In order to obtain loop models with high accuracy, efficiently sampling the loop conformation space to discover reasonable structures is a critical step. In loop conformation sampling, coarse-grain energy (scoring) functions coupling with reduced protein representations are often used to reduce the number of degrees of freedom as well as sampling computational time. However, due to implicitly considering many factors by reduced representations, the coarse-grain scoring functions may have potential insensitivity and inaccuracy, which can mislead the sampling process and consequently ignore important loop conformations. In this paper, we present a new computational sampling approach to obtain reasonable loop backbone models, so-called the Pareto optimal sampling (POS) method. The rationale of the POS method is to sample the function space of multiple, carefully selected scoring functions to discover an ensemble of diversified structures yielding Pareto optimality to all sampled conformations. The POS method can efficiently tolerate insensitivity and inaccuracy in individual scoring functions and thereby lead to significant accuracy improvement in loop structure prediction. We apply the POS method to a set of 4-12-residue loop targets using a function space composed of backbone-only Rosetta and distance-scale finite ideal-gas reference (DFIRE) and a triplet backbone dihedral potential developed in our lab. Our computational results show that in 501 out of 502 targets, the model sets generated by POS contain structure models are within subangstrom resolution. Moreover, the top-ranked models have a root mean square deviation (rmsd) less than 1 A in 96.8, 84.1, and 72.2% of the short (4-6 residues), medium (7-9 residues), and long (10-12 residues) targets, respectively, when the all-atom models are generated by local optimization from the backbone models and are ranked by our recently developed Pareto optimal consensus (POC) method. Similar sampling effectiveness can also be found in a set of 13-residue loop targets.     

Global optimization using bad derivatives: Derivative-free method for molecular energy minimization

A general method designed to isolate the global minimum of a multidimensional objective function with multiple minima is presented. The algorithm exploits an integral “coarse-graining” transformation of the objective function, U, into a smoothed function with few minima. When the coarse-graining is defined over a cubic neighborhood of length scale ϵ, the exact gradient of the smoothed function, 𝒰_ϵ, is a simple three-point finite difference of U. When ϵ is very large, the gradient of 𝒰_ϵ appears to be a “bad derivative” of U. Because the gradient of 𝒰_ϵ is a simple function of U, minimization on the smoothed surface requires no explicit calculation or differentiation of 𝒰_ϵ. The minimization method is “derivative-free” and may be applied to optimization problems involving functions that are not smooth or differentiable. Generalization to functions in high-dimensional space is straightforward. In the context of molecular conformational optimization, the method may be used to minimize the potential energy or, preferably, to maximize the Boltzmann probability function. The algorithm is applied to conformational optimization of a model potential, Lennard–Jones atomic clusters, and a tetrapeptide. © 1998 John Wiley & Sons, Inc. J Comput Chem 19: 1445–1455, 1998     

A Global Minimization Algorithm for Empirical Contact Potential Functions

Introduction Basedonthethermodynamichypothesis[1],any computionalapproachforsolvingproteinfoldingprob lemsoranabinitiopredictionofproteintertiarystruc turesfromtheirprimarysequences,requiresanempiri calpotentialfunctionthathasitsglobalminimumatthe natives…