A genetic algorithm for structure-based de novo design

Genetic algorithms have properties which make them attractive in de novo drug design. Like other de novo design programs, genetic algorithms require a method to reduce the enormous search space of possible compounds. Most often this is done using information from known ligands. We have developed the ADAPT program, a genetic algorithm which uses molecular interactions evaluated with docking calculations as a fitness function to reduce the search space. ADAPT does not require information about known ligands. The program takes an initial set of compounds and iteratively builds new compounds based on the fitness scores of the previous set of compounds. We describe the particulars of the ADAPT algorithm and its application to three well-studied target systems. We also show that the strategies of enhanced local sampling and re-introducing diversity to the compound population during the design cycle provide better results than conventional genetic algorithm protocols.     

Protein structure prediction from inaccurate and sparse NMR data using an enhanced genetic algorithm

Nuclear Magnetic Resonance Spectroscopy (most commonly known as NMR Spectroscopy) is used to generate approximate and partial distances between pairs of atoms of the native structure of a protein. To predict protein structure from these partial distances by solving the Euclidean distance geometry problem from the partial distances obtained from NMR Spectroscopy, we can predict three-dimensional (3D) structure of a protein. In this paper, a new genetic algorithm is proposed to efficiently address the Euclidean distance geometry problem towards building 3D structure of a given protein applying NMR's sparse data. Our genetic algorithm uses (i) a greedy mutation and crossover operator to intensify the search; (ii) a twin removal technique for diversification in the population; (iii) a random restart method to recover from stagnation; and (iv) a compaction factor to reduce the search space. Reducing the search space drastically, our approach improves the quality of the search. We tested our algorithms on a set of standard benchmarks. Experimentally, we show that our enhanced genetic algorithms significantly outperforms the traditional genetic algorithms and a previously proposed state-of-the-art method. Our method is capable of producing structures that are very close to the native structures and hence, the experimental biologists could adopt it to determine more accurate protein structures from NMR data.     

Assessing search strategies for flexible docking

We assess the efficiency of molecular dynamics (MD), Monte Carlo (MC), and genetic algorithms (GA) for docking five representative ligand–receptor complexes. All three algorithms employ a modified CHARMM-based energy function. The algorithms are also compared with an established docking algorithm, AutoDock. The receptors are kept rigid while flexibility of ligands is permitted. To test the efficiency of the algorithms, two search spaces are used: an 11-Å-radius sphere and a 2.5-Å-radius sphere, both centered on the active site. We find MD is most efficient in the case of the large search space, and GA outperforms the other methods in the small search space. We also find that MD provides structures that are, on average, lower in energy and closer to the crystallographic conformation. The GA obtains good solutions over the course of the fewest energy evaluations. However, due to the nature of the nonbonded interaction calculations, the GA requires the longest time for a single energy evaluation, which results in a decreased efficiency. The GA and MC search algorithms are implemented in the CHARMM macromolecular package. © 1998 John Wiley & Sons, Inc. J Comput Chem 19: 1623–1631, 1998     

SASS: a symmetry adapted stochastic search algorithm exploiting site symmetry

A simple symmetry adapted search algorithm (SASS) exploiting point group symmetry increases the efficiency of systematic explorations of complex quantum mechanical potential energy surfaces. In contrast to previously described stochastic approaches, which do not employ symmetry, candidate structures are generated within simple point groups, such as C2, Cs, and C2v. This facilitates efficient sampling of the 3N-6 Pople's dimensional configuration space and increases the speed and effectiveness of quantum chemical geometry optimizations. Pople's concept of framework groups [J. Am. Chem. Soc. 102, 4615 (1980)] is used to partition the configuration space into structures spanning all possible distributions of sets of symmetry equivalent atoms. This provides an efficient means of computing all structures of a given symmetry with minimum redundancy. This approach also is advantageous for generating initial structures for global optimizations via genetic algorithm and other stochastic global search techniques. Application of the SASS method is illustrated by locating 14 low-lying stationary points on the cc-pwCVDZ ROCCSD(T) potential energy surface of Li5H2. The global minimum structure is identified, along with many unique, nonintuitive, energetically favorable isomers.     

