Sub- and super- structure search

At the very bottom level of most structure handling algorithms two structures are compared atom by atom and bond by bond (ref. 1). However, the preprocessing steps, the I/O conditions, the constraints in the query or in the reference structures, and requirements for a match or failure differ considerably from application to application. The most frequent used structure manipulating procedures are substructure and superstructure searches. 

In the substructure search the query (input) is small compared to the reference structures. The goal is to find all structures from the reference file that contain the query as a substructure. In the superstructure search the investigated (input) structure is large compared to structures in the reference file which is usually much shorter than in the case of substructure search. The purpose of the superstructure search is to identify all structures (skeletons, substituents, parts) from the reference file that fit into the query structure (Fig. 4.4). 

Superstructure search consists of a number of substructure searches in each of which the reference file contains only one structure, namely, the query. The number of substructure searches is equal to the number of structures in the reference file of the superstructure search. 

As already mentioned, the comparison of structures is a tedious and time consuming procedure. Therefore, the part where atom-by-atom and bond-by-bod comparisons are made should be executed on a file containing only a number of structures as small as possible. To achieve this, a fast scan of a long reference file should be made to select only the structures that possibly contain the query. 

Usually this is done in two steps first, the query structure Sx is decomposed into fragments (see equation 4.1)  

---