Heuristics for similarity searching of chemical graphs using a maximum common edge subgraph algorithm

Recently a method (RASCAL) for determining graph similarity using a maximum common edge subgraph algorithm has been proposed which has proven to be very efficient when used to calculate the relative similarity of chemical structures represented as graphs. This paper describes heuristics which simplify a RASCAL similarity calculation by taking advantage of certain properties specific to chemical graph representations of molecular structure. These heuristics are shown experimentally to increase the efficiency of the algorithm, especially at more distant values of chemical graph similarity.     

Scaffold hopping using clique detection applied to reduced graphs

Similarity-based methods for virtual screening are widely used. However, conventional searching using 2D chemical fingerprints or 2D graphs may retrieve only compounds which are structurally very similar to the original target molecule. Of particular current interest then is scaffold hopping, that is, the ability to identify molecules that belong to different chemical series but which could form the same interactions with a receptor. Reduced graphs provide summary representations of chemical structures and, therefore, offer the potential to retrieve compounds that are similar in terms of their gross features rather than at the atom-bond level. Using only a fingerprint representation of such graphs, we have previously shown that actives retrieved were more diverse than those found using Daylight fingerprints. Maximum common substructures give an intuitively reasonable view of the similarity between two molecules. However, their calculation using graph-matching techniques is too time-consuming for use in practical similarity searching in larger data sets. In this work, we exploit the low cardinality of the reduced graph in graph-based similarity searching. We reinterpret the reduced graph as a fully connected graph using the bond-distance information of the original graph. We describe searches, using both the maximum common induced subgraph and maximum common edge subgraph formulations, on the fully connected reduced graphs and compare the results with those obtained using both conventional chemical and reduced graph fingerprints. We show that graph matching using fully connected reduced graphs is an effective retrieval method and that the actives retrieved are likely to be topologically different from those retrieved using conventional 2D methods.     

MultiMCS: a fast algorithm for the maximum common substructure problem on multiple molecules

Several efficient correspondence graph-based algorithms for determining the maximum common substructure (MCS) of a pair of molecules have been published in the literature. The extension of the problem to three or more molecules is however nontrivial; heuristics used to increase the efficiency in the two-molecule case are either inapplicable to the many-molecule case or do not provide significant speedups. Our specific algorithmic contribution is two-fold. First, we show how the correspondence graph approach for the two-molecule case can be generalized to obtain an algorithm that is guaranteed to find the optimum connected MCS of multiple molecules, and that runs fast on most families of molecules using a new divide-and-conquer strategy that has hitherto not been reported in this context. Second, we provide a characterization of those compound families for which the algorithm might run slowly, along with a heuristic for speeding up computations on these families. We also extend the above algorithm to a heuristic algorithm to find the disconnected MCS of multiple molecules and to an algorithm for clustering molecules into groups, with each group sharing a substantial MCS. Our methods are flexible in that they provide exquisite control on various matching criteria used to define a common substructure.     

Database clustering with a combination of fingerprint and maximum common substructure methods

We present an efficient method to cluster large chemical databases in a stepwise manner. Databases are first clustered with an extended exclusion sphere algorithm based on Tanimoto coefficients calculated from Daylight fingerprints. Substructures are then extracted from clusters by iterative application of a maximum common substructure algorithm. Clusters with common substructures are merged through a second application of an exclusion sphere algorithm. In a separate step, singletons are compared to cluster substructures and added to a cluster if similarity is sufficiently high. The method identifies tight clusters with conserved substructures and generates singletons only if structures are truly distinct from all other library members. The method has successfully been applied to identify the most frequently occurring scaffolds in databases, for the selection of analogues of screening hits and in the prioritization of chemical libraries offered by commercial vendors.     

The maximum common substructure as a molecular depiction in a supervised classification context: experiments in quantitative structure/biodegradability relationships

The maximum common structure between two molecules (MCS) induces a similarity that enables one to group compounds sharing the same pattern. This text relates a study based on such a structural depiction in a context of quantitative structure/biodegradability relationships (QSBR). The similarity indices are based exclusively on the MCS. First, the results of statistical tests prove that these indices significantly group compounds of similar activity together. These first conclusions enable the elaboration of classification models using those structural similarities. In a second part, a population of classifiers relying on the maximum common structure and the k-nearest-neighbor algorithm is explored. Finally, a thorough examination of the best models is conducted.     

The fragment molecular orbital and systematic molecular fragmentation methods applied to water clusters

Two electronic structure methods, the fragment molecular orbital (FMO) and systematic molecular fragmentation (SMF) methods, that are based on fragmenting a large molecular system into smaller, more computationally tractable components (fragments), are presented and compared with fully ab initio results for the predicted binding energies of water clusters. It is demonstrated that, even when explicit three-body effects are included (especially necessary for water clusters due to their complex hydrogen-bonded networks) both methods present viable, computationally efficient alternatives to fully ab initio quantum chemistry.     

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     

Many-body interaction analysis: algorithm development and application to large molecular clusters

