Clique-detection

One limitation of clique detection is that it needs to be run repeatedly with differei reference conformations and the run-time scales with the number of conformations pt molecule. The maximum likelihood method [Bamum et al. 1996] eliminates the need for reference conformation, effectively enabling every conformation of every molecule to a< as the reference. Despite this, the algorithm scales linearly with the number of conformatior per molecule, so enabling a larger number of conformations (up to a few hundred) to b handled. In addition, the method scores each of the possible pharmacophores based upo the extent to which it fits the set of input molecules and an estimate of its rarity. It is nc required that every molecule has to be able to match every feature for the pharmacophor to be considered. 

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. 

In conclusion, the advent of combinatorial and HTS approaches to lead discovery has resulted in substantial interest in the development of novel techniques for computer-based compound-selection. This interest is being reflected not only in the application of novel algorithmic approaches to compound selection, e.g., the use of k-D trees [13] and clique detection [55], but also in the increasing emphasis that is being placed on quantitative validation procedures, such as those discussed in the previous section such developments can only further increase the importance of the methods discussed in this chapter. 

Gardiner, E.J., Holliday, J.D., Willett, P., Wilton, D.J. and Artymiuk, P.J. Selection of reagents for combinatorial synthesis using clique detection. QSAR, 1998, 17,232-236. 

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. 

Clique-Detection-Based Maximal Common Substructure Search Algorithms... 

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. 

ALADDIN (91). DISCO uses a rapid technique, clique detection, to identify maps from the set of all potential pharmacophore points. Typically, the maps are generated in a few minutes of CPU time and the results can be viewed in a variety of molecular modeling programs. 

---