Minimization-Aware Recursive A Novel, Provable Algorithm that Accelerates Ensemble-Based Protein Design and Provably Approximates the Energy Landscape.

Protein design algorithms that model continuous sidechain flexibility and conformational ensembles better approximate the and behavior of proteins. The previous state of the art, iMinDEE-*-*, computes provable -approximations to partition functions of protein states (e.g., bound vs. unbound) by computing provable, admissible pairwise-minimized energy lower bounds on protein conformations, and using the * enumeration algorithm to return a gap-free list of lowest-energy conformations. iMinDEE-*-* runs in time sublinear in the number of conformations, but can be trapped in loosely-bounded, low-energy conformational wells containing many conformations with highly similar energies. That is, iMinDEE-*-* is unable to exploit the correlation between protein conformation and energy: . We introduce two new concepts that exploit this correlation: Minimization-Aware Enumeration and Recursive *. We combine these two insights into a novel algorithm, Minimization-Aware Recursive * (*), which tightens bounds not on single conformations, but instead on . We compare the performance of iMinDEE-*-* versus * by running the Branch and Bound over * (*) algorithm, which provably returns sequences in order of decreasing * score, using either iMinDEE--* or * to approximate partition functions. We show on 200 design problems that * not only enumerates and minimizes vastly fewer conformations than the previous state of the art, but also runs up to 2 orders of magnitude faster. Finally, we show that * not only efficiently approximates the partition function, but also approximates the . To our knowledge, * is the first algorithm to do so. We use * to analyze the change in energy landscape of the bound and unbound states of an HIV-1 capsid protein C-terminal domain in complex with a camelid VH, and measure the change in conformational entropy induced by binding. Thus, * both accelerates existing designs and offers new capabilities not possible with previous algorithms.