A parameter-free, solid-angle based, nearest-neighbor algorithm

We propose a parameter-free algorithm for the identification of nearest neighbors. The algorithm is very easy to use and has a number of advantages over existing algorithms to identify nearest-neighbors. This solid-angle based nearest-neighbor algorithm (SANN) attributes to each possible neighbor a solid angle and determines the cutoff radius by the requirement that the sum of the solid angles is 4π. The algorithm can be used to analyze 3D images, both from experiments as well as theory, and as the algorithm has a low computational cost, it can also be used "on the fly" in simulations. In this paper, we describe the SANN algorithm, discuss its properties, and compare it to both a fixed-distance cutoff algorithm and to a Voronoi construction by analyzing its behavior in bulk phases of systems of carbon atoms, Lennard-Jones particles and hard spheres as well as in Lennard-Jones systems with liquid-crystal and liquid-vapor interfaces.     

Protein-protein binding site prediction by local structural alignment

Generalization of an earlier algorithm has led to the development of new local structural alignment algorithms for prediction of protein-protein binding sites. The algorithms use maximum cliques on protein graphs to define structurally similar protein regions. The search for structural neighbors in the new algorithms has been extended to all the proteins in the PDB and the query protein is compared to more than 60,000 proteins or over 300,000 single-chain structures. The resulting structural similarities are combined and used to predict the protein binding sites. This study shows that the location of protein binding sites can be predicted by comparing only local structural similarities irrespective of general protein folds.     

SymDex: Increasing the Efficiency of Chemical Fingerprint Similarity Searches for Comparing Large Chemical Libraries by Using Query Set Indexing

The large sizes of today's chemical databases require efficient algorithms to perform similarity searches. It can be very time consuming to compare two large chemical databases. This paper seeks to build upon existing research efforts by describing a novel strategy for accelerating existing search algorithms for comparing large chemical collections. The quest for efficiency has focused on developing better indexing algorithms by creating heuristics for searching individual chemical against a chemical library by detecting and eliminating needless similarity calculations. For comparing two chemical collections, these algorithms simply execute searches for each chemical in the query set sequentially. The strategy presented in this paper achieves a speedup upon these algorithms by indexing the set of all query chemicals so redundant calculations that arise in the case of sequential searches are eliminated. We implement this novel algorithm by developing a similarity search program called Symmetric inDexing or SymDex. SymDex shows over a 232% maximum speedup compared to the state-of-the-art single query search algorithm over real data for various fingerprint lengths. Considerable speedup is even seen for batch searches where query set sizes are relatively small compared to typical database sizes. To the best of our knowledge, SymDex is the first search algorithm designed specifically for comparing chemical libraries. It can be adapted to most, if not all, existing indexing algorithms and shows potential for accelerating future similarity search algorithms for comparing chemical databases.     

Predicting patchy particle crystals: variable box shape simulations and evolutionary algorithms

We consider several patchy particle models that have been proposed in literature and we investigate their candidate crystal structures in a systematic way. We compare two different algorithms for predicting crystal structures: (i) an approach based on Monte Carlo simulations in the isobaric-isothermal ensemble and (ii) an optimization technique based on ideas of evolutionary algorithms. We show that the two methods are equally successful and provide consistent results on crystalline phases of patchy particle systems.     

Engineering microporous architectures: combining evolutionary algorithms with predefined exclusion zones

A global optimisation technique, based on the principles of evolution, has been refined for the prediction of plausible crystal framework structures from the knowledge of only the unit cell dimensions, constituent atoms and by defining exclusion zones--regions within the unit cell, from where the constituent atoms are repelled. The technique developed can be applied generally in generating new feasible framework structures with predefined microporous architectures. During the search, all trial, or candidate, structures are immediately relaxed by minimising the internal energy, which is based on the Born, or rigid ion, model of a solid. We present details of the implementation within the computational package GULP. Application to generating various microporous silicate framework structures, without imposing any symmetry constraints on the ionic positions, is described.     

Flexible ligand docking without parameter adjustment across four ligand–receptor complexes

