Math @ Duke

Publications [#337044] of Bruce R. Donald
Papers Published
 Ojewole, AA; Jou, JD; Fowler, VG; Donald, BR, BBK* (Branch and Bound Over K*): A Provable and Efficient EnsembleBased Protein Design Algorithm to Optimize Stability and Binding Affinity Over Large Sequence Spaces.,
Journal of Computational Biology : a Journal of Computational Molecular Cell Biology, vol. 25 no. 7
(July, 2018),
pp. 726739 [doi]
(last updated on 2018/09/27)
Abstract: Computational protein design (CPD) algorithms that compute binding affinity, Ka, search for sequences with an energetically favorable free energy of binding. Recent work shows that three principles improve the biological accuracy of CPD: ensemblebased design, continuous flexibility of backbone and sidechain conformations, and provable guarantees of accuracy with respect to the input. However, previous methods that use all three design principles are singlesequence (SS) algorithms, which are very costly: linear in the number of sequences and thus exponential in the number of simultaneously mutable residues. To address this computational challenge, we introduce BBK*, a new CPD algorithm whose key innovation is the multisequence (MS) bound: BBK* efficiently computes a single provable upper bound to approximate Ka for a combinatorial number of sequences, and avoids SS computation for all provably suboptimal sequences. Thus, to our knowledge, BBK* is the first provable, ensemblebased CPD 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 Ka for up to 105fold fewer sequences than the previous stateoftheart algorithms, which require exhaustive enumeration of sequences. Furthermore, for 51 proteinligand design problems, BBK* provably approximates Ka up to 1982fold faster than the previous stateoftheart iMinDEE/[Formula: see text]/[Formula: see text] 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.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

