A Comparison of Three Heuristic Algorithms for Molecular Docking

Thed0ckingpr0cedurebetweeninhibitorsandproteinisaverys0phisticatedoptimizati0npr0blem;itisverydifficuIttocarry0utminimizati0nusinggradientmeth0dssuchasthesteepestdescentmeth0d,Gauss-Newtonmethod,whichareveryeasytofallint0theI0calpotentialwellsandverydifficultt0escapefr0mthem.S0s0meheuristicmeth0dshavebeenintr0ducedint0thestudies0fmolecuIarrec0gniti0n.Howt0chooseadequate0ptin1izationmeth0dinthed0ckingprocedureiscriticaIt0thecalcuIati0nresults.Inthispaper,wedescribetheimplementati0nandc0mpari…     

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     

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.     

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.     

Automated docking using a Lamarckian genetic algorithm and an empirical binding free energy function

A novel and robust automated docking method that predicts the bound conformations of flexible ligands to macromolecular targets has been developed and tested, in combination with a new scoring function that estimates the free energy change upon binding. Interestingly, this method applies a Lamarckian model of genetics, in which environmental adaptations of an individual's phenotype are reverse transcribed into its genotype and become heritable traits (sic). We consider three search methods, Monte Carlo simulated annealing, a traditional genetic algorithm, and the Lamarckian genetic algorithm, and compare their performance in dockings of seven protein–ligand test systems having known three-dimensional structure. We show that both the traditional and Lamarckian genetic algorithms can handle ligands with more degrees of freedom than the simulated annealing method used in earlier versions of AUTO DOCK , and that the Lamarckian genetic algorithm is the most efficient, reliable, and successful of the three. The empirical free energy function was calibrated using a set of 30 structurally known protein–ligand complexes with experimentally determined binding constants. Linear regression analysis of the observed binding constants in terms of a wide variety of structure-derived molecular properties was performed. The final model had a residual standard error of 9.11 kJ mol⁻¹ (2.177 kcal mol⁻¹) and was chosen as the new energy function. The new search methods and empirical free energy function are available in AUTO DOCK , version 3.0. © 1998 John Wiley & Sons, Inc. J Comput Chem 19: 1639–1662, 1998     

An ant colony approach for clustering

This paper presents an ant colony optimization methodology for optimally clustering N objects into K clusters. The algorithm employs distributed agents which mimic the way real ants find a shortest path from their nest to food source and back. This algorithm has been implemented and tested on several simulated and real datasets. The performance of this algorithm is compared with other popular stochastic/heuristic methods viz. genetic algorithm, simulated annealing and tabu search. Our computational simulations reveal very encouraging results in terms of the quality of solution found, the average number of function evaluations and the processing time required.     

Efficiency of tabu‐search‐based conformational search algorithms

Efficient conformational search or sampling approaches play an integral role in molecular modeling, leading to a strong demand for even faster and more reliable conformer search algorithms. This article compares the efficiency of a molecular dynamics method, a simulated annealing method, and the basin hopping (BH) approach (which are widely used in this field) with a previously suggested tabu‐search‐based approach called gradient only tabu search (GOTS). The study emphasizes the success of the GOTS procedure and, more importantly, shows that an approach which combines BH and GOTS outperforms the single methods in efficiency and speed. We also show that ring structures built by a hydrogen bond are useful as starting points for conformational search investigations of peptides and organic ligands with biological activities, especially in structures that contain multiple rings. © 2011 Wiley Periodicals, Inc. J Comput Chem, 2011     

Lattice models of peptide aggregation: evaluation of conformational search algorithms

We present a series of conformational search calculations on the aggregation of short peptide fragments that form fibrils similar to those seen in many protein mis-folding diseases. The proteins were represented by a face-centered cubic lattice model with the conformational energies calculated using the Miyazawa-Jernigan potential. The searches were performed using algorithms based on the Metropolis Monte Carlo method, including simulated annealing and replica exchange. We also present the results of searches using the tabu search method, an algorithm that has been used for many optimization problems, but has rarely been used in protein conformational searches. The replica exchange algorithm consistently found more stable structures then the other algorithms, and was particularly effective for the octamers and larger systems.     

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.     

SUMONA: A supervised method for optimizing network alignment