Understanding molecular recognition is one of the fundamental problems in molecular biology. Computationally, molecular recognition is formulated as a docking problem. Ideally, a molecular docking algorithm should be computationally efficient, provide reasonably thorough search of conformational space, obtain solutions with reasonable consistency, and not require parameter adjustments. With these goals in mind, we developed DIVALI (Docking wIth eVolutionary AlgorIthms), a program which efficiently and reliably searches for the possible binding modes of a ligand within a fixed receptor. We use an AMBER-type potential function and search for good ligand conformations using a genetic algorithm (GA). We apply our system to study the docking of both rigid and flexible ligands in four different complexes. Our results indicate that it is possible to find diverse binding modes, including structures like the crystal structure, all with comparable potential function values. To achieve this, certain modifications to the standard GA recipe are essential. © 1995 John Wiley & Sons, Inc.     

A comparison of heuristic search algorithms for molecular docking

This paper describes the implementation and comparison of four heuristic search algorithms (genetic algorithm, evolutionary programming, simulated annealing and tabu search) and a random search procedure for flexible molecular docking. To our knowledge, this is the first application of the tabu search algorithm in this area. The algorithms are compared using a recently described fast molecular recognition potential function and a diverse set of five protein–ligand systems. Statistical analysis of the results indicates that overall the genetic algorithm performs best in terms of the median energy of the solutions located. However, tabu search shows a better performance in terms of locating solutions close to the crystallographic ligand conformation. These results suggest that a hybrid search algorithm may give superior results to any of the algorithms alone.     

Global optimization of clusters using electronic structure methods

Over the past decade, there has been a significant growth in the development and application of methods for performing global optimization (GO) of cluster and nanoparticle structures using first‐principles electronic structure methods coupled to sophisticated search algorithms. This has in part been driven by the desire to avoid the use of empirical potentials (EPs), especially in cases where no reliable potentials exist to guide the search toward reasonable regions of configuration space. This has been facilitated by improvements in the reliability of the search algorithms, increased efficiency of the electronic structure methods, and the development of faster, multiprocessor high‐performance computing architectures. In this review, we give a brief overview of GO algorithms, though concentrating mainly on genetic algorithm and basin hopping techniques, first in combination with EPs. The major part of the review then deals with details of the implementation and application of these search methods to allow exploration for global minimum cluster structures directly using electronic structure methods and, in particular, density functional theory. Example applications are presented, ranging from isolated monometallic and bimetallic clusters to molecular clusters and ligated and surface supported metal clusters. Finally, some possible future developments are highlighted. © 2013 Wiley Periodicals, Inc.     

A comparison of a direct search method and a genetic algorithm for conformational searching

We present results from the application of two conformational searching methods: genetic algorithms (GA) and direct search methods for finding low energy conformations of organic molecules. GAs are in a class of biologically motivated optimization methods that evolve a population of individuals in which individuals who are more “fit” have a higher probability of surviving into subsequent generations. The parallel direct search method (PDS) is a type of pattern search method that uses an adaptive grid to search for minima. Both methods found energies equal to or lower than the energy of the relaxed crystal structure in all cases, at a relatively small cost in CPU time. We suggest that either method would be a good candidate to find 3-D conformations in a large scale screening application. © 1996 by John Wiley & Sons, Inc.     

Enhanced sampling method in molecular simulations using genetic algorithm for biomolecular systems

We propose a molecular simulation method using genetic algorithm (GA) for biomolecular systems to obtain ensemble averages efficiently. In this method, we incorporate the genetic crossover, which is one of the operations of GA, to any simulation method such as conventional molecular dynamics (MD), Monte Carlo, and other simulation methods. The genetic crossover proposes candidate conformations by exchanging parts of conformations of a target molecule between a pair of conformations during the simulation. If the candidate conformations are accepted, the simulation resumes from the accepted ones. While conventional simulations are based on local update of conformations, the genetic crossover introduces global update of conformations. As an example of the present approach, we incorporated genetic crossover to MD simulations. We tested the validity of the method by calculating ensemble averages and the sampling efficiency by using two kinds of peptides, ALA3 and (AAQAA)₃. The results show that for ALA3 system, the distribution probabilities of backbone dihedral angles are in good agreement with those of the conventional MD and replica-exchange MD simulations. In the case of (AAQAA)₃ system, our method showed lower structural correlation of α-helix structures than the other two methods and more flexibility in the backbone ψ angles than the conventional MD simulation. These results suggest that our method gives more efficient conformational sampling than conventional simulation methods based on local update of conformations. © 2018 Wiley Periodicals, Inc.     

