Conformational searching methods for small molecules. II. Genetic algorithm approach

We demonstrate the use of a genetic algorithm (GA) search procedure for finding low-energy conformations of small to medium organic molecules (1–12 rotatable bonds). GAS are in a class of biologically motivated optimization methods that evolve a population of individuals where individuals who are more “fit” have a higher probability of surviving into subsequent generations. Here, an individual is a conformation of a given molecule and the fitness is the molecule's conformational energy. In the course of a simulated evolution, the population produces conformations having increasingly lower energy. We test the GA method on a suite of 72 molecules and compare the performance against the CSEARCH algorithm in Sybyl. For molecules with more than eight rotatable bonds, the GA method is more efficient computationally and as the number of rotatable bonds increases the relative efficiency of the GA method grows. The GA method also found energies equal to or lower than the energy of the relaxed crystal structure in the large majority of cases. © John Wiley & Sons, Inc.     

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.     

An exploration of a novel strategy for superposing several flexible molecules

Summary This paper describes a computational strategy for the superposition of a set of flexible molecules. The combinatorial problems of searching conformational space and molecular matching are reduced drastically by the combined use of simulated annealing methods and cluster analysis. For each molecule, the global minimum of the conformational energy is determined by annealing and the search trajectory is retained in a history file. All the significantly different low-energy conformations are extracted by cluster analysis of data in the history file. Each pair of molecules, in each of their significantly different conformations, is then matched by simulated annealing, using the difference-distance matrix as the objective function. A set of match statistics is then obtained, from which the best match taken from all different conformations can be found. The molecules are then superposed either by reference to a base molecule or by a consensus method. This strategy ensures that as wide a range of conformations as possible is considered, but at the same time that the smallest number of significantly different conformations is used. The method has been tested on a set of six angiotensin II antagonists with between 7–11 rotatable bonds.     

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.     

Tork: Conformational analysis method for molecules and complexes

A conformational search method for organic molecules and bimolecular complexes is presented. The method, termed Tork, uses normal-mode analysis in bond-angle-torsion coordinates and focuses on a key subset of torsional coordinates to identify natural molecular motions that lead the initial conformation to new energy minima. New conformations are generated via distortion along these modes and their pairwise combinations, followed by energy minimization. For complexes, special treatment is accorded to the six coordinates that specify the position and orientation of one molecule relative to the other. Tests described here show that Tork is highly efficient for cyclic, acyclic, and mixed single molecules, as well as for host-guest complexes.     

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.     

Toward a computational tool predicting the stereochemical outcome of asymmetric reactions: development of the molecular mechanics-based program ACE and application to asymmetric epoxidation reactions

The development and application of ACE, a program that predicts the stereochemical outcome of asymmetric reactions is presented. As major implementations, ACE includes a genetic algorithm to carry out an efficient global conformational search combined with a conjugate gradient minimization routine for local optimization and a corner flap algorithm to search ring conformations. Further improvements have been made that enable ACE to generate Boltzmann populations of conformations, to investigate highly asynchronous reactions, to compute fluctuating partial atomic charges and solvation energy and to automatically construct reactants and products from libraries of catalysts and substrates. Validation on previously investigated reactions (asymmetric Diels Alder cycloadditions and organocatalyzed aldol reactions) followed by application to a number of alkene epoxidation reactions and a comparative study of DFT-derived and ACE-derived predictions demonstrate the accuracy and usefulness of ACE in the context of asymmetric catalyst design.     

Determination of the major solution conformation of tyrocidine A,using molecular mechanics energy minimization and NMR-derived distance and torsion angle constraints

Molecular mechanics energy calculations coupled with nuclear magnetic resonance-determined distance and torsion angle constraints have been used to determine the three-dimensional structure of tyrocidine A, a cyclic decapeptide which exists largely as a single conformation in solution. Two open-chain polyalanine models were used to represent separate halves of the peptide backbone and a combinatorial method of searching conformation space used to generate candidate structures consistent with experimental distance constraints. These structures were energy-minimized using the AMBER molecular mechanics forcefield and the resulting conformations classified by factor analysis of their Cartesian coordinates. Representative low-energy conformers of the two halves of the backbone were fused together and two candidate conformations of the completed backbone refined by further minimization using both distance and torsional constraints. Side chains were then added as their experimentally preferred rotamers and the whole molecule minimized without constraints to give the final model structure. This shows type II' and III ß turns at residues 4–5 and 9–10, respectively, coupled by twisted antiparallel strands which show hydrogen bonds between all four pairs of opposing peptide groups. The backbone conformation of residues 2–6 closely resembles that found in the crystal structure of gramicidin S.     

A genetic algorithm encoded with the structural information of amino acids and dipeptides for efficient conformational searches of oligopeptides