This study focuses on improving the multi-objective memetic algorithm for protein–protein interaction (PPI) network alignment, Optimizing Network Aligner – OptNetAlign, via integration with other existing network alignment methods such as SPINAL, NETAL and HubAlign. The output of this algorithm is an elite set of aligned networks all of which are optimal with respect to multiple user-defined criteria. However, OptNetAlign is an unsupervised genetic algorithm that initiates its search with completely random solutions and it requires substantial running times to generate an elite set of solutions that have high scores with respect to the given criteria. In order to improve running time, the search space of the algorithm can be narrowed down by focusing on remarkably qualified alignments and trying to optimize the most desired criteria on a more limited set of solutions. The method presented in this study improves OptNetAlign in a supervised fashion by utilizing the alignment results of different network alignment algorithms with varying parameters that depend upon user preferences. Therefore, the user can prioritize certain objectives upon others and achieve better running time performance while optimizing the secondary objectives.     

A parallel tabu search for conformational energy optimization of oligopeptides

We have developed and implemented a tabu search heuristic (TS) to determine the best energy minimum for oligopeptides. Our test molecule was Met‐enkephalin, a pentapetide that over the years has been used as a validation model for many global optimizers. The test potential energy function was ECEPP/3. Our tabu search implementation is based on assigning integer values to the variables to be optimized, and in facilitating the diversification and intensification of the search. The final output from the TS is treated with a local optimizer, and our best result competes both in quality and CPU time with those reported in the literature. The results indicate that TS is an efficient algorithm for conformational searches. We present a parallel TS version along with experimental results that show that this algorithm allows significant increases in speed. © 2000 John Wiley & Sons, Inc. J Comput Chem 21: 147–156, 2000     

Massive docking of flexible ligands using environmental niches in parallelized genetic algorithms

Virtual screening of large libraries of small compounds requires fast and reliable automatic docking methods. In this article we present a parallel implementation of a genetic algorithm (GA) and the implementation of an enhanced genetic algorithm (EGA) with niching that lead to remarkable speedups compared to the original version AutoDock 3.0. The niching concept is introduced naturally by sharing genetic information between evolutions of subpopulations that run independently, each on one CPU. A unique set of additionally introduced search parameters that control this information flow has been obtained for drug‐like molecules based on the detailed study of three test cases of different complexity. The average docking time for one compound is of 8.6 s using eight R10,000 processors running at 200 MHz in an Origin 2000 computer. Different genetic algorithms with and without local search (LS) have been compared on an equal workload basis showing EGA/LS to be superior over all alternatives because it finds lower energy solutions faster and more often, particularly for high dimensionality problems. © 2001 John Wiley & Sons, Inc. J Comput Chem 22: 1971–1982, 2001     

A genetic algorithm for the automated generation of small organic molecules: Drug design using an evolutionary algorithm

Rational drug design involves finding solutions to large combinatorial problems for which an exhaustive search is impractical. Genetic algorithms provide a novel tool for the investigation of such problems. These are a class of algorithms that mimic some of the major characteristics of Darwinian evolution. LEA has been designed in order to conceive novel small organic molecules which satisfy quantitative structure-activity relationship based rules (fitness). The fitness consists of a sum of constraints that are range properties. The algorithm takes an initial set of fragments and iteratively improves them by means of crossover and mutation operators that are related to those involved in Darwinian evolution. The basis of the algorithm, its implementation and parameterization, are described together with an application in de novo molecular design of new retinoids. The results may be promising for chemical synthesis and show that this tool may find extensive applications in de novo drug design projects.     

Tabu search algorithm for DNA sequencing by hybridization with isothermic libraries

In this paper, a problem of isothermic DNA sequencing by hybridization (SBH) is considered. In isothermic SBH a new type of oligonucleotide libraries is used. The library consists of oligonucleotides of different lengths depending on an oligonucleotide content. It is assumed that every oligonucleotide in such a library has an equal melting temperature. Each nucleotide adds its increment to the oligonucleotide temperature and it is assumed that A and T add 2 degrees C and C and G add 4 degrees C. The hybridization experiment using isothermic libraries should provide data with a lower number of errors due to an expected similarity of melting temperatures. From the computational point of view the problem of isothermic DNA sequencing with errors is hard, similarly like its classical counterpart. Hence, there is a need for developing heuristic algorithms that construct good suboptimal solutions. The aim of the paper is to propose a heuristic algorithm based on tabu search approach. The algorithm solves the problem with both positive and negative errors. Results of an extensive computational experiment are presented, which prove the high quality of the proposed method.     

