The fuzzy-end elimination theorem: correctly implementing the side chain placement algorithm based on the dead-end elimination theorem.

Recently it has been shown that the dead-end elimination theorem is a powerful tool in the search for the global minimum energy conformation (GMEC) of a large collection of protein side chains given known backbone coordinates and a library of allowed side chain conformational states, also known as rotamers. A side chain placement algorithm based on this theorem iteratively applies this theorem to single as well as to pairs of rotamers leading to the identification of rotamers, single or pairs, that are incompatible with the GMEC and that can thus be qualified as 'dead-ending'. Here we formulate a theorem which proves that contrary to intuition dead-end rotamer pairs cannot simply be discarded from consideration in the iterative process leading to the further elimination of dead-end rotamers. We refer to this theorem as the fuzzy-end elimination theorem. We also describe how the obtained dead-end rotamer pairs can contribute to the search for the GMEC in the protein side chain placement problem. Hence the present work forms a theoretical basis for the correct implementation of a side chain placement algorithm based on the dead-end elimination theorem. In addition, possible future perspectives are presented.