Dead-End Elimination with Perturbations (“DEEPer”):
A provable protein design algorithm with continuous sidechain and backbone flexibility,

by M. Hallen, D. Keedy, and B. R. Donald.

Proteins 2013; 80(1):18-39. DOI: 10.1002/prot.24150

Abstract. Computational protein and drug design generally require accurate modeling of protein conformations. This modeling typically starts with an experimentally-determined protein structure and considers possible conformational changes due to mutations or new ligands. The DEE/A* algorithm provably finds the GMEC (global minimum-energy conformation) of a protein assuming the backbone does not move and the sidechains take on conformations from a set of discrete, experimentally-observed conformations called rotamers. DEE/A* can efficiently find the overall GMEC for exponentially many mutant sequences. Previous improvements to DEE/A* include modeling ensembles of sidechain conformations and either continuous sidechain or backbone flexibility. We present a new algorithm, DEEPer ("Dead-End Elimination with Perturbations"), that combines these advantages and can also handle much more extensive backbone flexibility and backbone ensembles. DEEPer provably finds the GMEC or, if desired by the user, all conformations and sequences within a specified energy window of the GMEC. It includes the new abilities to handle arbitrarily large backbone perturbations and to generate ensembles of backbone conformations. It also incorporates the shear, an experimentally-observed local backbone motion never before used in design. Additionally, we derive a new method to accelerate DEE/A*-based calculations, indirect pruning, that is particularly useful for DEEPer. In 67 benchmark tests on 64 proteins, DEEPer consistently identified lower-energy conformations than previous methods did, indicating more accurate modeling. Additional tests demonstrated its ability to incorporate larger, experimentally-observed backbone conformational changes and to model realistic conformational ensembles. These capabilities provide significant advantages for modeling protein mutations and protein-ligand interactions.

Figure: The DEEPer algorithm designs proteins by searching over sequence-space and over sidechain- and backbone- conformational space. High-energy mutations and conformations of both individual residues and pairs of residues are pruned. Low-energy mutations and conformations are enumerated using a conformational tree (left). The lowest-energy conformations and sequences are found using continuous minimization with respect to backbone perturbations, such as the shear motion, as well as sidechain dihedrals (right).