Stochastic molecular optimization using generalized simulated annealing

We propose a stochastic optimization technique based on a generalized simulated annealing (GSA) method for mapping minima points of molecular conformational energy surfaces. The energy maps are obtained by coupling a classical molecular force field (THOR package) with a GSA procedure. Unlike the usual molecular dynamics (MD) method, the method proposed in this study is force independent; that is, we obtain the optimized conformation without calculating the force, and only potential energy is involved. Therefore, we do not need to know the conformational energy gradient to arrive at equilibrium conformations. Its utility in molecular mechanics is illustrated by applying it to examples of simple molecules (H₂O and H₂O₃) and to polypeptides. The results obtained for H₂O and H₂O₃ using Tsallis thermostatistics suggest that the GSA approach is faster than the other two conventional methods (Boltzmann and Cauchy machines). The results for polypeptides show that pentalanine does not form a stable α-helix structure, probably because the number of hydrogen bonds is insufficient to maintain the helical array. On the contrary, the icoalanine molecule forms an α-helix structure. We obtain this structure simulating all Φ, Ψ pairs using only a few steps, as compared with conventional methods. © 1998 John Wiley & Sons, Inc. J Comput Chem 19: 647–657, 1998     

A fast annealing evolutionary algorithm for global optimization

By combining the aspect of population in genetic algorithms (GAs) and the simulated annealing algorithm (SAA), a novel algorithm, called fast annealing evolutionary algorithm (FAEA), is proposed. The algorithm is similar to the annealing evolutionary algorithm (AEA), and a very fast annealing technique is adopted for the annealing procedure. By an application of the algorithm to the optimization of test functions and a comparison of the algorithm with other stochastic optimization methods, it is shown that the algorithm is a highly efficient optimization method. It was also applied in optimization of Lennard-Jones clusters and compared with other methods in this study. The results indicate that the algorithm is a good tool for the energy minimization problem.     

Protein structure predictions by parallel simulated annealing molecular dynamics using genetic crossover

We propose a conformational search method to find a global minimum energy structure for protein systems. The simulated annealing is a powerful method for local conformational search. On the other hand, the genetic crossover can search the global conformational space. Our method incorporates these attractive features of the simulated annealing and genetic crossover. In the previous works, we have been using the Monte Carlo algorithm for simulated annealing. In the present work, we use the molecular dynamics algorithm instead. To examine the effectiveness of our method, we compared our results with those of the normal simulated annealing molecular dynamics simulations by using an α-helical miniprotein. We used genetic two-point crossover here. The conformations, which have lower energy than those obtained from the conventional simulated annealing, were obtained.     

Global optimization of atomic and molecular clusters using the space-fixed modified genetic algorithm method

A modified genetic algorithm approach has been applied to atomic Ar clusters and molecular water clusters up to (H₂O)₁₃. Several genetic operators are discussed which are suitable for real-valued space-fixed atomic coordinates and Euler angles. The performance of these operators has been systematically investigated. For atomic systems, it is found that a mix of operators containing a coordinate-averaging operator is optimal. For angular coordinates, the situation is less clear. It appears that inversion and two-point crossover operators are the best choice. © 1997 John Wiley & Sons, Inc. J Comput Chem 18: 1233–1244     

A genetic algorithm for flexible molecular overlay and pharmacophore elucidation

Summary A genetic algorithm (GA) has been developed for the superimposition of sets of flexible molecules. Molecules are represented by a chromosome that encodes angles of rotation about flexible bonds and mappings between hydrogen-bond donor proton, acceptor lone pair and ring centre features in pairs of molecules. The molecule with the smallest number of features in the data set is used as a template, onto which the remaining molecules are fitted with the objective of maximising structural equivalences. The fitness function of the GA is a weighted combination of: (i) the number and the similarity of the features that have been overlaid in this way; (ii) the volume integral of the overlay; and (iii) the van der Waals energy of the molecular conformations defined by the torsion angles encoded in the chromosomes. The algorithm has been applied to a number of pharmacophore elucidation problems, i.e., angiotensin II receptor antagonists, Leu-enkephalin and a hybrid morphine molecule, 5-HT_1D agonists, benzodiazepine receptor ligands, 5-HT₃ antagonists, dopamine D₂ antagonists, dopamine reuptake blockers and FKBP12 ligands. The resulting pharmacophores are generated rapidly and are in good agreement with those derived from alternative means.     

