$$BBK^*$$ (Branch and Bound over $$K^*$$ ): A Provable and Efficient Ensemble-Based Algorithm to Optimize Stability and Binding Affinity over Large Sequence Spaces

Protein design algorithms that compute binding affinity search for sequences with an energetically favorable free energy of binding. Recent work shows that the following design principles improve the biological accuracy of protein design: ensemble-based design and continuous conformational flexibility. Ensemble-based algorithms capture a measure of entropic contributions to binding affinity, \(K_a\). Designs using backbone flexibility and continuous side-chain flexibility better model conformational flexibility. A third design principle, provable guarantees of accuracy, ensures that an algorithm computes the best sequences defined by the input model (i.e. input structures, energy function, and allowed protein flexibility). However, previous provable methods that model ensembles and continuous flexibility are single-sequence algorithms, which are very costly: linear in the number of sequences and thus exponential in the number of mutable residues. To address these computational challenges, we introduce a new protein design algorithm, \(BBK^*\), that retains all aforementioned design principles yet provably and efficiently computes the tightest-binding sequences. A key innovation of \(BBK^*\) is the multi-sequence (MS) bound: \(BBK^*\) efficiently computes a single provable upper bound to approximate \(K_a\) for a combinatorial number of sequences, and entirely avoids single-sequence computation for all provably suboptimal sequences. Thus, to our knowledge, \(BBK^*\) is the first provable, ensemble-based \(K_a\) algorithm to run in time sublinear in the number of sequences. Computational experiments on 204 protein design problems show that \(BBK^*\) finds the tightest binding sequences while approximating \(K_a\) for up to \(10^5\)-fold fewer sequences than exhaustive enumeration. Furthermore, for 51 protein-ligand design problems, \(BBK^*\) provably approximates \(K_a\) up to 1982-fold faster than the previous state-of-the-art iMinDEE/\(A^*\)/\(K^*\) algorithm. Therefore, \(BBK^*\) not only accelerates protein designs that are possible with previous provable algorithms, but also efficiently performs designs that are too large for previous methods.