Editing Protein design (section)

====Dead-end elimination====
{{main|Dead-end elimination}}

The dead-end elimination (DEE) algorithm reduces the search space of the problem iteratively by removing rotamers that can be provably shown to be not part of the global lowest energy conformation (GMEC). On each iteration, the dead-end elimination algorithm compares all possible pairs of rotamers at each residue position, and removes each rotamer <var>r&prime;<sub>i</sub></var> that can be shown to always be of higher energy than another rotamer <var>r<sub>i</sub></var> and is thus not part of the GMEC:

: <math> E(r^\prime_i) + \sum_{j\ne i} \min_{r_j} E(r^\prime_i,r_j) > E(r_i) + \sum_{j\ne i} \max_{r_j} E(r_i,r_j) </math>

Other powerful extensions to the dead-end elimination algorithm include the [[Dead-end elimination#Pairs elimination criterion|pairs elimination criterion]], and the [[Dead-end elimination#Generalization|generalized dead-end elimination criterion]]. This algorithm has also been extended to handle continuous rotamers with provable guarantees.

Although the Dead-end elimination algorithm runs in polynomial time on each iteration, it cannot guarantee convergence. If, after a certain number of iterations, the dead-end elimination algorithm does not prune any more rotamers, then either rotamers have to be merged or another search algorithm must be used to search the remaining search space. In such cases, the dead-end elimination acts as a pre-filtering algorithm to reduce the search space, while other algorithms, such as A*, Monte Carlo, Linear Programming, or FASTER are used to search the remaining search space.<ref name="donald10" />