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     

Alignment of molecules by the Monte Carlo optimization of molecular similarity indices

3D-QSAR uses statistical techniques to correlate calculated structural properties with target properties like biological activity. The comparison of calculated structural properties is dependent upon the relative orientations of molecules in a given data set. Typically molecules are aligned by performing an overlap of common structural units. This “alignment rule” is adequate for a data set, that is closely related structurally, but is far more difficult to apply to either a diverse data set or on the basis of some structural property other than shape, even for sterically similar molecules. In this work we describe a new algorithm for molecular alignment based upon optimization of molecular similarity indices. We show that this Monte Carlo based algorithm is more effective and robust than other optimizers applied previously to the similarity based alignment problem. We show that QSARs derived using the alignments generated by our algorithm are superior to QSARs derived using the more common alignment of fitting of common structural units. © 1997 by John Wiley & Sons, Inc. J Comput Chem 18 : 1344–1353, 1997     

Pareto optimization in computational protein design with multiple objectives

The optimization for function in computational design requires the treatment of, often competing, multiple objectives. Current algorithms reduce the problem to a single objective optimization problem, with the consequent loss of relevant solutions. We present a procedure, based on a variant of a Pareto algorithm, to optimize various competing objectives in protein design that allows reducing in several orders of magnitude the search of the solution space. Our methodology maintains the diversity of solutions and provides an iterative way to incorporate automatic design methods in the design of functional proteins. We have applied our systematic procedure to design enzymes optimized for both catalysis and stability. However, this methodology can be applied to any computational chemistry application requiring multi-objective combinatorial optimization techniques.     

Unsupervised parameter optimization for automated retention time alignment of severely shifted gas chromatographic data using the piecewise alignment algorithm

Simulated chromatographic separations were used to study the performance of piecewise retention time alignment and to demonstrate automated unsupervised (without a training set) parameter optimization. The average correlation coefficient between the target chromatogram and all remaining chromatograms in the data set was used to optimize the alignment parameters. This approach frees the user from providing class information and makes the alignment algorithm applicable to classifying completely unknown data sets. The average peak in the raw simulated data set was shifted up to two peak-widths-at-base (average relative shift=2.0) and after alignment the average relative shift was improved to 0.3. Piecewise alignment was applied to severely shifted GC separations of gasolines and reformate distillation fraction samples. The average relative shifts in the raw gasolines and reformates data were 4.7 and 1.5, respectively, but after alignment improved to 0.5 and 0.4, respectively. The effect of piecewise alignment on peak heights and peak areas is also reported. The average relative difference in peak height was -0.20%. The average absolute relative difference in area was 0.15%.     

Different approaches toward an automatic structural alignment of drug molecules: Applications to sterol mimics,thrombin and thermolysin inhibitors

Summary A relative comparison of the binding properties of different drug molecules requires their mutual superposition with respect to various alignment criteria. In order to validate the results of different alignment methods, the crystallographically observed binding geometries of ligands in the pocket of a common protein receptor have been used. The alignment function in the program SEAL that calculates the mutual superposition of molecules has been optimized with respect to these references. Across the reference data set, alignments could be produced that show mean rms deviations of approximately 1 Å compared to the experimental situation. For structures with obvious skeletal similarities a multiple-flexible fit, linking common pharmacophoric groups by virtual springs, has been incorporated into the molecular mechanics program MOMO. In order to combine conformational searching with comparative alignments, the optimized SEAL approach has been applied to sets of conformers generated by MIMUMBA, a program for conformational analysis. Multiple-flexible fits have been calculated for inhibitors of ergosterol biosynthesis. Sets of different thrombin and thermolysin inhibitors have been conformationally analyzed and subsequently aligned by a combined MIMUMBA/SEAL approach. Since for these examples crystallographic data on their mutual alignment are available, an objective assessment of the computed results could be performed. Among the generated conformers, one geometry could be selected for the thrombin and thermolysin inhibitors that approached reasonably well the experimentally observed alignment.     

AcquaAlta: a directional approach to the solvation of ligand-protein complexes

Water molecules mediating polar interactions in ligand-protein complexes can substantially contribute to binding affinity and specificity. To account for such water molecules in computer-aided drug design, we performed an extensive search in the Cambridge Structural Database (CSD) to identify the geometrical criteria defining interactions of water molecules with ligand and protein. In addition, with ab initio calculations the propensity of ligand hydration was evaluated. Based on this information, we developed an algorithm (AcquaAlta) to reproduce water molecules bridging polar interactions between ligand and protein moieties. This approach was validated with 20 crystal structures and yielded a match of 76% between experimental and calculated water positions. When water molecules establishing only weak interactions with the protein were neglected, the match could be improved to 88%. Supported by a pharmacophore-based alignment tool, the solvation algorithm was then applied to the docking of oligopeptides to the periplasmic oligopeptide binding protein A (OppA). Calculated waters based on the crystal poses matched an average of 66% of the experimental waters. With water molecules calculated based on the docked ligands, the average match with the experimental waters dropped to 53%.     

