Dead-end elimination theorem

J. Desmet, M. De Maeyer, B. Hazes, I. Lasters. The dead-end elimination theorem and its use in protein sidechain positioning. Nature. 1992, 356, 539-542. 

I. Lasters, J. Desmet. The fuzzy-end elimination theorem Correctly implementing the sidechain placement algorithm based on the dead-end elimination theorem. Prot. Eng. 1993,... 

Another way to simplify the tertiary structure problem is to fix the backbone and then carry out an exhaustive search on the allowed side chain conformations. Desmet and co-workers have developed a dead-end elimination method for searching side chain conformations. Side chain conformations are grouped into a limited set of allowed rotamers. While an exhaustive search of all possible combinations of these rotamers is still not feasible, the application of the dead-end elimination theorem allows removal of impossible combinations early in the search, thus controlling the combinatorial explosion and leading to a small group of possible final solutions. The possible solutions can then be compared to find the best possible structure. 

J. Desmet, M. DeMaeyer, B. Hazes, and I. Lasters, Nature, 356,539 (1992). The Dead-End Elimination Theorem and Its Use in Protein Side-Chain Positioning. 

Enhancements for Combinatorial Optimization Algorithms Based on the Dead-End Elimination Theorem. 

Dead-end elimination. Frequently, the optimization of discretized problems will require a combinatorially large number of evaluations. In this case, whether the problem is computable at all will often depend on whether an efficient branch-and-bound strategy can be implemented. The optimization of sidechain interactions in a protein is a good example. The dead-end elimination theorem shows that it can be efficiently bounded, if one approximates the protein to consist of a set of interacting amino acids with discrete sidechain rotamer states and a fixed backbone. Then its potential energy can be written as... 

A critical assumption is that real-world sidechains occur in discretizable rotamers. It has been recognized already in 1987 that this is largely true (Figure 8). This is underscored by a detailed recent study of sidechain rotamers and the authors show that more than a third of all possible sidechain rotamer states may be safely eliminated even before applying the dead-end elimination theorem to analyzing the rest. 

---