A Global Minimization Algorithm for Empirical Contact Potential Functions

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

A Simulated Annealing Algorithm for Training Empirical Potential Functions of Protein Folding

In this paper are reported the local minimum problem by means of current greedy algorithm for training the empirical potential function of protein folding on 8623 non-native structures of 31 globular proteins and a solution of the problem based upon the simulated annealing algorithm. This simulated annealing algorithm is indispensable for developing and testing highly refined empirical potential functions.     

Genetic algorithms for protein conformation sampling and optimization in a discrete backbone dihedral angle space

We have investigated protein conformation sampling and optimization based on the genetic algorithm and discrete main chain dihedral state model. An efficient approach combining the genetic algorithm with local minimization and with a niche technique based on the sharing function is proposed. Using two different types of potential energy functions, a Go-type potential function and a knowledge-based pairwise potential energy function, and a test set containing small proteins of varying sizes and secondary structure compositions, we demonstrated the importance of local minimization and population diversity in protein conformation optimization with genetic algorithms. Some general properties of the sampled conformations such as their native-likeness and the influences of including side-chains are discussed.     

Powerful simulated-annealing algorithm locates global minimum of protein-folding potentials from multiple starting conformations

Protein-folding potentials, designed with the explicit goal that the global energy minimum correspond to crystallographically observed conformations of protein molecules, may offer great promise toward calculating native protein structures. Achieving this promise, however, depends on finding an effective means of dealing with the multiple-minimum problem inherent in such potentials. In this study, a protein-folding-potential test system has been developed that exhibits the properties of general protein-folding potentials yet has a unique well-defined global energy minimum corresponding to the crystallographically determined conformation of the test molecule. A simulated-annealing algorithm is developed that locates the global minimum of this potential in four of eight test runs from random starting conformations. Exploration of the energy-conformation surface of the potential indicates that it contains the numerous local minima typical of protein-folding potentials and that the global minimum is not easily located by conventional minimization procedures. When the annealing algorithm is applied to a previously developed actual folding potential to analyze the conformation of avian pancreatic polypeptide, a new conformer is located that is lower in energy than any conformer located in previous studies using a variety of minimization techniques.     

MSEED: A program for the rapid analytical determination of accessible surface areas and their derivatives

An algorithm for the rapid analytical determination of the accessible surface areas of solute molecules is described. The accessible surface areas as well as the derivatives with respect to the Cartesian coordinates of the atoms are computed by a program called “MSEED,” which is based in part on Connolly's analytical formulas for determining surface area. Comparisons of the CPU time required for MSEED, Connolly's numerical algorithm DOT, and a program for surface area determination (ANA) based on Connolly's analytical algorithm, are presented. MSEED is shown to be as much as 70 times faster than ANA and up to 11 times faster than DOT for several proteins. The greater speed of MSEED is achieved partially because nonproductive computation of the surface areas of internal atoms is avoided. A sample minimization of an energy function, which included a term for hydration, was carried out on MET-enkephalin using MSEED to compute the solvent-accessible surface area and its derivatives. The potential employed was ECEPP/2 plus an empirical potential for solvation based on the solvent-accessible surface area of the peptide. The CPU time required for 150 steps of minimization with the potential that included solvation was approximately twice as great as the CPU time required for 150 steps of minimization with the ECEPP/2 potential only.     

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

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

First Step Towards Planning of Syntheses in Solid-State Chemistry: Determination of Promising Structure Candidates by Global Optimization

A method is presented here that allows, in principle, the prediction of the existence and structure of (meta)stable solid compounds. It is based on a set of adjustable modules that are applied to the study of the energy function of the chemical system of interest. The main elements are a set of routines for global optimization and local minimization, as well as algorithms for the investigation of the phase space structure near local minima of the potential energy, and the analysis and characterization of the structure candidates. The current implementation focuses on ionic compounds, for which empirical potentials are used for the evaluation of the energy function in the first stage, and a Hartree–Fock algorithm for refinements. The global optimization is performed with a stochastic simulated annealing algorithm, and the local minimization employs stochastic quenches and gradient methods. The neighborhoods of the local minima are studied with the threshold algorithm. The results of this approach are illustrated with a number of examples: compounds of binary noble gases, and binary and ternary ionic compounds. These include several substances that have not been synthesized yet, but should stand a fair chance of being kinetically stable, for example further alkali metal nitrides besides Li₃N, as well as Ca₃SiBr₂ or SrTi₂O₅.     