Standing wave optimization of SMB using a hybrid simulated annealing and genetic algorithm (SAGA)

In this paper we draw on two stochastic optimization techniques, Simulated Annealing and Genetic Algorithm (SAGA), to create a hybrid to determine the optimal design of nonlinear Simulated Moving Bed (SMB) systems. A mathematical programming model based on the Standing Wave Design (SWD) offers a significant advantage in optimizing SMB systems. SAGA builds upon the strength of SA and GA to optimize the 16 variables of the mixed-integer nonlinear programming model for single- and multi-objective optimizations. The SAGA procedure is shown to be robust with computational time in minutes for single-objective optimization and in a few hours for a multi-objective optimization, which is comprised of more than one hundred points.     

A geometry optimization benchmark using highly correlated wavefunctions (FCI and MRD-CI)

Summary Full configuration interaction (FCI) geometry optimizations have been performed for the X³B₁, a¹A₁, b¹B₁ and c¹A₁ electronic states of CH₂, the X²B₁ and A²A₁ electronic states of NH₂ and the X¹A₁ electronic state of BH₃ using a DZP basis set. The results are compared with those obtained using the MRD-CI method at different levels of theoretical treatment. The agreement between the geometrical parameters optimized with the FCI and MRD-CI methods is very good.     

Geometry optimizations of benzene clusters using a modified genetic algorithm

A modified genetic algorithm with real-number coding, non-uniform mutation and arithmetical crossover operators was described in this paper. A local minimization was used to improve the final solution obtained by the genetic algorithm. Using the exp-6-1 interatomic energy function, the modified genetic algorithm with local minimization (MGALM) was applied to the geometry optimization problem of small benzene clusters (C6H6)N(N = 2-7) to obtain the global minimum energy structures. MGALM is simple but the structures optimized are comparable to the published results obtained by parallel genetic algorithms.     

Cofolga: a genetic algorithm for finding the common folding of two RNAs

In order to predict non-coding RNA genes and functions on the basis of genome sequences, accurate secondary structure prediction is useful. Although single-sequence folding programs such as mfold have been successful, it is of great importance to develop a novel approach for further improvement of the prediction performance. In the present paper, a secondary structure prediction method based on genetic algorithm, Cofolga, is proposed. The program developed performs folding and alignment of two homologous RNAs simultaneously. Cofolga was tested with a dataset composed of 13 tRNAs, seven 5S rRNAs, five RNase P RNAs, and five SRP RNAs; as a result, it turned out that the average prediction accuracies for the tRNAs, 5S rRNAs, RNase P RNAs, and SRP RNAs obtained by Cofolga with an optimal weight factor and default parameters were 83.6, 81.8, 73.5, and 67.7%, respectively. These results were superior to those obtained by a single-sequence folding based on free-energy minimization in which corresponding average prediction accuracies were 52.4, 47.4, 57.7, and 52.3%, respectively. Cofolga has a post-processing in which a single-sequence folding is performed after fixation of a predicted common structure; this post-processing enables Cofolga to predict a structure that is present in one of two RNAs alone. The executable files of Cofolga (for Windows/Unix/Mac) can be obtained by an e-mail request.     

Development and optimization of a novel genetic algorithm for identifying nanoclusters from scanning transmission electron microscopy images