FLAME: a program to flexibly align molecules

Herein, we describe a method to flexibly align molecules (FLAME = FLexibly Align MolEcules). FLAME aligns two molecules by first finding maximum common pharmacophores between them using a genetic algorithm. The resulting alignments are then subjected to simultaneous optimizations of their internal energies and an alignment score. The utility of the method in pairwise alignment, multiple molecule flexible alignment, and database searching was examined. For pairwise alignment, two carboxypeptidase ligands (Protein Data Bank codes and ), two estrogen receptor ligands ( and ), and two thrombin ligands ( and ) were used as test sets. Alignments generated by FLAME starting from CONCORD structures compared very well to the X-ray structures (average root-mean-square deviation = 0.36 A) even without further minimization in the presence of the protein. For multiple flexible alignments, five structurally diverse D3 receptor ligands were used as a test set. The FLAME alignment automatically identified three common pharmacophores: a base, a hydrogen-bond acceptor, and a hydrophobe/aromatic ring. The best alignment was then used to search the MDDR database. The search results were compared to the results using atom pair and Daylight fingerprint similarity. A similar database search comparison was also performed using estrogen receptor modulators. In both cases, hits identified by FLAME were structurally more diverse compared to those from the atom pair and Daylight fingerprint methods.     

The Classification of Rice Blast Resistant Seed Based on Ranman Spectroscopy and SVM

Rice blast is a serious threat to rice yield. Breeding disease-resistant varieties is one of the most economical and effective ways to prevent damage from rice blast. The traditional identification of resistant rice seeds has some shortcoming, such as long possession time, high cost and complex operation. The purpose of this study was to develop an optimal prediction model for determining resistant rice seeds using Ranman spectroscopy. First, the support vector machine (SVM), BP neural network (BP) and probabilistic neural network (PNN) models were initially established on the original spectral data. Second, due to the recognition accuracy of the Raw-SVM model, the running time was fast. The support vector machine model was selected for optimization, and four improved support vector machine models (ABC-SVM (artificial bee colony algorithm, ABC), IABC-SVM (improving the artificial bee colony algorithm, IABC), GSA-SVM (gravity search algorithm, GSA) and GWO-SVM (gray wolf algorithm, GWO)) were used to identify resistant rice seeds. The difference in modeling accuracy and running time between the improved support vector machine model established in feature wavelengths and full wavelengths (200–3202 cm⁻¹) was compared. Finally, five spectral preproccessing algorithms, Savitzky–Golay 1-Der (SGD), Savitzky–Golay Smoothing (SGS), baseline (Base), multivariate scatter correction (MSC) and standard normal variable (SNV), were used to preprocess the original spectra. The random forest algorithm (RF) was used to extract the characteristic wavelengths. After different spectral preproccessing algorithms and the RF feature extraction, the improved support vector machine models were established. The results show that the recognition accuracy of the optimal IABC-SVM model based on the original data was 71%. Among the five spectral preproccessing algorithms, the SNV algorithm’s accuracy was the best. The accuracy of the test set in the IABC-SVM model was 100%, and the running time was 13 s. After SNV algorithms and the RF feature extraction, the classification accuracy of the IABC-SVM model did not decrease, and the running time was shortened to 9 s. This demonstrates the feasibility and effectiveness of IABC in SVM parameter optimization, with higher prediction accuracy and better stability. Therefore, the improved support vector machine model based on Ranman spectroscopy can be applied to the fast and non-destructive identification of resistant rice seeds.     

An adaptive and iterative algorithm for refining multiple sequence alignment

Multiple sequence alignment is a basic tool in computational genomics. The art of multiple sequence alignment is about placing gaps. This paper presents a heuristic algorithm that improves multiple protein sequences alignment iteratively. A consistency-based objective function is used to evaluate the candidate moves. During the iterative optimization, well-aligned regions can be detected and kept intact. Columns of gaps will be inserted to assist the algorithm to escape from local optimal alignments. The algorithm has been evaluated using the BAliBASE benchmark alignment database. Results show that the performance of the algorithm does not depend on initial or seed alignments much. Given a perfect consistency library, the algorithm is able to produce alignments that are close to the global optimum. We demonstrate that the algorithm is able to refine alignments produced by other software, including ClustalW, SAGA and T-COFFEE. The program is available upon request.     