Evaluation of Multi-Objective Optimization Algorithms for NMR Chemical Shift Assignment

An automated NMR chemical shift assignment algorithm was developed using multi-objective optimization techniques. The problem is modeled as a combinatorial optimization problem and its objective parameters are defined separately in different score functions. Some of the heuristic approaches of evolutionary optimization are employed in this problem model. Both, a conventional genetic algorithm and multi-objective methods, i.e., the non-dominated sorting genetic algorithms II and III (NSGA2 and NSGA3), are applied to the problem. The multi-objective approaches consider each objective parameter separately, whereas the genetic algorithm followed a conventional way, where all objectives are combined in one score function. Several improvement steps and repetitions on these algorithms are performed and their combinations are also created as a hyper-heuristic approach to the problem. Additionally, a hill-climbing algorithm is also applied after the evolutionary algorithm steps. The algorithms are tested on several different datasets with a set of 11 commonly used spectra. The test results showed that our algorithm could assign both sidechain and backbone atoms fully automatically without any manual interactions. Our approaches could provide around a 65% success rate and could assign some of the atoms that could not be assigned by other methods.     

Structures and relative stability of medium- and large-sized silicon clusters. VI. Fullerene cage motifs for low-lying clusters Si(39), Si(40), Si(50), Si(60), Si(70), and Si(80)

We performed a constrained search, combined with density-functional theory optimization, of low-energy geometric structures of silicon clusters Si(39), Si(40), Si(50), Si(60), Si(70), and Si(80). We used fullerene cages as structural motifs to construct initial configurations of endohedral fullerene structures. For Si(39), we examined six endohedral fullerene structures using all six homolog C(34) fullerene isomers as cage motifs. We found that the Si(39) constructed based on the C(34)(C(s):2) cage motif results in a new leading candidate for the lowest-energy structure whose energy is appreciably lower than that of the previously reported leading candidate obtained based on unbiased searches (combined with tight-binding optimization). The C(34)(C(s):2) cage motif also leads to a new candidate for the lowest-energy structure of Si(40) whose energy is notably lower than that of the previously reported leading candidate with outer cage homolog to the C(34)(C(1):1). Low-lying structures of larger silicon clusters Si(50) and Si(60) are also obtained on the basis of preconstructed endohedral fullerene structures. For Si(50), Si(60), and Si(80), the obtained low-energy structures are all notably lower in energy than the lowest-energy silicon structures obtained based on an unbiased search with the empirical Stillinger-Weber potential of silicon. Additionally, we found that the binding energy per atom (or cohesive energy) increases typically >10 meV with addition of every ten Si atoms. This result may be used as an empirical criterion (or the minimal requirement) to identify low-lying silicon clusters with size larger than Si(50).     

Modulated structure and molecular dissociation of solid chlorine at high pressures

Among diatomic molecular halogen solids, high pressure structures of solid chlorine (Cl(2)) remain elusive and least studied. We here report first-principles structural search on solid Cl(2) at high pressures through our developed particle-swarm optimization algorithm. We successfully reproduced the known molecular Cmca phase (phase I) at low pressure and found that it remains stable up to a high pressure 142 GPa. At 150 GPa, our structural searches identified several energetically competitive, structurally similar, and modulated structures. Analysis of the structural results and their similarity with those in solid Br(2) and I(2), it was suggested that solid Cl(2) adopts an incommensurate modulated structure with a modulation wave close to 2∕7 in a narrow pressure range 142-157 GPa. Eventually, our simulations at >157 GPa were able to predict the molecular dissociation of solid Cl(2) into monatomic phases having body centered orthorhombic (bco) and face-centered cubic (fcc) structures, respectively. One unique monatomic structural feature of solid Cl(2) is the absence of intermediate body centered tetragonal (bct) structure during the bco → fcc transition, which however has been observed or theoretically predicted in solid Br(2) and I(2). Electron-phonon coupling calculations revealed that solid Cl(2) becomes superconductors within bco and fcc phases possessing a highest superconducting temperature of 13.03 K at 380 GPa. We further probed the molecular Cmca → incommensurate phase transition mechanism and found that the softening of the A(g) vibrational (rotational) Raman mode in the Cmca phase might be the driving force to initiate the transition.     