Whilst technological advancements have allowed imaging at atomic resolution using scanning transmission electron microscopy (STEM), identification of nanocluster structures has proven difficult due to their low thermal stability, and often resultant low-symmetry. In this work, we look at a novel solution to this problem using a genetic algorithm (GA). GAs are search methods for the minimization of statistical problems based on natural evolution. We develop a STEM model first described by Curley et al. (2007) and, using high-symmetry cluster structures as test subjects, look at the effectiveness and efficiency of the GA at optimizing orientation parameters for a cluster when compared to a model solution. We find for a 309-atom icosahedron that a random minimizing search would prove more efficient than a GA; however, for a 309-atom decahedron the GA becomes more effective and efficient than a random search. We predict that as we continue to lower symmetry of our test cases, we will find the GA becomes even more efficient at optimizing this otherwise computationally expensive problem.     

Structure and spectroscopy of water-fluoride microclusters: a combined genetic algorithm and DFT-based study

In this article, we explore the efficiency of using a coupled genetic algorithm (GA) and density functional theory (DFT) based strategy to evaluate probable structures of (H(2) O)(n) F(-) micro-clusters, with n = 1 - 6. We use the stochastic optimization technique of GA to arrive at structures of the cluster systems and once the structures are obtained, do a DFT calculation with the optimized coordinates from the GA calculation as input to get the infra-red spectrum of all the systems. The results of our work closely resembles the pure quantum chemical results obtained by Baik et al. (J Chem Phys 1999, 110, 9116-9127).     

A heuristic and parallel simulated annealing algorithm for variable selection in near‐infrared spectroscopy analysis

A new heuristic and parallel simulated annealing algorithm was proposed for variable selection in near‐infrared spectroscopy analysis. The algorithm employs a parallel mechanism to enhance the search efficiency, a heuristic mechanism to generate high‐quality candidate solutions, and the concept of Metropolis criterion to estimate accuracy of the candidate solutions. Several near‐infrared datasets have been evaluated under the proposed new algorithm, with partial least squares leading to improved analytical figures of merit upon wavelength selection. Improved robust and predictive regression models were obtained by the new algorithm. The method could also be helpful in other chemometric activities such as classification or quantitative structure‐activity relationship problems.     

Optimization of bimetallic Cu–Au and Ag–Au clusters by using a modified adaptive immune optimization algorithm

A modified adaptive immune optimization algorithm (AIOA) is designed for optimization of Cu–Au and Ag–Au bimetallic clusters with Gupta potential. Compared with homoatom clusters, there are homotopic isomers in bimetallic cluster, so atom exchange operation is presented in the modified AIOA. The efficiency of the algorithm is tested by optimization of Cu_nAu_38‐n (0 ≤ n ≤ 38). Results show that all the structures with the putative global minimal energies are successfully located. In the optimization of Ag_nAu_55‐n (0 ≤ n ≤ 55) bimetallic clusters, all the structures with the reported minimal energies are obtained, and 36 structures with even lower potential energies are found. On the other hand, with the optimized structures of Cu_nAu_55‐n, it is shown that all 55‐atom Cu–Au bimetallic clusters are Mackay icosahedra except for Au₅₅, which is a face‐centered cubic (fcc)‐like structure; Cu₅₅, Cu₁₂Au₄₃, and Cu₁Au₅₄ have two‐shell Mackay icosahedral geometries with I_h point group symmetry. © 2009 Wiley Periodicals, Inc. J Comput Chem 2009     

Reference energy extremal optimization: a stochastic search algorithm applied to computational protein design

We adapt a combinatorial optimization algorithm, extremal optimization (EO), for the search problem in computational protein design. This algorithm takes advantage of the knowledge of local energy information and systematically improves on the residues that have high local energies. Power-law probability distributions are used to select the backbone sites to be improved on and the rotamer choices to be changed to. We compare this method with simulated annealing (SA) and motivate and present an improved method, which we call reference energy extremal optimization (REEO). REEO uses reference energies to convert a problem with a structured local-energy profile to one with more random profile, and extremal optimization proves to be extremely efficient for the latter problem. We show in detail the large improvement we have achieved using REEO as compared to simulated annealing and discuss a number of other heuristics we have attempted to date.     