A completely automated algorithm for performing many-body interaction energy analysis of clusters (MBAC) [M. J. Elrodt and R. J. Saykally, Chem. Rev. 94, 1975 (1994); S. S. Xantheas, J. Chem. Phys. 104, 8821 (1996)] at restricted Hartree-Fock (RHF)/MA Plesset 2nd order perturbation theory (MP2)/density functional theory (DFT) level of theory is reported. Use of superior guess density matrices (DM's) for smaller fragments generated from DM of the parent system and elimination of energetically insignificant higher-body combinations, leads to a more efficient performance (speed-up up to 2) compared to the conventional procedure. MBAC approach has been tested out on several large-sized weakly bound molecular clusters such as (H(2)O)(n), n=8, 12, 16, 20 and hydrated clusters of amides and aldehydes. The MBAC results indicate that the amides interact more strongly with water than aldehydes in these clusters. It also reconfirms minimization of the basis set superposition error for large cluster on using superior quality basis set. In case of larger weakly bound clusters, the contributions higher than four body are found to be repulsive in nature and smaller in magnitude. The reason for this may be attributed to the increased random orientations of the interacting molecules separated from each other by large distances.     

Step-by-step calculation of all maximum common substructures through a constraint satisfaction based algorithm

In this paper we propose a new algorithm for subgraph isomorphism based on the representation of molecular structures as colored graphs and the representation of these graphs as vectors in n-dimensional spaces. The presented process that obtains all maximum common substructures is based on the solution of a constraint satisfaction problem defined as the common m-dimensional space (m< or =n) in which the vectors representing the matched graphs can be defined.     

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.     

Estimations of subgraph positions in molecular graphs and their common subgraph peculiarities

Some questions emerged from electronic data processing of molecular structures (graphs) and its fragments have been considered in this work. Quantitative estimations of subgraph positions in molecular graphs are presented and some properties of their maximal common subgraphs are described.     

De novo generation of molecular structures using optimization to select graphs on a given lattice

A recurrent problem in organic chemistry is the generation of new molecular structures that conform to some predetermined set of structural constraints that are imposed in an endeavor to build certain required properties into the newly generated structure. An example of this is the pharmacophore model, used in medicinal chemistry to guide de novo design or selection of suitable structures from compound databases. We propose here a method that efficiently links up a selected number of required atom positions while at the same time directing the emergent molecular skeleton to avoid forbidden positions. The linkage process takes place on a lattice whose unit step length and overall geometry is designed to match typical architectures of organic molecules. We use an optimization method to select from the many different graphs possible. The approach is demonstrated in an example where crystal structures of the same (in this case rigid) ligand complexed with different proteins are available.     

Global geometry optimization of clusters using a growth strategy optimized by a genetic algorithm

A new strategy for global geometry optimization of clusters is presented. Important features are a restriction of search space to favorable nearest-neighbor distance ranges, a suitable cluster growth representation with diminished correlations, and easy transferability of the results to larger clusters. The strengths and possible limitations of the method are demonstrated for Si₁₀ using an empirical potential.     

Parallelizing a molecular dynamics algorithm on a multiprocessor workstation using OpenMP

The atomistic molecular dynamics program YASP has been parallelized for shared-memory computer architectures. Parallelization was restricted to the most CPU-time-consuming parts: neighbor-list construction, calculation of nonbonded, angle and dihedral forces, and constraints. Most of the sequential FORTRAN code was kept; parallel constructs were inserted as compiler directives using the OpenMP standard. Only in the case of the neighbor list did the data structure have to be changed. The parallel code achieves a useful speedup over the sequential version for systems of several thousand atoms and above. On an IBM Regatta p690+, the throughput increases with the number of processors up to a maximum of 12-16 processors depending on the characteristics of the simulated systems. On dual-processor Xeon systems, the speedup is about 1.7.     

Geometry optimization of molecular clusters and complexes using scaled internal coordinates

Scaled internal coordinates are introduced for use in the geometry optimization of systems composed of multiple fragments, such as solvated molecules, clusters, and biomolecular complexes. The new coordinates are related to bond lengths, bond angles and torsion angles by geometry-dependent scaling factors. The scaling factors serve to expedite the optimization of complexes containing outlying fragments, without hindering the optimization of the intramolecular degrees of freedom. Trial calculations indicate that, at asymptotic separations, the scaling factors improve the rate of convergence by a factor of 4 to 5.     

Pharmacophore elucidation and 3D-QSAR analysis of a new class of highly potent inhibitors of acid ceramidase based on maximum common substructure and field fit alignment methods

Comparative molecular field analysis (CoMFA) and comparative similarity indices analysis (CoMSIA) studies have been carried on a series of 2,4-dioxopyrimidine-1-carboxamides as acid ceramidase inhibitors. Two alignment rules for the compounds were defined using maximum common substructure and field fit. The best orientation was then searched by all-orientation search strategy, to minimize the effect of the initial orientation of the structures. The Kennard Stone algorithm was used to divide the entire set into training (25 compounds) and test (7 compounds) sets. Pharmacophore model identification was also performed using DISCOtech algorithm and refinement was carried out using GASP, to highlight important structural features that could be responsible for the inhibitory activity. All constructed models showed appropriate statistical parameters in terms of q ² and r _pred ² . Based upon the information obtained from CoMFA, CoMSIA, and developed pharmacophore pattern, some key features that may be used to design new inhibitors for acid ceramidase have been identified.     

A molecular dynamics investigation of rare-gas solvated cation-benzene clusters using a new model potential

The main static and dynamic properties of some ionic heteroclusters, involving K+, C6H6, and Ar, have been investigated. A new representation of the intermolecular potential energy, which takes into account both electrostatic and non-electrostatic contributions to the overall noncovalent interaction, was used. Dynamical calculations were performed for a microcanonical ensemble. Particular attention was paid to the opening of the isomerization and dissociation processes for K+-C6H6-Ar(n) and to the formation of some of its fragments at increasing temperatures of the cluster considered.