title: Improved Pruning algorithms and Divide-and-Conquer strategies for Dead-End Elimination, with application to protein design.
abstract: BACKGROUND
  Structure-based protein redesign can help engineer proteins with desired novel function. Improving computational efficiency while still maintaining the accuracy of the design predictions has been a major goal for protein design algorithms. The combinatorial nature of protein design results both from allowing residue mutations and from the incorporation of protein side-chain flexibility. Under the assumption that a single conformation can model protein folding and binding, the goal of many algorithms is the identification of the Global Minimum Energy Conformation (GMEC). A dominant theorem for the identification of the GMEC is Dead-End Elimination (DEE). DEE-based algorithms have proven capable of eliminating the majority of candidate conformations, while guaranteeing that only rotamers not belonging to the GMEC are pruned. However, when the protein design process incorporates rotameric energy minimization, DEE is no longer provably-accurate. Hence, with energy minimization, the minimized-DEE (MinDEE) criterion must be used instead.
  
  
  RESULTS
  In this paper, we present provably-accurate improvements to both the DEE and MinDEE criteria. We show that our novel enhancements result in a speedup of up to a factor of more than 1000 when applied in redesign for three different proteins: Gramicidin Synthetase A, plastocyanin, and protein G.
  
  
  BACKGROUND
  Contact authors for source code.
authors.affiliation: Dartmouth Computer Science Department, Hanover, NH 03755, USA.
authors.forename: Ivelin
authors.initials: I
authors.lastname: Georgiev
authors.forename: Ryan H
authors.initials: RH
authors.lastname: Lilien
authors.forename: Bruce R
authors.initials: BR
authors.lastname: Donald
mesh_terms: D000465:Algorithms; D000595:Amino Acid Sequence; D003198:Computer Simulation; D015195:Drug Design; D008956:Models, Chemical; D008958:Models, Molecular; D008969:Molecular Sequence Data; D011487:Protein Conformation; D015202:Protein Engineering / Q000379:methods*; D011506:Proteins / Q000032:analysis / Q000737:chemistry* / Q000235:genetics; D011994:Recombinant Proteins / Q000032:analysis / Q000737:chemistry; D016415:Sequence Alignment / Q000379:methods*; D020539:Sequence Analysis, Protein / Q000379:methods*; D012984:Software
chemical_list: D011506:Proteins; D011994:Recombinant Proteins