A new Lamarckian genetic algorithm for flexible ligand‐receptor docking

We present a Lamarckian genetic algorithm (LGA) variant for flexible ligand‐receptor docking which allows to handle a large number of degrees of freedom. Our hybrid method combines a multi‐deme LGA with a recently published gradient‐based method for local optimization of molecular complexes. We compared the performance of our new hybrid method to two non gradient‐based search heuristics on the Astex diverse set for flexible ligand‐receptor docking. Our results show that the novel approach is clearly superior to other LGAs employing a stochastic optimization method. The new algorithm features a shorter run time and gives substantially better results, especially with increasing complexity of the ligands. Thus, it may be used to dock ligands with many rotatable bonds with high efficiency. © 2010 Wiley Periodicals, Inc. J Comput Chem, 2010     

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.     

Evolutionary-algorithm-based strategy for computer-assisted structure elucidation

An evolutionary algorithm (EA) using a graph-based data structure to explore the molecular constitution space is presented. The EA implementation proves to be a promising alternative to deterministic approaches to the problem of computer-assisted structure elucidation (CASE). While not relying on any external database, the EA-guided CASE program SENECA is able to find correct solutions within calculation times comparable to that of other CASE expert systems. The implementation presented here significantly expands the size limit of constitutional optimization problems treatable with evolutionary algorithms by introducing novel efficient graph-based genetic operators. The new EA-based search strategy is discussed including the underlying data structures, component design, parameter optimization, and evolution process control. Typical structure elucidation examples are given to demonstrate the algorithm's performance.     

Properties of a genetic algorithm extended by a random self-learning operator and asymmetric mutations: A convergence study for a task of powder-pattern indexing

Genetic algorithms represent a powerful global-optimisation tool applicable in solving tasks of high complexity in science, technology, medicine, communication, etc. The usual genetic-algorithm calculation scheme is extended here by introduction of a quadratic self-learning operator, which performs a partial local search for randomly selected representatives of the population. This operator is aimed as a minor deterministic contribution to the (stochastic) genetic search. The population representing the trial solutions is split into two equal subpopulations allowed to exhibit different mutation rates (so called asymmetric mutation). The convergence is studied in detail exploiting a crystallographic-test example of indexing of powder diffraction data of orthorhombic lithium copper oxide, varying such parameters as mutation rates and the learning rate. It is shown through the averaged (over the subpopulation) fitness behaviour, how the genetic diversity in the population depends on the mutation rate of the given subpopulation. Conditions and algorithm parameter values favourable for convergence in the framework of proposed approach are discussed using the results for the mentioned example. Further data are studied with a somewhat modified algorithm using periodically varying mutation rates and a problem-specific operator. The chance of finding the global optimum and the convergence speed are observed to be strongly influenced by the effective mutation level and on the self-learning level. The optimal values of these two parameters are about 6 and 5%, respectively. The periodic changes of mutation rate are found to improve the explorative abilities of the algorithm. The results of the study confirm that the applied methodology leads to improvement of the classical genetic algorithm and, therefore, it is expected to be helpful in constructing of algorithms permitting to solve similar tasks of higher complexity.     

Hybrid genetic algorithm–tabu search approach for optimising multilayer optical coatings

Constructing multilayer optical coatings (MOCs) is a difficult large-scale optimisation problem due to the enormous size of the search space. In the present paper, a new approach for designing MOCs is presented using genetic algorithms (GAs) and tabu search (TS). In this approach, it is not necessary to specify how many layers will be present in a design, only a maximum needs to be defined. As it is generally recognised that the existence of specific repeating blocks is beneficial for a design, a specific GA representation of a design is used which promotes the occurrence of repeating blocks. Solutions found by GAs are improved by a new refinement method, based on TS, a global optimisation method which is loosely based on artificial intelligence. The improvements are demonstrated by creating a visible transmitting/infrared reflecting filter with a wide variety of materials.