Backtracking trees

Fig. 5.1. Backtrack tree for labeled generation of simple graphs on three nodes.

Figure 5.2 shows the backtrack tree for this application of Algorithm 5.1. 

Table 5.5. Pruning the backtrack tree for l-azabicyclo[4.3.2]undecane, structure 3 from Figure 5.8. Atoms that become unique are printed in bold.

Therefore this part of the backtrack tree can be pruned immediately. In exactly the same manner the last alternative at btll, marking atom 11 with atom 10 also becoming unique after refinement by 11, is found to be worse than candidate 2. Figure 5.9 shows the backtrack tree corresponding to this example, the pruned parts of the tree are drawn as dashed lines. 

Fig. 5.9. The backtrack tree for structure 3, Figure 5.8. Parts of the tree that are pruned are drawn in dashed lines.

Large parts of the search tree can be pruned in cases of higher symmetry. If two labelings result in the same bond matrix at different positions in the tree, then a symmetry (automorphism) has been found. The information on automorphisms that accumulates in the process finally defines the complete automorphism group of the graph or molecule. This is stored in the form of a set of generators (a Sims chain [93,142,296]). This information is used to prune parts of the backtrack tree found to be equivalent to other parts already considered. 

Fig. 5.10. The backtrack tree for cubane, structure 4, Figure 5.8. The branches for vertex 3-8 past...

Fig. 5.1 Backtrack tree for labeled generation of simple graphs on three nodes.-----------------169...

Figure 20 The backtracking trees presented here represent the interaction of four amino acid residues. In (a) the top of the tree is the first residue side chain that possess two possible rotameric states, thus two branches. Residue 2 is on the next level and has three rotamers. The third residue has five possible rotamers, and Residue 4 has two possible rotamer states. The tree in (a) is not efficient because of the number of rotamer options for Residue 3. The same set of residues are evaluated in (b), but the order in which they are examined is changed. Residue 1 is still first, but that is now followed by Residue 4, then Residue 2, and finally Residue 3. Residues having the fewest possible rotamers are evaluated first, thus increasing the speed of the search for the GMEC. A total of 60 possible side-chain interactions exist in this example with the most favorable denoted with a circle [1, 2, 5, 1]. The arrows denote the path of the most favorable rotamer combination. This image was adapted from Canutescu et al. ...

---