 |
FIGURE 3.5 The basic operation of clique detection.
In graph theory terms, a clique is a subgraph in which every node is connected to every other node. For three-dimensional molecular structures, the nodes of the graph might typically be the atoms of the structure labeled according to atomic symbol and the edges are the distances between the points. Clique-detection algorithms find cliques in an input graph that match a clique in a reference graph. That is, they find corresponding points in the two three-dimensional structures such that corresponding points are of the same type in the two structures and all corresponding interpoint distances are identical within some tolerance.
In Figure 3.5, two different cliques in the same molecule are indicated, as is one clique of a second molecule. As shown, the matching cliques in the two molecules can be superimposed. Notice that the points do not superimpose exactly since the lengths of the edges need only be identical within some tolerance.
|
FIGURE 3.5 The basic operation of clique detection.
NAS Home Page | NAP Home Page | Reading Room | MCTCC Home Page