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.     

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.     

From molecule to solid: The prediction of organic crystal structures

A method for predicting the structure of a molecular crystal based on the systematic search for a global potential energy minimum is considered. The method takes into account unequal occurrences of the structural classes of organic crystals and symmetry of the multidimensional configuration space. The programs of global minimization PMC, comparison of crystal structures CRYCOM, and approximation to the distributions of the electrostatic potentials of molecules FitMEP are presented as tools for numerically solving the problem. Examples of predicted structures substantiated experimentally and the experience of author’s participation in international tests of crystal structure prediction organized by the Cambridge Crystallographic Data Center (Cambridge, UK) are considered.     

Calculation of the minimum energy conformation of acetylcholine using a global optimization technique

The conformational energy of acetylcholine is minimized with respect to the distances between nonbonded atoms with the help of the Bremermann method of unconstrained global optimization. The set of distances for which the energy is the absolute minimum is then used to calculate the coordinates of all the atoms and hence the conformation of the molecule. The simplest type of potential function, namely the classical potential function is chosen for the calculation. The major advantages of this method are (i) that the starting point need not be close to the actual solution, (ii) that it gives the global minimum, irrespective of the starting point, (iii) that it is very general and can be used for any type of potential function, and (iv) that it does not require the computation of gradients. The results obtained are in very good agreement with those of other workers.     

Global optimization of binary Lennard-Jones clusters using three perturbation operators

Global optimization of binary Lennard-Jones clusters is a challenging problem in computational chemistry. The difficulty lies in not only that there are enormous local minima on the potential energy surface but also that we must determine both the coordinate position and the atom type for each atom and thus have to deal with both continuous and combinatorial optimization. This paper presents a heuristic algorithm (denoted by 3OP) which makes extensive use of three perturbation operators. With these operators, the proposed 3OP algorithm can efficiently move from a poor local minimum to another better local minimum and detect the global minimum through a sequence of local minima with decreasing energy. The proposed 3OP algorithm has been evaluated on a set of 96 × 6 instances with up to 100 atoms. We have found most putative global minima listed in the Cambridge Cluster Database as well as discovering 12 new global minima missed in previous research.     

A Global Minimization Algorithm for Empirical Contact Potential Functions

Global minimization algorithm is indispensable to solving the protein folding problem based upon thermodynamic hypothesis. Here we propose a pseudo potential function, contact difference(CD), for simulating empirical contact potential functions and testing global minimization algorithm. The present paper covers conformational sampling and global minimization algorithm called BML03, based upon Monte Carlo and simulated annealing, which is able to locate CD‘s global minimum and refold extended protein structures into one swith root mean square distance(RMSD) as small as 0.03 nm from the native structures. For empirieal contact potential functions, these results demonstrate that their global minimization problems may be solvable.     

A dynamic lattice searching method for fast optimization of Lennard-Jones clusters

A highly efficient unbiased global optimization method called dynamic lattice searching (DLS) was proposed. The method starts with a randomly generated local minimum, and finds better solution by a circulation of construction and searching of the dynamic lattice (DL) until the better solution approaches the best solution. The DL is constructed adaptively based on the starting local minimum by searching the possible location sites for an added atom, and the DL searching is implemented by iteratively moving the atom located at the occupied lattice site with the highest energy to the vacant lattice site with the lowest energy. Because the DL can greatly reduce the searching space and the number of the time-consuming local minimization procedures, the proposed DLS method runs at a very high efficiency, especially for the clusters of larger size. The performance of the DLS is investigated in the optimization of Lennard-Jones (LJ) clusters up to 309 atoms, and the structure of the LJ(500) is also predicted. Furthermore, the idea of dynamic lattice can be easily adopted in the optimization of other molecular or atomic clusters. It may be a promising approach to be universally used for structural optimizations in the chemistry field.     

A comparison of distance geometry and molecular dynamics simulation techniques for conformational analysis of β-cyclodextrin

