Backtracking substructure

The backtracking algorithm is the core part of every software system that performs substructure searching. There are other approaches which have been applied both as alternatives to the backtracking algorithm or (most usually) in combination with it. Section 6.3.3 describes the approaches used for the optimization of the... 

Backtracking-Based Maximal Common Substructure Search Algorithms... 

Figure 7 Decreased Matrix and Corresponding Matrix of structures 1 and 2 with original order (starting atom pair 2-7) [1]. The information shown belongs to one partial mapping between structures 1 and 2, before any backtracking operation is performed and with the common substructures found drawn in bold lines. [From the American Chemical Society (the bold highlighting added and all signs removed.)]...

As shown in Fig. 7, atom 1 in structure 1 is first tried to be matched onto atom 2 in structure 2. Following this search branch, a substructure with five atoms and four bonds is found before any backtracking is performed (bold lines in structures 1 and 2 of Fig. 7). The size of the common structure found so far is used as a backtrack condition. With this backtracking condition, no branches were cut off before the next more extended substructure containing six atoms and five bonds is found. Then, this new best number of bonds is used as a new backtrack condition for further search. It can be easily seen from structures 1 and 2 in Fig. 7 that the correct MCSS will not be found until atom 1 in structure 1 is matched against atom 8 or 9 in structure 2. This example reveals that most CPU time is wasted on investigating many useless searches on bad branches within the search tree. 

The method described in this section can be used to guide the backtracking search within one search tree in such a way that larger common substructures may be found as early as possible during the search process. 

The task is to check whether the specified substructure is contained in the given molecule. Starting atom-wise comparison at nitrogen atom no. 1, in both structures the attached atom is carbon. The next atom, however, is oxygen in the molecule and carbon in the substructure. At this point, the search is stopped and backtracked. A new trial starting at the nitrogen atom no. 8 in the molecule will match the substructure step by step. 

Substructure searches are implemented in standard fashion that is, a fast screen-out is used to get rid of obvious nonmatches, followed by a full atom-by-atom search on the structures that pass the screen. The atom-by-atom search is a backtracking, graph-tracing procedure, resembling those used by Chemical Abstracts Service and Molecular Design Ltd. 

Figure 1.5 Schematic representation of the search procedure within the 3 DSEARCH program. For each substructure identified in Step I, Steps 2, 3 and 4 are repeated as many times as necessary to identify the specified motif In this example, two iterations are sufficient. During the search process, failure at any stage causes the process to backtrack to the previous stage, as indicated by the double-headed arrows. Reproduced from [32] by permission of the International Union of Crystallography...

---