The dead-end elimination algorithm (DEE) is a method for minimizing a function over a discrete set of independent variables.
The basic idea is to identify "dead ends", i.e., combinations of variables that are not necessary to define a global minimum because there is always a way of replacing such combination by a better or equivalent one.
Hence, dead-end elimination is a mirror image of dynamic programming, in which "good" combinations are identified and explored further.
Although the method itself is general, it has been developed and applied mainly to the problems of predicting and designing the structures of proteins (and in this wise was cited in the Scientific Background to the 2024 Nobel Prize in Chemistry).
[1] It closely related to the notion of dominance in optimization also known as substitutability in a Constraint Satisfaction Problem.
The original description and proof of the dead-end elimination theorem can be found in [1].
An effective DEE implementation requires four pieces of information: Note that the criteria can easily be reversed to identify the maximum of a given function as well.
Dead-end elimination has been used effectively to predict the structure of side chains on a given protein backbone structure by minimizing an energy function
The dihedral angle search space of the side chains is restricted to a discrete set of rotamers for each amino acid position in the protein (which is, obviously, of fixed length).
Since atoms in proteins are assumed to interact only by two-body potentials, the energy may be written Where
(that is, the pair energy between a rotamer and itself) is taken to be zero, and thus does not affect the summations.
of the same sidechain, then rotamer A can be eliminated from further consideration, which reduces the search space.
The pairs criterion is more difficult to describe and to implement, but it adds significant eliminating power.
, the matrices of precomputed energies can become costly to store.
entries, so the total number of self-energies to store is
This makes the total number of entries in an unreduced pair matrix
The above two criteria are normally applied iteratively until convergence, defined as the point at which no more rotamers or pairs can be eliminated.
Since this is normally a reduction in the sample space by many orders of magnitude, simple enumeration will suffice to determine the minimum within this pared-down set.
The single-rotamer search scales quadratically in time with total number of rotamers.
The pair search scales cubically and is the slowest part of the algorithm (aside from energy calculations).
A large-scale benchmark of DEE compared with alternative methods of protein structure prediction and design finds that DEE reliably converges to the optimal solution for protein lengths for which it runs in a reasonable amount of time[2].
It significantly outperforms the alternatives under consideration, which involved techniques derived from mean field theory, genetic algorithms, and the Monte Carlo method.
are all different orientations of the same amino acid side chain.
It is also possible to allow multiple side chains to "compete" over a position
by including both types of side chains in the set of rotamers for that position.
A short zinc finger protein fold has been redesigned this way[3].
However, this greatly increases the number of rotamers per position and still requires a fixed protein length.
One example is a refinement of the singles elimination criterion known as the Goldstein criterion[4], which arises from fairly straightforward algebraic manipulation before applying the minimization: Thus rotamer
This is an improvement over the original criterion, which requires comparison of the best possible (that is, the smallest) energy contribution from
An extended discussion of elaborate DEE criteria and a benchmark of their relative performance can be found in [5].