Subgraph 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. 

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]. 

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. 

Recently, Bayada et al. [32] described the multiple largest common subgraph problem mentioned above with an efficient algorithm to handle it. 

Therefore, searching for some edge-weighted maximal common subgraph for the two complete graphs is equivalent to searching for a clique [58] in this... 

Given two graphs Gi and G2, if there exists a subgraph of order k of Gi isomorphic to a subgraph 5 of G2, the pair of isomorphic subgraphs S, S ) is called a common subgraph of order k of Gi and G2. A common subgraph is maximal if there is no common... 

Maximum common subgraph isomorphism algorithms are used to locate the largest common part that two strnctnres have in common. These algorithms are nsed to find similar strnctnres. 

Maximum Common Subgraph Isomorphism is a method from mathematical graph theory used to locate the largest part that two structures have in common to find similar structures. 

For convenience, in the subsequent sections of this chapter, the mathematical terms introduced above, such as graph, subgraph, and maximal common subgraph, are interchangeably used with the corresponding chemical terms, such as structure, substructure, and maximal common substructure. 

---