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 combinatorial optimization of protein side-chain placement in protein design and homology modeling. In order to reach their full potential, the theorems must be extended to handle very hard problems. We present a suite of new algorithms within the DEE paradigm that significantly extend its range of convergence and reduce run time. As a demonstration, we show that a total protein design problem of 10(115) combinations, a hydrophobic core design problem of 10(244) combinations, and a side-chain placement problem of 10(1044) combinations 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 approximately 53, 144 and 851 log-units, respectively, using modest computational resources. Small to average-sized protein domains can now be designed automatically, and side-chain placement calculations can be solved for nearly all sizes of proteins and protein complexes in the growing field of structural genomics.
Looger
L L
LL
Department of Biochemistry, Duke University Medical Center, Box 3711, Durham, NC 27710, USA.
Hellinga
H W
HW
D000465:Algorithms; D000595:Amino Acid Sequence; D004268:DNA-Binding Proteins; D005353:Fibronectins / Q000737:chemistry / Q000235:genetics; D016678:Genome; D006801:Humans; D007140:Immunoglobulin Fab Fragments / Q000737:chemistry / Q000235:genetics; D008956:Models, Chemical; D011487:Protein Conformation; D015202:Protein Engineering; D017510:Protein Folding; D012097:Repressor Proteins / Q000737:chemistry / Q000235:genetics; D017386:Sequence Homology, Amino Acid; D014764:Viral Proteins; D054334:Viral Regulatory and Accessory Proteins; D014961:X-Ray Diffraction
D004268:DNA-Binding Proteins; D005353:Fibronectins; D007140:Immunoglobulin Fab Fragments; D012097:Repressor Proteins; D014764:Viral Proteins; D054334:Viral Regulatory and Accessory Proteins; C016649:phage repressor proteins