The K* algorithm provably approximates partition functions for a set of states (e.g., protein, ligand, and protein-ligand complex) to a user-specified accuracy  ϵ.Often, reaching an  ϵ -approximation for a particular set of partition functions takes a prohibitive amount of time and space. To alleviate some of this cost, we introduce two algorithms into the OSPREY suite for protein design: FRIES, a Fast Removal of Inadequately Energied Sequences, and EWAK*, an Energy Window Approximation to K*. In combination, these algorithms provably retain calculational accuracy while limiting the input sequence space and the conformations included in each partition function calculation to only the most energetically favorable. This combined approach leads to significant speed-ups compared to the previous state-of-the-art multi-sequence algorithm, BBK*. As a proof of concept, we used these new algorithms to redesign the protein-protein interface (PPI) of the c-Raf-RBD:KRas complex. The Ras-binding domain of the protein kinase c-Raf (c-Raf-RBD) is the tightest known binder of KRas, a historically “undruggable” protein implicated in difficult-to-treat cancers including pancreatic ductal adenocarcinoma (PDAC). FRIES/EWAK* accurately retrospectively predicted the effect of 38 out of 41 different sets of mutations in the PPI of the c-Raf-RBD:KRas complex. Notably, these mutations include mutations whose effect had previously been incorrectly predicted using other computational methods.  Next, we used FRIES/EWAK* for prospective design and discovered a novel point mutation that improves binding of c-Raf-RBD to KRas in its active, GTP-bound state (KRas GTP ). We combined this new mutation with two previously reported mutations (which were also highly-ranked by OSPREY) to create a new variant of c-Raf-RBD, c-Raf-RBD(RKY). FRIES/EWAK* in OSPREY computationally predicted that this new variant would bind even more tightly than the previous best-binding variant, c-Raf-RBD(RK). We measured the binding affinity of c-Raf-RBD(RKY) using a bio-layer interferometry (BLI) assay and found that this new variant exhibits single-digit nanomolar affinity for KRas GTP , confirming the computational predictions made with FRIES/EWAK*. This study steps through the advancement and development of computational protein design by presenting theory, new algorithms, accurate retrospective designs, new prospective designs, and biochemical validation.

Novel, provable algorithms for efficient ensemble-based computational protein design and their application to the redesign of the c-Raf-RBD:KRas protein-protein interface