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

Journal Article (Journal Article)

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.

Full Text

Duke Authors

Cited Authors

  • Looger, LL; Hellinga, HW

Published Date

  • March 16, 2001

Published In

Volume / Issue

  • 307 / 1

Start / End Page

  • 429 - 445

PubMed ID

  • 11243829

International Standard Serial Number (ISSN)

  • 0022-2836

Digital Object Identifier (DOI)

  • 10.1006/jmbi.2000.4424


  • eng

Conference Location

  • Netherlands