Semiglobal simplex optimization and its application to determining the preferred solvation sites of proteins

The classical simplex method is extended into the Semiglobal Simplex (SGS) algorithm. Although SGS does not guarantee finding the global minimum, it affords a much more thorough exploration of the local minima than any traditional minimization method. The basic idea of SGS is to perform a local minimization in each step of the simplex algorithm, and thus, similarly to the Convex Global Underestimator (CGU) method, the search is carried out on a surface spanned by local minima. The SGS and CGU methods are compared by minimizing a set of test functions of increasing complexity, each with a known global minimum and many local minima. Although CGU delivers substantially better success rates in simple problems, the two methods become comparable as the complexity of the problems increases. Because SGS is generally faster than CGU, it is the method of choice for solving optimization problems in which function evaluation is computationally inexpensive and the search region is large. The extreme simplicity of the method is also a factor. The SGS method is applied here to the problem of finding the most preferred (i.e., minimum free energy) solvation sites on a streptavidin monomer. It is shown that the SGS method locates the same lowest free energy positions as an exhaustive multistart Simplex search of the protein surface, with less than one-tenth the number of minizations. The combination of the two methods, i.e.. multistart simplex and SGS, provides a reliable procedure for predicting all potential solvation sites of a protein.     

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.     

Parametrization of analytic interatomic potential functions using neural networks

A generalized method that permits the parameters of an arbitrary empirical potential to be efficiently and accurately fitted to a database is presented. The method permits the values of a subset of the potential parameters to be considered as general functions of the internal coordinates that define the instantaneous configuration of the system. The parameters in this subset are computed by a generalized neural network (NN) with one or more hidden layers and an input vector with at least 3n-6 elements, where n is the number of atoms in the system. The Levenberg-Marquardt algorithm is employed to efficiently affect the optimization of the weights and biases of the NN as well as all other potential parameters being treated as constants rather than as functions of the input coordinates. In order to effect this minimization, the usual Jacobian employed in NN operations is modified to include the Jacobian of the computed errors with respect to the parameters of the potential function. The total Jacobian employed in each epoch of minimization is the concatenation of two Jacobians, one containing derivatives of the errors with respect to the weights and biases of the network, and the other with respect to the constant parameters of the potential function. The method provides three principal advantages. First, it obviates the problem of selecting the form of the functional dependence of the parameters upon the system's coordinates by employing a NN. If this network contains a sufficient number of neurons, it will automatically find something close to the best functional form. This is the case since Hornik et al., [Neural Networks 2, 359 (1989)] have shown that two-layer NNs with sigmoid transfer functions in the first hidden layer and linear functions in the output layer are universal approximators for analytic functions. Second, the entire fitting procedure is automated so that excellent fits are obtained rapidly with little human effort. Third, the method provides a procedure to avoid local minima in the multidimensional parameter hyperspace. As an illustrative example, the general method has been applied to the specific case of fitting the ab initio energies of Si(5) clusters that are observed in a molecular dynamics (MD) simulation of the machining of a silicon workpiece. The energies of the Si(5) configurations obtained in the MD calculations are computed using the B3LYP procedure with a 6-31G(**) basis set. The final ab initio database, which comprises the density functional theory energies of 10 202 Si(5) clusters, is fitted to an empirical Tersoff potential containing nine adjustable parameters, two of which are allowed to be the functions of the Si(5) configuration. The fitting error averaged over all 10 202 points is 0.0148 eV (1.43 kJ mol(-1)). This result is comparable to the accuracy achieved by more general fitting methods that do not rely on an assumed functional form for the potential surface.     

Heuristic-based tabu search algorithm for folding two-dimensional AB off-lattice model proteins

