Math @ Duke

Publications [#343327] of Bruce R. Donald
Papers Published
 Jou, JD; Holt, GT; Lowegard, AU; Donald, BR, MinimizationAware Recursive K ^{∗} (MARK ^{∗} ): A Novel, Provable Algorithm that Accelerates EnsembleBased Protein Design and Provably Approximates the Energy Landscape,
Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11467 LNBI
(January, 2019),
pp. 101119, ISBN 9783030170820 [doi]
(last updated on 2019/06/04)
Abstract: © 2019, Springer Nature Switzerland AG. Protein design algorithms that model continuous sidechain flexibility and conformational ensembles better approximate the in vitro and in vivo behavior of proteins. The previous state of the art, iMinDEE A ∗  K ∗ , computes provable ε approximations to partition functions of protein states (e.g., bound vs. unbound) by computing provable, admissible pairwiseminimized energy lower bounds on protein conformations and using the A ∗ enumeration algorithm to return a gapfree list of lowestenergy conformations. iMinDEEA ∗  K ∗ runs in time sublinear in the number of conformations, but can be trapped in looselybounded, lowenergy conformational wells containing many conformations with highly similar energies. That is, iMinDEE A ∗  K ∗ is unable to exploit the correlation between protein conformation and energy: similar conformations often have similar energy. We introduce two new concepts that exploit this correlation: MinimizationAware Enumeration and Recursive K ∗ . We combine these two insights into a novel algorithm, MinimizationAware Recursive K ∗ (MARK ∗ ), that tightens bounds not on single conformations, but instead on distinct regions of the conformation space. We compare the performance of iMinDEE A ∗  K ∗ vs. MARK ∗ by running the BBK ∗ algorithm, which provably returns sequences in order of decreasing K ∗ score, using either iMinDEE A ∗  K ∗ or MARK ∗ to approximate partition functions. We show on 200 design problems that MARK ∗ not only enumerates and minimizes vastly fewer conformations than the previous state of the art, but also runs upÂ to two orders of magnitude faster. Finally, we show that MARK ∗ not only efficiently approximates the partition function, but also provably approximates the energy landscape. To our knowledge, MARK ∗ is the first algorithm to do so. We use MARK ∗ to analyze the change in energy landscape of the bound and unbound states of the HIV1 capsid protein Cterminal domain in complex with camelid V H H, and measure the change in conformational entropy induced by binding. Thus, MARK ∗ both accelerates existing designs and offers new capabilities not possible with previous algorithms.


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

