Subgraphs Common

Raymond JW, Willett P. Maximum common subgraph isomorphism algorithms for the matching of chemical structures. J Comput-Aided Mol Des 2002 16 521-33. 

Let us find the optimal local similarity, or the maximum common subgraph, of two graphs ... 

Figure 3. When a reaction (1) is added to the data base its MXC (2) and CXC (3) are also added. The reaction is then compared with other reactions (4) and a maximum common subgraph (5) is added.

In order to find the maximum common subgraph between two graphs G and H, the following approach is frequently used. Firstly, a so-called product graph is created. The graph contains a node for all possible assignments of nodes from one graph to the other. 

McGregor, J. and Willett, P. (1981) Use of a maximal common subgraph algorithm in the automatic identification of the ostensible bond changes occurring in chemical reactions../. Chem. Inf. Comput. Sci. 21, 137-140. 

Two vertices are called adjacent if they share a common edge. A path is a sequence of adjacent vertices. A graph is connected if any two of its vertices are linked by a path. A maximal connected subgraph of graph G is called a connected component of G. Every graph can be decomposed into connected components. 

In Fig. 4.17, a set of benzodiazepines is shown that were aligned using Feature Tree matchings. The bond orientations extracted from the template are shown by arrows. The algorithm has been shown to be very useful to visualize similarities beyond common subgraphs. Further test cases can be found in [53]. 

In this chapter, the largest common substructure is defined as a connected subgraph having the greatest number of edges in a graph. The algorithm of Takahashi et al. [31] is summarized as follows,... 

Step (iv) Detection of common subgraphs in the given chemical structures can be done by the subgraph (substructure) search technique. If there are no common subgraphs present, the search is terminated. 

Step (v) The common subgraphs obtained hitherto are stored in the candidate list. 

---