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. That is, the rigid-GMEC and the conformation with the lowest energy among all energy-minimized conformations (the minGMEC) are likely to be different. While the traditional DEE algorithm succeeds in not pruning rotamers that are part of the rigid-GMEC, it makes no guarantees regarding the identification of the minGMEC.
In our recent work, we have derived a novel, provable, and efficient DEE-like algorithm, called minimized-DEE (MinDEE), that guarantees that rotamers belonging to the minGMEC will not be pruned, while still pruning a combinatorial number of conformations. We have shown that MinDEE is useful not only in identifying the minGMEC, but also as a filter in an ensemble-based scoring and search algorithm for protein redesign that exploits energy-minimized conformations. Further, we have presented provably-accurate improvements to both the DEE and MinDEE criteria. Our novel enhancements resulted in a speedup of up to a factor of more than 1000 when applied in redesign for three different proteins: GrsA, plastocyanin, and protein G.