Clique-detection algorithm

Since its first introduction in 1982, the DOCK software has been extended in several directions. The matching spheres can be labeled with chemical properties,61 and distance bins are used to speed up the search process.62,63 Recently, the search algorithm for distance-compatible matches was changed28 to the clique-detection algorithm introduced by Crippen and co-workers.55 Furthermore, several scoring functions are now applied in combination with the DOCK algorithm.64-68... 

Use a clique-detection algorithm to identify the set of size-n cliques in G. 

Although Catalyst was not a commercial success (the company BioCAD folded in 1994, and the software was taken over by MSI), it stimulated much interest in fully automated pharmacophore discovery. Martin et al. [16] developed DISCO, borrowing code from ALADDIN to detect features and employing a clique detection algorithm mathematically similar to the MNMM method. DISCO also relies on separate, exhaustive conformational analysis, and, in general, produces many pharmacophores consistent with the SAR. 

Now let us use a simple example to explain the method for finding MCSSs based on the clique-detection algorithm. The procedures for finding the MCSS for two structures 1 and 2 in Fig. 6 involves several stages ... 

Gardiner EJ, Artymiuk PJ, Willett P. Clique-detection algorithms for matching three-dimensional molecular structures. J Mol Graph Model 1997 15 245-253. 

Another way to view similarity between 3-D structures is to focus on the pharmacophore atoms and the direction, or points, of their interaction with a target protein. The program FAMILY (142) assigns 3-D structures to families of compounds in which the variation in all distances between the points of interest are within a specified tolerance, usually 0.3-0.5 A. FAMILY uses the Bron-Kerbosh clique detection algorithm (143,144) to find these common 3-D substructures, and is rapid in execution since a typical test found that 384 compounds could be matched over seven points in under a minute on a VAX 9000. The points that are considered in the analysis are selected in an initial run of ALADDIN, and are typically the pharmacophore atoms and all heavy atoms that are attached to them. In a classification of dopaminergics, the atoms attached to these attached atoms were also used to increase the number of families found. In this example of compounds that met the pharmacophore requirements, it was shown that the set of computer-designed compounds (97) sorted itself into 36 families whereas compounds in a definitive review (145) sorted themselves into 15 families. 

Podolyan, Y. and Karypis, G. (2009) Common pharmacophore identification using frequent clique detection algorithm. Journal of Chemical Information and Modeling, 49,... 

---