Theoretical and algorithmical optimization of the dead-end elimination theorem

The dead-end elimination theorem has proved to be a powerful method to reduce the theoretically accessible conformational space when modeling protein side chains by using a rotameric representation of possible conformations. In this work, theoretical details about variants to the original criterion are discussed. We also provide information on how the equations can be algorithmically implemented in such a way that both computational performance and structural accuracy are optimized. In addition, we discuss the theoretical and practical aspects of three new methods called the "bottom line theorem", dead-end elimination assisted by local modeling and a combinatorial search combined with conventional dead-end elimination. It is shown that the algorithm in its current from enables the determination of the global minimum energy side chain conformation of large proteins on a time scale of hours while for small proteins of up to 30 residues the calculations are done on a time scale of seconds. The latter opens a way to combine a main chain sampling algorithm with the dead-end elimination method to locally model entire fragments of a protein chain.