铝原子Bernal多面体团簇的理论研究

将遗传算法用于铝原子团簇的构型计算.运用这种方法,从任意构型开始,较好地计算了6、8、9、10个铝原子组成的原子团簇的能量最低时的构型,发现这四种铝原子团簇的能量最低构型分别取四种Bernal多面体排列.并对得到的四种构型用密度泛函方法（DFT）进行量子化学计算,结果表明，这类构型是势能面上的极小值点,可以稳定存在.     

A machine learning technique toward generating minimum energy structures of small boron clusters

The search for a global minimum related to molecular electronic structure and chemical bonding has received wide attention based on some theoretical calculations at various levels of theory. Particle swarm optimization (PSO) algorithm and modified PSO have been used to predict the energetically stable/metastable states associated with a given chemical composition. Out of a variety of techniques such as genetic algorithm, basin hopping, simulated annealing, PSO, and so on, PSO is considered to be one of the most suitable methods due to its various advantages over others. We use a swarm‐intelligence based parallel code to improve a PSO algorithm in a multidimensional search space augmented by quantum chemical calculations on gas phase structures at 0 K without any symmetry constraint to obtain an optimal solution. Our currently employed code is interfaced with Gaussian software for single point energy calculations. The code developed here is shown to be efficient. Small population size (small cluster) in the multidimensional space is actually good enough to get better results with low computational cost than the typical larger population. But for larger systems also the analysis is possible. One can try with a large number of particles as well. We have also analyzed how arbitrary and random structures and the local minimum energy structures gravitate toward the target global minimum structure. At the same time, we compare our results with that obtained from other evolutionary techniques.     

An improved algorithm for analytical gradient evaluation in resolution-of-the-identity second-order Møller-Plesset perturbation theory: application to alanine tetrapeptide conformational analysis

We present a new algorithm for analytical gradient evaluation in resolution‐of‐the‐identity second‐order Møller‐Plesset perturbation theory (RI‐MP2) and thoroughly assess its computational performance and chemical accuracy. This algorithm addresses the potential I/O bottlenecks associated with disk‐based storage and access of the RI‐MP2 t‐amplitudes by utilizing a semi‐direct batching approach and yields computational speed‐ups of approximately 2–3 over the best conventional MP2 analytical gradient algorithms. In addition, we attempt to provide a straightforward guide to performing reliable and cost‐efficient geometry optimizations at the RI‐MP2 level of theory. By computing relative atomization energies for the G3/99 set and optimizing a test set of 136 equilibrium molecular structures, we demonstrate that satisfactory relative accuracy and significant computational savings can be obtained using Pople‐style atomic orbital basis sets with the existing auxiliary basis expansions for RI‐MP2 computations. We also show that RI‐MP2 geometry optimizations reproduce molecular equilibrium structures with no significant deviations (>0.1 pm) from the predictions of conventional MP2 theory. As a chemical application, we computed the extended‐globular conformational energy gap in alanine tetrapeptide at the extrapolated RI‐MP2/cc‐pV(TQ)Z level as 2.884, 4.414, and 4.994 kcal/mol for structures optimized using the HF, DFT (B3LYP), and RI‐MP2 methodologies and the cc‐pVTZ basis set, respectively. These marked energetic discrepancies originate from differential intramolecular hydrogen bonding present in the globular conformation optimized at these levels of theory and clearly demonstrate the importance of long‐range correlation effects in polypeptide conformational analysis. © 2007 Wiley Periodicals, Inc. J Comput Chem, 2007