Generalized dead-end elimination algorithms make large-scale protein side-chain structure prediction tractable: Implications for protein design and structural genomics

The dead-end elimination (DEE) theorems are powerful tools for the combinat orial optimization of protein side-chain placement in protein design and ho mology modeling. In order to reach their full potential, the theorems must be extended to handle very hard problems. We present a suite of new algorit hms within the DEE paradigm that significantly extend its range of converge nce and reduce run time. As a demonstration, we show that a total protein d esign problem of 10(115) combinations, a hydrophobic core design problem of 10(244) combinations, and a side-chain placement problem of 10(1044) combi nations are solved in less than two weeks, a day and a half, and an hour of CPU time, respectively. This extends the range of the method by approximat ely 53, 144 and 851 log-units, respectively, using modest computational res ources. Small to average-sized protein domains can now be designed automati cally, and side-chain placement calculations can be solved for nearly all s izes of proteins and protein complexes in the growing field of structural g enomics. (C) 2001 Academic Press.