The protein structure prediction problem is a classical NP hard problem in bioinformatics. The lack of an effective global optimization method is the key obstacle in solving this problem. As one of the global optimization algorithms, tabu search (TS) algorithm has been successfully applied in many optimization problems. We define the new neighborhood conformation, tabu object and acceptance criteria of current conformation based on the original TS algorithm and put forward an improved TS algorithm. By integrating the heuristic initialization mechanism, the heuristic conformation updating mechanism, and the gradient method into the improved TS algorithm, a heuristic-based tabu search (HTS) algorithm is presented for predicting the two-dimensional (2D) protein folding structure in AB off-lattice model which consists of hydrophobic (A) and hydrophilic (B) monomers. The tabu search minimization leads to the basins of local minima, near which a local search mechanism is then proposed to further search for lower-energy conformations. To test the performance of the proposed algorithm, experiments are performed on four Fibonacci sequences and two real protein sequences. The experimental results show that the proposed algorithm has found the lowest-energy conformations so far for three shorter Fibonacci sequences and renewed the results for the longest one, as well as two real protein sequences, demonstrating that the HTS algorithm is quite promising in finding the ground states for AB off-lattice model proteins.     

Analysis and prediction of hydrogen bonding in protein-DNA complexes using parallel processors

A number of essential biological functions are controlled by proteins that bind to specific sequences in genomic DNA. In this article we present a simplified model for analyzing DNA-protein interactions mediated exclusively by hydrogen bonds. Based on this model, an optimized algorithm for geometric pattern recognition was developed. The large number of local energy minima are efficiently screened by using a geometric approach to pattern matching based on a square-well potential. The second part of the algorithm represents a closed form solution for minimization based on a quadratic potential. A Monte Carlo method applied to a modified Lennard-Jones potential is used as a third step to rank DNA sequences in terms of pattern matching. Using protein structures derived from four DNA-protein complexes with three-dimensional coordinates established by X-ray diffraction analysis, all possible DNA sequences to which these proteins could bind were ranked in terms of binding energies. The algorithm predicts the correct DNA sequence when at least two hydrogen bonds per base pair are involved in binding to the protein, providing a partial solution to the three-dimensional docking problem. This study lays a framework for future refinements of the algorithm in which the number of assumptions made in the present analysis are reduced. © 1996 by John Wiley & Sons, Inc.     

Can a physics‐based,all‐atom potential find a protein's native structure among misfolded structures? I. Large scale AMBER benchmarking

Recent work has shown that physics-based, all-atom energy functions (AMBER, CHARMM, OPLS-AA) and local minimization, when used in scoring, are able to discriminate among native and decoy structures. Yet, there have been only few instances reported of the successful use of physics based potentials in the actual refinement of protein models from a starting conformation to one that ends in structures, which are closer to the native state. An energy function that has a global minimum energy in the protein's native state and a good correlation between energy and native-likeness should be able to drive model structures closer to their native structure during a conformational search. Here, the possible reasons for the discrepancy between the scoring and refinement results for the case of AMBER potential are examined. When the conformational search via molecular dynamics is driven by the AMBER potential for a large set of 150 nonhomologous proteins and their associated decoys, often the native minimum does not appear to be the lowest free energy state. Ways of correcting the potential function in order to make it more suitable for protein model refinement are proposed.     

Quantum-Chemical and semiclassical calculations of intermolecular interactions of phospholipids

By use of empirical 0–1–6–12 atom–atom potential functions and the PCILOCC method intra- and intermolecular interactions of glycero–phosphoryl–ethanolamine model head groups in a planar layer crystal were calculated. Starting from investigations of the two-dimensional energy-contour diagrams the minima of energy as a function of all head group torsion angles were calculated using a gradient procedure. Within an interval of 15 kcal/mol above the energy of the global minimum we obtained about 30 local minima. These results demonstrate a high flexibility of the investigated phosphorylethanolamine head group in agreement with experiment. The ethanolamine moiety exists in enantiomeric conformations. With the torsion angles of the 0–1–6–12 energy minimization procedure PCILOCC calculations were carried out. These calculations yield the x-ray conformation as the most stable one (unit-cell stabilization energy = ?36.3 kcal/mol). The PCILOCC as well as the potential function calculations show that the conformation of phospholipid head groups in layer crystals is determined by intramolecular as well as by intermolecular interactions with neighboring phospholipid molecules.     

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.     

Energy design for protein-protein interactions

