A clique in a graph is a completely connected subgraph. It contains a subset of the nodes in the graph such that there is an edge between every pair of nodes in the subgraph. A key characteristic of a clique is that it cannot be extended by the addition of extra nodes; a simple example is shown in Figure 2-11. A maximum clique is the largest such subgraph that is present. An efficient algorithm for clique detection has been developed by Bron and Kerbosch (1973) and is often found to be a suitable approach for applications in chemoinformatics.

The clique detection approach to pharmacophore mapping can be explained using the following simple example. Consider one conformation for each of two molecules, each of which contains two donors (D1, D2 in the first molecule and di, d2 in the second) and two acceptors (A1, A2 and ai, a2). These sets of features are illustrated in Figure 2-12. All possible pairs of matching features are generated. There are eight in this case: A1a1, A1a2, A2a1, A2a2, D1d1, D1d2, D2d1, D2d2. Each of these pairings constitutes a node in a new graph which is sometimes called a correspondence graph. An edge is created between all pairs of nodes in the correspondence graph where the corresponding inter-feature distances in the two molecules are equal (within some tolerance). If we assume for the sake of simplicity that the distances in our illustration need to be exactly equal then we

Figure 2-12. Simple illustration of clique detection method. Consider two molecules, each of which contains two donors and two acceptors. The two graphs at the top illustrate the distances between these sets of features in the two conformations being considered. There are eight nodes in the correspondence graph (bottom) but only six edges. From these, there is one maximum clique which consists of three pairs of matching features (bottom left). (Reproduced with permission from [Gillet and Leach 2006].)

can for example draw an edge between the nodes Aiai and D\d2(distance = 4) and also between the nodes D2d1 and A2a2 (distance = 7). The bottom half of Figure 2-i2 shows the eight nodes of the correspondence graph with edges drawn between the matching nodes. This graph differs somewhat from those we have encountered previously, insofar that there is not necessarily a path between all nodes (it is a disconnected graph). In this case the two-node subgraph (A1a1, D1d2) does not constitute a valid clique as a third node (corresponding to the pairing D2d1) can be added to form the three-node clique shown in bold. This is the

Graph G1

Graph G2

Graph G1

Graph G2

Figure 2-12. Simple illustration of clique detection method. Consider two molecules, each of which contains two donors and two acceptors. The two graphs at the top illustrate the distances between these sets of features in the two conformations being considered. There are eight nodes in the correspondence graph (bottom) but only six edges. From these, there is one maximum clique which consists of three pairs of matching features (bottom left). (Reproduced with permission from [Gillet and Leach 2006].)

maximum clique present and represents a possible 3D pharmacophore consisting of three features. The corresponding subgraphs in the original graphs are shown in bold. The subgraph consisting of nodes (A2a\, D\d\ and D2d2) is not fully connected and therefore is not a clique, although it does contain two two-node cliques.

The first stage of the DISCO program which uses clique detection for pharmacophore mapping [Martin et al. 1993; Martin 2000; DISCO] involves the generation of a series of low-energy conformations for each molecule. The molecule with the smallest number of conformations is chosen as the "reference" molecule. Each of its conformations is considered in turn as the reference conformation. All the conformations of the other molecules in the set are then compared to this reference conformation and the cliques identified. Having considered each of the conformations of the reference molecule the entire set of cliques is then examined. Any clique that is common to all of the molecules, such that it is matched by at least one conformation of each molecule in the set, is a common pharmacophore.

Was this article helpful?

Learning About Fitness Resolution Fortress Can Have Amazing Benefits For Your Life And Success! Start Planning To Have Excellent Health And Fitness Today!

## Post a comment