Maximal-common-subgraph-isomorphism

Grindley HM, Artymiuk PJ, Rice DW, Willett P. Identification of tertiary structure resemblance in proteins using a maximal common subgraph isomorphism algorithm. J Mol Biol 1993 229 707-721. 

H. M. Grindley, P. J. Artymiuk, D. W. Rice, and P. Willett, J. Mol. Biol., 229, 707 (1993). Identification of Tertiary Structure Resemblance in Proteins Using a Maximal Common Subgraph Isomorphism Algorithm. 

MCS detection is equivalent to maximal common subgraph isomorphism Levi notes that this belongs to the class of NP-complete problems since the identification of all subgraphs containing MCSiAyB) atoms requires... 

It expresses the number of edges and/or loops that must be deleted from G] to get a subgraph which is isomorphic to the maximal common subgraph G2HG2 The distance (2.10) is rewritten in a manifestly symmetric form [cf. (2.11b)]... 

The subgraphs Gj and Gg are isomorphic to the maximal common subgraph GjnGgi G Mlg MJjnGg. These subgraphs correspond to those parts of Gj and Gg that remain intact in the chemical transformation (3.14). Hence, a simplified version of (3.14) is expressed by... 

Three main types of similarity measure have been used for quantifying the degree of resemblance between pairs of 2D chemical structures, these measures being based upon fragment substructures, topological indices, or maximal common subgraph (MCS) isomorphism algorithms. 

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

---