Subgraph matching

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

Barrow, H. G. and R. M. Burstall, "Subgraph Isomorphism, Matching Relational Structures, and Maximal Cliques," Information Processing Letters, (4), 83-84 (January 1976). 

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

The refinement procedure utilises the fact that if some query node Q(X) has another node Q(fV) at some specific distance ) ( and/or angle), and if some database node D(Z) matches with Q(W), then there must also be some node D(Y) at the appropriate distance(s) from D(Z) which matches with Q(X) this is a necessary, but not sufficient, condition for a subgraph isomorphism to be present (except in the limiting case of all the query nodes having been matched, when the condition is both necessary and sufficient). The refinement procedure is called before each possible assignment of a database node to a query node and the matched substructure is increased by one node if, and only if, the condition holds for all nodes W, X, Y and Z. The basic algorithm terminates once a match has been detected or until a mismatch has been confirmed [70] it is easy to extend the algorithm to enable the detection of all matches between a query pattern and a database structure, as is required for applications such as those discussed here. 

Graphs of query and test molecules can be compared by graph matching (subgraph detection) algorithms or systematic comparison of inter-feature distances. Two molecules are considered similar if their pharmacophores match for at least one predicted conformation. In order to explore conformational space and generate conformational ensembles, multiple compound conformations are typically generated by systematic conformational search (in increments) around rotatable bonds. 

H.G. Barrow, R.M. Burstall, Subgraph Isomorphism, Matching Relational Structures and Maximal Cliques, Information Proc-cesing Letters, 4 (1976) 83-84. 

Once ACCS subset is assigned to a specific activity class, characteristic substructures are mapped back on each molecule by performing a subgraph search for each fragment and whenever a fragment matches an atom of the molecule, a counter for that atom is increased by 1. For each atom, division of its final counter state by the total number of matched substructures gives its match rate. Then, for each active molecule, core structures are defined as the set of all atoms of the molecule that have an ACCS match rate greater than a threshold value. 

Yak/Prgen and COMPASS work fundamentally with the surface of molecules, and derive representations of the predicted binding surface of the receptor ( pseudoreceptor ). APOLLO appears to work with features —groups on the molecule that meet specific topological criteria (i.e., which match a specified subgraph isomorphism query) these features must be defined by the user. 

---