Bron-Kerbosh clique-detection

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. 

The Bron-Kerbosh clique detection is used iteratively to find sets of common distances, i.e., cliques, obtaining thereby disco solutions, e.g., pharmacophore maps chirality is also considered by evaluating the sign of the torsion angle for quadruplets of non-coplanar points. In family only one pair of structures is composed at a time for grouping structures into families. The program compair makes similar pairwise comparisons employing a user-supplied reference structure each time. 

---