The genetic algorithm (GA) is an intelligent approach for finding minima in a highly dimensional parametric space. However, the success of GA searches for low energy conformations of biomolecules is rather limited so far. Herein an improved GA scheme is proposed for the conformational search of oligopeptides. A systematic analysis of the backbone dihedral angles of conformations of amino acids (AAs) and dipeptides is performed. The structural information is used to design a new encoding scheme to improve the efficiency of GA search. Local geometry optimizations based on the energy calculations by the density functional theory are employed to safeguard the quality and reliability of the GA structures. The GA scheme is applied to the conformational searches of Lys, Arg, Met‐Gly, Lys‐Gly, and Phe‐Gly‐Gly representative of AAs, dipeptides, and tripeptides with complicated side chains. Comparison with the best literature results shows that the new GA method is both highly efficient and reliable by providing the most complete set of the low energy conformations. Moreover, the computational cost of the GA method increases only moderately with the complexity of the molecule. The GA scheme is valuable for the study of the conformations and properties of oligopeptides. © 2016 Wiley Periodicals, Inc.     

Revised algorithms for the build-up procedure for predicting protein conformations by energy minimization

The build-up procedure for predicting low-energy conformations of polypeptides has been extended to cover the case of peptides in aqueous solutions. The revised procedure consists of five steps to be applied to each stage of the build-up. I. All low-energy minima of each of the two fragments to be joined are combined as starting points for energy minimization of the enlarged fragment, and those minima of the enlarged fragment within a certain upper bound of the lowest energy are retained. II. Whenever one of the combinations in Step I leads to an atomic overlap, the minimization is started again using a pseudoenergy function which remains finite everywhere and becomes equal to the standard energy function when no atoms overlap. III. The minima generated in Steps I and II are culled by ignoring side-chain conformations and retaining only those minima whose backbone conformations differ significantly. IV. The rotameric states of the side chains are optimized, by testing their energy of interaction with the rest of the molecule, and subjecting the whole molecule to a further round of energy minimization if the test indicates that this would reduce the energy. V. The energies of all minima are recomputed with inclusion of a term for solvation and with a smaller upper bound as the criterion for retention. The original build-up procedure consisted of Steps I and III only. Examples are presented showing the effectiveness of the new Steps II and IV in locating low-energy minima, and the problems that remain to be solved, chiefly concerning Step V, are discussed.     

The energy well connection graph: a use of curvilinear coordinates to achieve dimension reduction for graph representation of molecular conformation energy data

In the conformation space of a flexible molecule, curvilinear coordinate paths connecting conformations of segments of the given molecule are used to reduce the number of variables required for describing barriers between preferred conformations of the molecule as a whole. The technique is applied to a hypothetical example, then to m-trinuoromethyl-N-ethyl-amphetamine (fenfluramine), and to N-methyl-3-phenyl-3-(o-methoxyphenoxy)-propylamine (nisoxetine). In the latter example, the number of variables is thus reduced from six to three. In all three examples, a graph representation of low-energy well connection is achieved. The limit of easy comprehension has thus been moved back from about three torsion angles to three effective segments. Within this limit the procedure leads to a quantitative diagram, which is no harder to read than a contour map, showing the barriers to low-energy interconnection among the favorable conformations of a moderately complex molecule.     

Docking flexible molecules: A case study of three proteins

A genetic algorithm (GA) conformation search method is used to dock a series of flexible molecules into one of three proteins. The proteins examined are thermolysin (tmn), carboxypeptidase A (cpa), and dihydrofolate reductase (dfr). In the latter two proteins, the crystal ligand was redocked. For thermolysin, we docked eight ligands into a protein conformation derived from a single crystal structure. The bound conformations of the other ligands in tmn are known. In the cpa and dfr cases, and in seven of the eight tmn ligands, the GA docking method found conformations within 1.6 Å root mean square (rms) of the relaxed crystal conformation. © 1995 John Wiley & Sons, Inc.     

Molecular mechanics conformational analysis of tylosin

The conformations of the 16-membered macrolide antibiotic tylosin were studied with molecular mechanics (AMBER* force field) including modelling of the effect of the solvent on the conformational preferences (GB/SA). A Monte Carlo conformational search procedure was used for finding the most probable low-energy conformations. The present study provides complementary data to recently reported analysis of the conformations of tylosin based on NMR techniques. A search for the low-energy conformations of protynolide, a 16-membered lactone containing the same aglycone as tylosin, was also carried out, and the results were compared with the observed conformation in the crystal as well as with the most probable conformations of the macrocyclic ring of tylosin. The dependence of the results on force field was also studied by utilizing the MM3 force field. Some particular conformations were computed with the semiempirical molecular orbital methods AM1 and PM3.     

A robust force field based method for calculating conformational energies of charged drug-like molecules

The binding affinity of a drug-like molecule depends among other things on the availability of the bioactive conformation. If the bioactive conformation has a significantly higher energy than the global minimum energy conformation, then the molecule is unlikely to bind to its target. Determination of the global minimum energy conformation and calculation of conformational penalties of binding is a prerequisite for prediction of reliable binding affinities. Here, we present a simple and computationally efficient procedure to estimate the global energy minimum for a wide variety of structurally diverse molecules, including polar and charged compounds. Identifying global energy minimum conformations of such compounds with force field methods is problematic due to the exaggeration of intramolecular electrostatic interactions. We demonstrate that the global energy minimum conformations of zwitterionic compounds generated by conformational analysis with modified electrostatics are good approximations of the conformational distributions predicted by experimental data and with molecular dynamics performed in explicit solvent. Finally the method is used to calculate conformational penalties for zwitterionic GluA2 agonists and to filter false positives from a docking study.     

