Substructures Maximal Common

A substructure search algorithm is usually the first step in the implementation of other important topological procedures for the analysis of chemical structures such as identification of equivalent atoms, determination of maximal common substructure, ring detection, calculation of topological indices, etc. 

Brint, A.T. and Willett, P. (1987a). Algorithms for the Identification of Three-Dimensional Maximal Common Substructures. J.Chem.Inf.Comput.ScL, 27,152-158. 

Cone, M.M., Venkataraghavan, R. and McLafferty, F.W. (1977). Molecular Structure Comparison Program for the Identification of Maximal Common Substructures. JAm.Chem.Soc., 99, 7668-7671. 

Xu, J. (1996) GMA a generic match algorithm for structural homomorphism, isomorphism, and maximal common substructure match and its applications./. Ghem. Inf. Gomput. Sci, 36, 25-34. 

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. 

Brief analysis of the internal relationships between the structure isomorphism, SSS, and MSCC problems can help us understand these problems better. The MCSS problem is that of determining all possible maximal common substructures of two (or more) given structures. If the detected maximal common substructure is isomorphic to the smaller of the two given structures, this kind of MCSS problem is, in fact, a substructure isomorphism problem. If the maximal common substructure found is isomorphic to both of the given structures, such a problem belongs to the structure isomorphism problem. Therefore the structure and substructure isomorphism problems are only two special cases of the more general MCSS problem (see also Fig. 1). 

Because of limitations of space, the structure isomorphism problem will not be further discussed. This chapter will focus on the discussion of the major algorithms and methodologies for solving substructure and maximal common substructure problems and their applications. 

Historically, substructure search methods were first developed for dealing with 2-D structures, and later these techniques were either extended to become, or incorporated into, 3-D substructure search approaches. The same is true for maximal common substructure searching methods. Two-dimensional methods are not only useful tools themselves for many applications, but also an important foundation for the understanding and development of the 3-D counterparts in many cases. In this chapter, the SSS methods will be introduced first. Then, attention will be focused toward the discussion on MCSS methodologies. 

Early Work in the Development of Maximal Common Substructure Search Algorithms... 

Applications of the Maximal Common Substructure Search Method... 

Chen L, Robien W. MCSS a new algorithm for perception of maximal common substructures and its application to NMR spectral studies. 1. The algorithm. J Chem Inf Comput Sci 1992 32 501-506. 

---