Subgraph isomorphism algorithm

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

In order to conduct a search, the graphs that represent each of the proteins in the PDB must be examined using a subgraph isomorphism algorithm to see if they... 

Subgraph isomorphism algorithms can find a snbstrnctnre within a structure. 

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. 

Due to the nature of this approach, subgraph isomorphism algorithms are time consuming isomorphism is a combinatorial problem belonging to the nondetermin-istic polynomial time complete (NP complete) class of problems, which are widely believed to be unsolvable. Several authors suggested improvements to reduce the... 

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. 

A subgraph isomorphism algorithm published by Ullmann in 1976 also contains a refinement step, which is essentially an application of relaxation. 

IDENTIFICATION OP SECONDARY STRUCTURE MOTIFS Use of Subgraph Isomorphism Algorithm... 

Ensure the pattern of centres in the candidate matches that in the query. This utilises Ullman s subgraph isomorphism algorithm as described by Willett . 

Our current work involves the use of the DAP for the implementation of UUmann s subgraph isomorphism algorithm, which has been shown to provide a highly efficient mechanism for substructure searching in files of both 2-D and 3-D chemical structures . 

---