Proteins bind to other proteins efficiently and specifically to carry on many cell functions such as signaling, activation, transport, enzymatic reactions, and more. To determine the geometry and strength of binding of a protein pair, an energy function is required. An algorithm to design an optimal energy function, based on empirical data of protein complexes, is proposed and applied. Emphasis is made on negative design in which incorrect geometries are presented to the algorithm that learns to avoid them. For the docking problem the search for plausible geometries can be performed exhaustively. The possible geometries of the complex are generated on a grid with the help of a fast Fourier transform algorithm. A novel formulation of negative design makes it possible to investigate iteratively hundreds of millions of negative examples while monotonically improving the quality of the potential. Experimental structures for 640 protein complexes are used to generate positive and negative examples for learning parameters. The algorithm designed in this work finds the correct binding structure as the lowest energy minimum in 318 cases of the 640 examples. Further benchmarks on independent sets confirm the significant capacity of the scoring function to recognize correct modes of interactions.     

Adhesion and debonding of soft elastic films: crack patterns, metastable pathways, and forces

We study the phenomenon of debonding in a thin soft elastic film sandwiched between two rigid plates as one of the plates is brought into intimate contact and then pulled away from contact proximity by application of a normal force. Nonlinear simulations based on minimization of total energy (composed of stabilizing elastic strain energy and destabilizing adhesive interaction energy) are employed to address the problems of contact hysteresis, cavitation, crack morphology, variation of contact area, snap-off distance, pull-off force, work done, and energy loss. Below a critical distance (d(c)) upon approach, simulations show the formation of columnar structures and nonrandom, regularly arranged nanocavities at the soft interface at a length scale of approximately 3h (h being the thickness of the film). The persistence of such instability upon withdrawal (distance >d(c)) indicates a contact hysteresis, which is caused by an energy barrier that separates the metastable states of the patterned configuration and the global minimum state of the flat film. The energy and the pull-off force are found to be nonequilibrium and nonunique properties depending on the initial contact, defects, noise, etc. Three broad pathways of debonding leading to adhesive failure of the interface, depending on the stiffness of the film, step size of withdrawal, and the imposed noise, are identified: a catastrophic column collapse mode, a peeling mode involving a continuous decrease in the contact area, and a column splitting mode. The first two modes are caused by a very high stress concentration near the cavity edges. These metastable patterned configurations engender pull-off forces that are orders of magnitude smaller than that required to separate two flat surfaces from contact.     

Deterministic global optimization of molecular structures using interval analysis

The search for the global minimum of a molecular potential energy surface is a challenging problem. The molecular structure corresponding to the global minimum is of particular importance because it usually dictates both the physical and chemical properties of the molecule. The existence of an extremely large number of local minima, the number of which may increase exponentially with the size of the molecule, makes this global minimization problem extremely difficult. A new strategy is described here for solving such global minimization problems deterministically. The methodology is based on interval analysis, and provides a mathematical and computational guarantee that the molecular structure with the global minimum potential energy will be found. The technique is demonstrated using two sets of example problems. The first set involves a relatively simple potential model, and problems with up to 40 atoms. The second set involves a more realistic potential energy function, representative of those in current use, and problems with up to 11 atoms.     

Atomic decomposition of the protein solvation free energy and its application to amyloid-beta protein in water

We report the development of an atomic decomposition method of the protein solvation free energy in water, which ascribes global change in the solvation free energy to local changes in protein conformation as well as in hydration structure. So far, empirical decomposition analyses based on simple continuum solvation models have prevailed in the study of protein-protein interactions, protein-ligand interactions, as well as in developing scoring functions for computer-aided drug design. However, the use of continuum solvation model suffers serious drawbacks since it yields the protein free energy landscape which is quite different from that of the explicit solvent model and since it does not properly account for the non-polar hydrophobic effects which play a crucial role in biological processes in water. Herein, we develop an exact and general decomposition method of the solvation free energy that overcomes these hindrances. We then apply this method to elucidate the molecular origin for the solvation free energy change upon the conformational transitions of 42-residue amyloid-beta protein (Aβ42) in water, whose aggregation has been implicated as a primary cause of Alzheimer's disease. We address why Aβ42 protein exhibits a great propensity to aggregate when transferred from organic phase to aqueous phase.     

On the investigation of the low-energy conformational space of molecules

A new perspective on traditional energy minimization problems is provided by a connection between statistical thermodynamics and combinatorial optimization (finding the minimum of a function depending on many variables). The joint use of a new method for uncovering the global minimum of intramolecular potential energy functions, based on following the asymptotic behavior of a system of stochastic differential equations, and an iterative-improvement technique, whereby a search for relative minima is made by carrying out local quasi-Newton minimizations starting from many distinct points of the energy hypersurface, proved most effective for investigating the low-energy conformational space of molecules.