Molecular mechanics conformational analysis of cyclononane using the RIPS method and comparison with quantum-mechanical calculations

The recently reported Random Incremental Pulse Search (RIPS) technique has been used to probe the conformational energy surface of cyclononane. The stochastic method permits searching of the potential energy surface for all minimum-energy conformations. The search located all previously reported structures together with three additional conformations that were not found by earlier, primitive searching techniques. Two of these structures are high-nergy skew forms, and the third is a low-energy conformer that should contribute significantly to the overall equilibrium set of cyclononane conformations. The global minimum has been found to be the D₃ symmetrical twist chair-boat (TBC) form in accordance with previous studies. The newly discovered low-energy structure, which lies only 2.2 kcal/mol above the global minimum, has been designated twist chair-twist chair (TCTC). The two higher energy conformers are skewed chair-chair (SCC) and skewed boat-boat (SBB) forms that are 5.7 kcal/mol and 10.4 kcal/mol above the global minimum, respectively. The seven reported conformations were reanalyzed quantum mechanically (AM 1), and a comparison between MM 2 and AM 1 results is presented.     

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.     

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     

Sequence-structure relationships in DNA oligomers: a computational approach

A collective-variable model for DNA structure is used to predict the conformation of a set of 30 octamer, decamer, and dodecamer oligomers for which high-resolution crystal structures are available. The model combines an all-atom base pair representation with an empirical backbone, emphasizing the role of base stacking in fixing sequence-dependent structure. We are able to reproduce trends in roll and twist to within 5 degrees across a large database of both A- and B-DNA oligomers. A genetic algorithm approach is used to search for global minimum structures and this is augmented by a grid search to identify local minimums. We find that the number of local minimums is highly sequence dependent, with certain sequences having a set of minimums that span the entire range between canonical A- and B-DNA conformations. Although the global minimum does not always agree with the crystal structure, for 24 of the 30 oligomers, we find low-energy local minimums that match the experimental step parameters. Discrepancies throw some light on the role of crystal packing in determining the solid-state conformation of double-helical DNA.     

A fast new approach to pharmacophore mapping and its application to dopaminergic and benzodiazepine agonists

Summary In the absence of a 3D structure of the target biomolecule, to propose the 3D requirements for a small molecule to exhibit a particular bioactivity, one must supply both a bioactive conformation and a superposition rule for every active compound. Our strategy identifies both simultaneously. We first generate and optimize all low-energy conformations by any suitable method. For each conformation we then use ALAD-DIN to calculate the location of points to be considered as part of the superposition. These points include atoms in the molecule and projections from the molecule to hydrogen-bond donors and acceptors or charged groups in the binding site. These positions and the relative energy of each conformation are the input to our new program DISCO. It uses a clique-detection method to find superpositions that contain a least one conformation of each molecule and user-specified numbers of point types and chirality. DISCO is fast; for example, it takes about 1 min CPU to propose pharmacophores from 21 conformations of seven molecules. We typically run DISCO several times to compare alternative pharmacophore maps. For D₂ dopamine agonists DISCO shows that the newer 2-aminothiazoles fit the traditional pharmacophore. Using site points correctly identifies the bioactive enantiomers of indoles to compare with catechols whereas using only ligand points leads to selecting the inactive enantiomer for the pharmacophore map. In addition, DISCO reproduces pharmacophore maps of benzodiazepines in the literature and proposes subtle improvements. Our experience suggests that clique-detection methods will find many applications in computational chemistry and computer-assisted molecular design.     

Prodock: Software package for protein modeling and docking

A new software package, Prodock , for protein modeling and flexible docking is presented. The protein system is described in internal coordinates with an arbitrary level of flexiblity for the proteins or ligands. The protein is represented by an all-atom model with the Ecepp /3 or Amber IV force field, depending on whether the ligand is a peptidic molecule or not. Prodock is based on a new residue data dictionary that makes the programming easier and the definition of molecular flexibility more straigthforward. Two versions of the dictionary have been constructed for the Ecepp /3 and Amber IV geometry, respectively. The global optimization of the energy function is carried out with the scaled collective variable Monte Carlo method plus energy minimization. The incorporation of a local minimization during the conformational sampling has been shown to be very important for distinguishing low-energy nonnative conformations from native structures. To make the Monte Carlo minimization method efficient for docking, a new grid-based energy evaluation technique using Bezier splines has been incorporated. This article includes some techniques and simulation tools that significantly improve the efficiency of flexible docking simulations, in particular forward/backward polypeptide chain generation. A comparative study to illustrate the advantage of using quaternions over Euler angles for the rigid-body rotational variables is presented in this paper. Several applications of the program Prodock are also discussed. ©1999 John Wiley & Sons, Inc. J Comput Chem 20: 412–427, 1999