Dead-end elimination for multistate protein design

Multistate protein design is the task of predicting the amino acid sequence that is best suited to selectively and stably fold to one state out of a set of competing structures. Computationally, it entails solving a challenging optimization problem. Therefore, notwithstanding the increased interest in multistate design, the only implementations reported are based on either genetic algorithms or Monte Carlo methods. The dead-end elimination (DEE) theorem cannot be readily transfered to multistate design problems despite its successful application to single-state protein design. In this article we propose a variant of the standard DEE, called type-dependent DEE. Our method reduces the size of the conformational space of the multistate design problem, while provably preserving the minimal energy conformational assignment for any choice of amino acid sequence. Type-dependent DEE can therefore be used as a preprocessing step in any computational multistate design scheme. We demonstrate the applicability of type-dependent DEE on a set of multistate design problems and discuss its strength and limitations. (c) 2007 Wiley Periodicals, Inc.