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 t hey are powerful tools, these algorithms have severe limitations when the number of side chain rotamers is large. This is due to the high-or der time dependence of the aspect of the calculation that deals with r otamer doubles. We present three independent algorithmic enhancements that significantly increase the speed of the doubles computation. Thes e methods work by using quantities that are inexpensive to compute as a basis for forecasting which expensive calculations are worthwhile. O ne of the methods, the comparison of extrema, is derived from analytic al considerations, and the remaining two, the ''magic-bullet'' and the ''q(rs)'' and ''q(uv)'' metrics, are based on empirical observation o f the distribution of energies in the system. When used together, thes e methods effect an overall speed improvement of as much as a factor o f 47, and for the doubles aspect of the calculation, a factor of 95. T ogether, these enhancements extend the envelope of inverse folding to larger proteins by making formerly intractable calculations attainable in reasonable computer time. (C) 1998 John Wiley & Sons, Inc. J Compu t Chem 19: 1505-1514, 1998.