Similarity Searching in Databases of Chemical Structures

Metrics for measuring distances in configuration spaces

In order to characterize molecular structures we introduce configurational fingerprint vectors which are counterparts of quantities used experimentally to identify structures. The Euclidean distance between the configurational fingerprint vectors satisfies the properties of a metric and can therefore safely be used to measure dissimilarities between configurations in the high dimensional configuration space. In particular we show that these metrics are a perfect and computationally cheap replacement for the root-mean-square distance (RMSD) when one has to decide whether two noise contaminated configurations are identical or not. We introduce a Monte Carlo approach to obtain the global minimum of the RMSD between configurations, which is obtained from a global minimization over all translations, rotations, and permutations of atomic indices.

Three dissimilarity measures to contrast dendrograms

We discussed three dissimilarity measures between dendrograms defined over the same set, they are triples, partition, and cluster indices. All of them decompose the dendrograms into subsets. In the case of triples and partition indices, these subsets correspond to binary partitions containing some clusters, while in the cluster index, a novel dissimilarity method introduced in this paper, the subsets are exclusively clusters. In chemical applications, the dendrograms gather clusters that contain similarity information of the data set under study. Thereby, the cluster index is the most suitable dissimilarity measure between dendrograms resulting from chemical investigation. An application example of the three measures is shown to remark upon the advantages of the cluster index over the other two methods in similarity studies. Finally, the cluster index is used to measure the differences between five dendrograms obtained when applying five common hierarchical clustering algorithms on a database of 1000 molecules.

A binary linear programming formulation of the graph edit distance

A binary linear programming formulation of the graph edit distance for unweighted, undirected graphs with vertex attributes is derived and applied to a graph recognition problem. A general formulation for editing graphs is used to derive a graph edit distance that is proven to be a metric, provided the cost function for individual edit operations is a metric. Then, a binary linear program is developed for computing this graph edit distance, and polynomial time methods for determining upper and lower bounds on the solution of the binary program are derived by applying solution methods for standard linear programming and the assignment problem. A recognition problem of comparing a sample input graph to a database of known prototype graphs in the context of a chemical information system is presented as an application of the new method. The costs associated with various edit operations are chosen by using a minimum normalized variance criterion applied to pairwise distances between nearest neighbors in the database of prototypes. The new metric is shown to perform quite well in comparison to existing metrics when applied to a database of chemical graphs.

Assessing the performance of OMEGA with respect to retrieving bioactive conformations

OMEGA is a rule-based program which rapidly generates conformational ensembles of small molecules. We have varied the parameters which control the nature of the ensembles generated by OMEGA in a statistical fashion (D-optimal) with the aim of increasing the probability of generating bioactive conformations. Thirty-six drug-like ligands from different ligand-protein complexes determined by high-resolution (< or =2.0A) X-ray crystallography have been analyzed. Statistically significant models (Q(2)> or =0.75) confirm that one can increase the performance of OMEGA by modifying the parameters. Twenty-eight of the bioactive conformations were retrieved when using a low-energy cut-off (5 kcal/mol), a low RMSD value (0.6A) for duplicate removal, and a maximum of 1000 output conformations. All of those that were not retrieved had eight or more rotatable bonds. The duplicate removal parameter was found to have the largest impact on retrieval of bioactive conformations, and the maximum number of conformations also affected the results considerably. The input conformation was found to influence the results largely because certain bond angles can prevent the bioactive conformation from being generated as a low-energy conformation. Pre-optimizing the input structures with MMFF94s improved the results significantly. We also investigated the performance of OMEGA in connection with database searching. The shape-matching program Rapid Overlay of Chemical Structures (ROCS) was used as search tool. Two multi-conformational databases were built from the MDDR database plus the 36 compounds; one large (maximum 1000 conformations/mol) and one small (maximum 100 conformations/mol). Both databases provided satisfactory results in terms of retrieval. ROCS was able to rank 35 out of 36 X-ray structures among the top 500 hits from the large database.

Comparison of algorithms for dissimilarity-based compound selection

Dissimilarity-based compound selection has been suggested as an effective method for selecting structurally diverse subsets of chemical databases. This article reports a comparison of several maximum-dissimilarity and sphere-exclusion algorithms for dissimilarity-based selection. The effectiveness of the algorithms is quantified by the numbers of biological activity classes identified in subsets selected from the World Drugs Index database, and by the numbers of active compounds identified in feedback searches of this database. The experiments demonstrate the general effectiveness and efficiency of the MaxMin algorithm.