Radical performance enhancements for combinatorial optimization algorithms based on the dead-end elimination theorem

Recent advances in protein design have demonstrated the effectiveness of optimization algorithms based on the dead-end elimination theorem. The algorithms solve the combinatorial problem of finding the optimal placement of side chains for a set of backbone coordinates. Although they are powerful tools, these algorithms have severe limitations when the number of side chain rotamers is large. This is due to the high-order time dependence of the aspect of the calculation that deals with rotamer doubles. We present three independent algorithmic enhancements that significantly increase the speed of the doubles computation. These methods work by using quantities that are inexpensive to compute as a basis for forecasting which expensive calculations are worthwhile. One of the methods, the comparison of extrema, is derived from analytical considerations, and the remaining two, the “magic-bullet” and the “q_rs” and “q_uv” metrics, are based on empirical observation of the distribution of energies in the system. When used together, these methods effect an overall speed improvement of as much as a factor of 47, and for the doubles aspect of the calculation, a factor of 95. Together, these enhancements extend the envelope of inverse folding to larger proteins by making formerly intractable calculations attainable in reasonable computer time. © 1998 John Wiley & Sons, Inc. J Comput Chem 19: 1505–1514, 1998