Improved Pruning algorithms and Divide-and-Conquer strategies for Dead-End Elimination, with application to protein design Bioinformatics

Motivation: Structure-based protein redesign can help engineer proteinswithdesirednovel function. Improvingcomputational 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 theDEE andMinDEE criteria.We show that our novel enhance-ments 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. Availability: Contact authors for source code. Contact