Evaluation of a method for controlling molecular scaffold diversity in de novo ligand design

We describe an algorithm for the automated generation of molecular structures subject to geometric and connectivity constraints. The method relies on simulated annealing and simplex optimization of a penalty function that contains a variety of conditions and can be useful in structure-based drug design projects. The procedure controls the diversity and complexity of the generated molecules. Structure selection filters are an integral part and drive the algorithm. Several procedures have been developed to achieve reliable control. A number of template sets can be defined and combined to control the range of molecules which are searched. Ring systems are predefined. Normally, the ring-system complexity is one of the most elusive and difficult factors to control when fusion-, bridge- and spiro-structures are built by joining templates. Here this is not an issue; the decision about which systems are acceptable, and which are not, is made before the run is initiated. Queries for inclusion and exclusion spheres are incorporated into the objective function, and, by using a flexible notation, the structure generation can be directed and more focused. Simulated annealing is a reliable optimizer and converges asymptotically to the global minimum. The objective functions used here are degenerate, so it is likely that each run will produce a different set of good solutions.     

A novel conformation optimization model and algorithm for structure-based drug design

In this paper, we present a multi-scale optimization model and an entropy-based genetic algorithm for molecular docking. In this model, we introduce to the refined docking design a concept of residue groups based on induced-fit and adopt a combination of conformations in different scales. A new iteration scheme, in conjunction with multi-population evolution strategy, entropy-based searching technique with narrowing down space and the quasi-exact penalty function, is developed to address the optimization problem for molecular docking. A new docking program that accounts for protein flexibility has also been developed. The docking results indicate that the method can be efficiently employed in structure-based drug design.     

New optimization method for conformational energy calculations on polypeptides: Conformational space annealing

A new optimization method is presented to search for the global minimum-energy conformations of polypeptides. The method combines essential aspects of the build-up procedure and the genetic algorithm, and it introduces the important concept of “conformational space annealing.” Instead of considering a single conformation, attention is focused on a population of conformations while new conformations are obtained by modifying a “seed conformation.” The annealing is carried out by introducing a distance cutoff, D_cut, which is defined in the conformational space; D_cut effectively divides the whole conformational space of local minima into subdivisions. The value of D_cut is set to a large number at the beginning of the algorithm to cover the whole conformational space, and annealing is achieved by slowly reducing it. Many distinct local minima designed to be distributed as far apart as possible in conformational space are investigated simultaneously. Therefore, the new method finds not only the global minimum-energy conformation but also many other distinct local minima as by-products. The method is tested on Met-enkephalin, a 24-dihedral angle problem. For all 100 independent runs, the accepted global minimum-energy conformation was obtained after about 2600 minimizations on average. © 1997 John Wiley & Sons, Inc. J Comput Chem 18: 1222–1232     

Topological study of a hypothetical molecular sieve MCR-16 with extra-large open pores

The topology of the framework of a novel zeolite, named MCR-16, with cylindrical channels spanned by the 16-membered ring, is constructed, in which the sigma transformation is a conceptual device for inter-relating the known zeolite mordenite and the hypothetical MCR-16. The consistent molecular mechanics force field is used as the foundation for the discussion on the steric energy of the structure. The configuration energy is minimized by the simulated annealing method. The consequent Si–O, Si–Si and O–O distances and Si–O–Si and O–Si–O angles of the designed MCR-16 structure are all within the limits of the reasonable ranges.     

Continuous optimization methods for ground-state searches of spin clusters

Computational methods were developed for ground-state searches of Heisenberg model spin clusters in which spin sites were represented by classical spin vectors. Simulated annealing, continuous genetic algorithm, and particle swarm optimization methods were applied for solving the problems. Because the results of these calculations were influenced by the settings of optimization parameters, effective parameter settings were also investigated. The results indicated that a continuous genetic algorithm is the most effective method for ground-state searches of Heisenberg model spin clusters, and that a mutation operator plays an important role in this genetic algorithm. These results provide useful information for solving physically or chemically important continuous optimization problems.