Skip to main content

BBK* (Branch and bound over K*): A provable and efficient ensemble-based algorithm to optimize stability and binding affinity over large sequence spaces

Publication ,  Conference
Ojewole, AA; Jou, JD; Fowler, VG; Donald, BR
Published in: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
January 1, 2017

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, Ka. 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 Ka for a combinatorial number of sequences, and entirely avoids single-sequence computation for all provably subop-timal sequences. Thus, to our knowledge, BBK* is the first provable, ensemble-based Ka 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 105-fold fewer sequences than exhaustive enumeration. Furthermore, for 51 protein-ligand design problems, BBK* provably approximates Ka 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.

Duke Scholars

Published In

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

DOI

EISSN

1611-3349

ISSN

0302-9743

Publication Date

January 1, 2017

Volume

10229 LNCS

Start / End Page

157 / 172

Related Subject Headings

  • Artificial Intelligence & Image Processing
  • 46 Information and computing sciences
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Ojewole, A. A., Jou, J. D., Fowler, V. G., & Donald, B. R. (2017). BBK* (Branch and bound over K*): A provable and efficient ensemble-based algorithm to optimize stability and binding affinity over large sequence spaces. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (Vol. 10229 LNCS, pp. 157–172). https://doi.org/10.1007/978-3-319-56970-3_10
Ojewole, A. A., J. D. Jou, V. G. Fowler, and B. R. Donald. “BBK* (Branch and bound over K*): A provable and efficient ensemble-based algorithm to optimize stability and binding affinity over large sequence spaces.” In Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 10229 LNCS:157–72, 2017. https://doi.org/10.1007/978-3-319-56970-3_10.
Ojewole AA, Jou JD, Fowler VG, Donald BR. BBK* (Branch and bound over K*): A provable and efficient ensemble-based algorithm to optimize stability and binding affinity over large sequence spaces. In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2017. p. 157–72.
Ojewole, A. A., et al. “BBK* (Branch and bound over K*): A provable and efficient ensemble-based algorithm to optimize stability and binding affinity over large sequence spaces.” Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10229 LNCS, 2017, pp. 157–72. Scopus, doi:10.1007/978-3-319-56970-3_10.
Ojewole AA, Jou JD, Fowler VG, Donald BR. BBK* (Branch and bound over K*): A provable and efficient ensemble-based algorithm to optimize stability and binding affinity over large sequence spaces. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2017. p. 157–172.

Published In

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

DOI

EISSN

1611-3349

ISSN

0302-9743

Publication Date

January 1, 2017

Volume

10229 LNCS

Start / End Page

157 / 172

Related Subject Headings

  • Artificial Intelligence & Image Processing
  • 46 Information and computing sciences