Distance geometry and molecular dynamics simulation techniques were compared in their ability to search the conformational potential energy surface of β-cyclodextrin. Structures generated by the DISGEO program were minimized using three different atomic point charge sets. Some of these structures were used as starting points for molecular dynamics simulation in vacuo at 298K. The distance geometry results showed that the global features of the conformational potential energy surface were generally independent of the point charge set. The distance geometry technique was able to find structures of lower energy than those obtained by direct minimization of the X-ray or neutron diffraction structures. However, the molecular dynamics simulation technique was consistently able to find structures of lower energy than those generated by distance geometry. Root mean square fit of the trajectory structures to the starting structure showed that the simulation allowed the molecule to explore regions of the potential energy surface in the neighborhood of the starting structure. Both the distance geometry and molecular dynamics simulation techniques showed that β-cyclodextrin can adopt a wide range of conformations in the gas phase and that these conformations are much less symmetrical than the crystalline structure.     

Genetic algorithms: A robust scheme for geometry optimizations and global minimum structure problems

A Genetic Algorithm for Geometry Optimizations (GALGO) program has been developed to study the efficiency of this method of finding global minimum structures. Using a semiempirical tight-binding potential, the behavior of different genetic algorithm (GA) operators has been tested for the linear chain isomer of a C₈ cluster. An optimum set of parameters for the GA operators is proposed for this problem and afterward is used to obtain the global minimum structure of rare-gas atomic clusters of up to 13 atoms using the 12–6 Lennard-Jones interatomic pair potential. © 1995 by John Wiley & Sons, Inc.     

A self-organizing algorithm for molecular alignment and pharmacophore development

We present a method for simultaneous three-dimensional (3D) structure generation and pharmacophore-based alignment using a self-organizing algorithm called Stochastic Proximity Embedding (SPE). Current flexible molecular alignment methods either start from a single low-energy structure for each molecule and tweak bonds or torsion angles, or choose from multiple conformations of each molecule. Methods that generate structures and align them iteratively (e.g., genetic algorithms) are often slow. In earlier work, we used SPE to generate good-quality 3D conformations by iteratively adjusting pairwise distances between atoms based on a set of geometric rules, and showed that it samples conformational space better and runs faster than earlier programs. In this work, we run SPE on the entire ensemble of molecules to be aligned. Additional information about which atoms or groups of atoms in each molecule correspond to points in the pharmacophore can come from an automatically generated hypothesis or be specified manually. We add distance terms to SPE to bring pharmacophore points from different molecules closer in space, and also to line up normal/direction vectors associated with these points. We also permit pharmacophore points to be constrained to lie near external coordinates from a binding site. The aligned 3D molecular structures are nearly correct if the pharmacophore hypothesis is chemically feasible; postprocessing by minimization of suitable distance and energy functions further improves the structures and weeds out infeasible hypotheses. The method can be used to test 3D pharmacophores for a diverse set of active ligands, starting from only a hypothesis about corresponding atoms or groups.     

Conformational search of peptides and proteins: Monte Carlo minimization with an adaptive bias method applied to the heptapeptide deltorphin

The energy function of a protein consists of a tremendous number of minima. Locating the global energy minimum (GEM) structure, which corresponds approximately to the native structure, is a severe problem in global optimization. Recently we have proposed a conformational search technique based on the Monte Carlo minimization (MCM) method of Li and Scheraga, where trial dihedral angles are not selected at random within the range [-180 degrees,180 degrees ] (as with MCM) but with biased probabilities depending on the increased structure-energy correlations as the GEM is approached during the search. This method, called the Monte Carlo minimization with an adaptive bias (MCMAB), was applied initially to the pentapeptide Leu-enkephalin. Here we study its properties further by applying it to the larger peptide with bulky side chains, deltorphin (H-Tyr-D-Met-Phe-His-Leu-Met-Asp-NH(2)). We find that on average the number of energy minimizations required by MCMAB to locate the GEM for the first time is smaller by a factor of approximately three than the number required by MCM-in accord with results obtained for Leu-enkephalin.     

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.     

Do intelligent configuration search techniques outperform random search for large molecules?

We compare three global configuration search methods on a scalable model problem to measure relative performance over a range of molecule sizes. Our model problem is a 2-D polymer composed of atoms connected by rigid rods in which all pairs of atoms interact via Lennard–Jones potentials. The global minimum energy can be calculated analytically. The search methods are all hybrids combining a global sampling algorithm with a local refinement technique. The sampling methods are simulated annealing (SA ), genetic algorithms (GA ), and random search. Each of these uses a conjugate gradient (CG ) routine to perform the local refinement. Both GA and SA perform progressively better relative to random search as the molecule size increases. We also test two other local refinement techniques in addition to CG , coupled to random search as the global method. These are simplex followed by CG and simplex followed by block-truncated Newton. For small problems, the addition of the intermediate simplex step improved the performance of the overall hybrid method. © 1992 John Wiley & Sons, Inc.     