The PRALINE online server: optimising progressive multiple alignment on the web

We introduce the online server for PRALINE (http://ibium.cs.vu.nl/programs/pralinewww/), an iterative versatile progressive multiple sequence alignment (MSA) tool. PRALINE provides various MSA optimisation strategies including weighted global and local profile pre-processing, secondary structure-guided alignment and a reliability measure for aligned individual residue positions. The latter can also be used to optimise the alignment when the profile pre-processing strategies are iterated. In addition, we have modelled the server output to enable comprehensive visualisation of the generated alignment and easy figure generation for publications. The alignment is represented in five default colour schemes based on: residue type, position conservation, position reliability, residue hydrophobicity and secondary structure; depending on the options set. We have also implemented a custom colour scheme that allows the user to select which colour will represent one or more amino acids in the alignment. The grouping of sequences, on which the alignment is based, can also be visualised as a dendrogram. The PRALINE algorithm is designed to work more as a toolkit for MSA rather than a one step process.     

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.     

Optimizing the size and configuration of combinatorial libraries

This paper addresses a major issue in library design, namely how to efficiently optimize the library size (number of products) and configuration (number of reagents at each position) simultaneously with other properties such as diversity, cost, and drug-like physicochemical property profiles. These objectives are often in competition, for example, minimizing the number of reactants while simultaneously maximizing diversity, and thus present difficulties for traditional optimization methods such as genetic algorithms and simulated annealing. Here, a multiobjective genetic algorithm (MOGA) is used to vary library size and configuration simultaneously with other library properties. The result is a family of solutions that explores the tradeoffs in the objectives. This is achieved without the need to assign relative weights to the objectives. The user is then able to make an informed choice on an appropriate compromise solution. The method has been applied to two different virtual libraries: a two-component aminothiazole library and a four-component benzodiazepine library.     

ALIGN_MTX—An optimal pairwise textual sequence alignment program,adapted for using in sequence-structure alignment

The presented program ALIGN_MTX makes alignment of two textual sequences with an opportunity to use any several characters for the designation of sequence elements and arbitrary user substitution matrices. It can be used not only for the alignment of amino acid and nucleotide sequences but also for sequence-structure alignment used in threading, amino acid sequence alignment, using preliminary known PSSM matrix, and in other cases when alignment of biological or non-biological textual sequences is required. This distinguishes it from the majority of similar alignment programs that make, as a rule, alignment only of amino acid or nucleotide sequences represented as a sequence of single alphabetic characters. ALIGN_MTX is presented as downloadable zip archive at http://www.imbbp.org/software/ALIGN_MTX/ and available for free use.As application of using the program, the results of comparison of different types of substitution matrix for alignment quality in distantly related protein pair sets were presented. Threading matrix SORDIS, based on side-chain orientation in relation to hydrophobic core centers with evolutionary change-based substitution matrix BLOSUM and using multiple sequence alignment information position-specific score matrices (PSSM) were taken for test alignment accuracy. The best performance shows PSSM matrix, but in the reduced set with lower sequence similarity threading matrix SORDIS shows the same performance and it was shown that combined potential with SORDIS and PSSM can improve alignment quality in evolutionary distantly related protein pairs.     

16-fold degeneracy of peptide plane orientations from residual dipolar couplings: analytical treatment and implications for protein structure determination

Residual dipolar couplings (RDCs) measured for internally rigid molecular fragments provide important information about the relative orientations of these fragments. Dependent on the symmetry of the alignment tensor and the symmetry of the molecular fragment, however, there generally exist more than one solution for the fragment orientation consistent with the measured RDCs. Analytical solutions are presented that describe the complete set of orientations of internally rigid fragments that are consistent with multiple dipolar couplings measured in a single alignment medium that is rhombic. For the first time, it is shown that, for a planar fragment such as the peptide plane, there generally exist 16 different solutions with their analytical expressions presented explicitly. The presence of these solutions is shown to be highly relevant for standard structure determination protocols using RDCs to refine molecular structures. In particular, when using standard protein structure refinement with RDCs that were measured in a single alignment medium as constraints, it is found that often more than one of the peptide plane solutions is physically viable; i.e., despite being consistent with measured RDCs, the local backbone structure can be incorrect. On the basis of experimental and simulated examples, it is rationalized why protein structures that are refined against RDCs measured in a single medium can have lower resolution (precision) than one would expect on the basis of the experimental accuracy of the RDCs. Conditions are discussed under which the correct solution can be identified.