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. Then we can refrain from searching such combinations further. 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. 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 . Basic requirements An effective DEE implementation requires four pieces of information: A well-defined finite set of discrete independent variables A precomputed numerical value (considered the "energy") associated with each element in the set of variables (and possibly with their pairs, triples, etc.) A criterion or criteria for determining when an element is a "dead end", that is, when it cannot possibly be a member of the solution set An objective function (considered the "energy function") to be minimized Note that the criteria can easily be reversed to identify the maximum of a given function as well. Applications to protein structure prediction 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). The original DEE description included criteria for the elimination of single rotamers and of rotamer pairs, although this can be expanded. In the following discussion, let be the length of the protein and let represent the rotamer of the side chain. Since atoms in proteins are assumed to interact only by two-body potentials, the energy may be written Where represents the "self-energy" of a particular rotamer , and represents the "pair energy" of the rotamers . Also note that (that is, the pair energy between a rotamer and itself) is taken to be zero, and thus does not affect the summations.