Direct energy functional minimization under orthogonality constraints

The direct energy functional minimization problem in electronic structure theory, where the single-particle orbitals are optimized under the constraint of orthogonality, is explored. We present an orbital transformation based on an efficient expansion of the inverse factorization of the overlap matrix that keeps orbitals orthonormal. The orbital transformation maps the orthogonality constrained energy functional to an approximate unconstrained functional, which is correct to some order in a neighborhood of an orthogonal but approximate solution. A conjugate gradient scheme can then be used to find the ground state orbitals from the minimization of a sequence of transformed unconstrained electronic energy functionals. The technique provides an efficient, robust, and numerically stable approach to direct total energy minimization in first principles electronic structure theory based on tight-binding, Hartree-Fock, or density functional theory. For sparse problems, where both the orbitals and the effective single-particle Hamiltonians have sparse matrix representations, the effort scales linearly with the number of basis functions N in each iteration. For problems where only the overlap and Hamiltonian matrices are sparse the computational cost scales as O(M2N), where M is the number of occupied orbitals. We report a single point density functional energy calculation of a DNA decamer hydrated with 4003 water molecules under periodic boundary conditions. The DNA fragment containing a cis-syn thymine dimer is composed of 634 atoms and the whole system contains a total of 12,661 atoms and 103,333 spherical Gaussian basis functions.     

The many ways to have a quintuple bond

The existence and persistence of five-fold (quintuple) bonding in isomers of model RMMR molecules of quite different geometry are examined theoretically. The molecules studied are RMMR, with R = H, F, Cl, Br, CN, and CH3; M = Cr, Mo, and W. The potential energy surface of these molecules is quite complex, containing two, three, even four local minima. The structural preferences in these molecules are rationalized, and electronic factors responsible for these preferences are elucidated. The linear geometry is always a minimum, but almost never the global minimum; there is a definite preference in RMMR for either a trans-bent conformation or perturbations of the trans-bent isomer with at least one of the R groups in a bridging position about the MM bond. The potential energy surface of these RMMR molecules is relatively flat, the lowest energy conformation being that which for a given molecule attains the best compromise between maximization of the MM bonding and minimization of orbital interactions that are MR antibonding. A surprising low-symmetry C(s) structure is identified, which along with the trans-bent isomer is one of the two most popular choices for the global minimum. Regardless of what isomer of the RMMR molecule is preferred, the MM quintuple bond persists.     

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.     

Coarse-grained force field: general folding theory

We review the coarse-grained UNited RESidue (UNRES) force field for the simulations of protein structure and dynamics, which is being developed in our laboratory over the last several years. UNRES is a physics-based force field, the prototype of which is defined as a potential of mean force of polypeptide chains in water, where all the degrees of freedom except the coordinates of α-carbon atoms and side-chain centers have been integrated out. We describe the initial implementation of UNRES to protein-structure prediction formulated as a search for the global minimum of the potential-energy function and its subsequent molecular dynamics and extensions of molecular-dynamics implementation, which enabled us to study protein-folding pathways and thermodynamics, as well as to reformulate the protein-structure prediction problem as a search for the conformational ensemble with the lowest free energy at temperatures below the folding-transition temperature. Applications of UNRES to study biological problems are also described.     

Global energy minimization by rotational energy embedding

Given a sufficiently good empirical potential function for the internal energy of molecules, prediction of the preferred conformations is nearly impossible for large molecules because of the enormous number of local energy minima. Energy embedding has been a promising method for locating extremely good local minima, if not always the global minimum. The algorithm starts by locating a very good local minimum when the molecule is in a high-dimensional Euclidean space, and then it gradually projects down to three dimensions while allowing the molecule to relax its energy throughout the process. Now we present a variation on the method, called rotational energy embedding, where the descent into three dimensions is carried out by a sequence of internal rotations that are the multidimensional generalization of varying torsion angles in three dimensions. The new method avoids certain kinds of difficulties experienced by ordinary energy embedding and enables us to locate conformations very near the native for avian pancreatic polypeptide and apamin, given only their amino acid sequences and a suitable potential function.