title: BWM*: A Novel, Provable, Ensemble-based Dynamic Programming Algorithm for Sparse Approximations of Computational Protein Design.
abstract: Sparse energy functions that ignore long range interactions between residue pairs are frequently used by protein design algorithms to reduce computational cost. Current dynamic programming algorithms that fully exploit the optimal substructure produced by these energy functions only compute the GMEC. This disproportionately favors the sequence of a single, static conformation and overlooks better binding sequences with multiple low-energy conformations. Provable, ensemble-based algorithms such as A* avoid this problem, but A* cannot guarantee better performance than exhaustive enumeration. We propose a novel, provable, dynamic programming algorithm called Branch-Width Minimization* (BWM*) to enumerate a gap-free ensemble of conformations in order of increasing energy. Given a branch-decomposition of branch-width w for an n-residue protein design with at most q discrete side-chain conformations per residue, BWM* returns the sparse GMEC in O([Formula: see text]) time and enumerates each additional conformation in merely O([Formula: see text]) time. We define a new measure, Total Effective Search Space (TESS), which can be computed efficiently a priori before BWM* or A* is run. We ran BWM* on 67 protein design problems and found that TESS discriminated between BWM*-efficient and A*-efficient cases with 100% accuracy. As predicted by TESS and validated experimentally, BWM* outperforms A* in 73% of the cases and computes the full ensemble or a close approximation faster than A*, enumerating each additional conformation in milliseconds. Unlike A*, the performance of BWM* can be predicted in polynomial time before running the algorithm, which gives protein designers the power to choose the most efficient algorithm for their particular design problem.
authors.affiliation: 1 Department of Computer Science, Duke University , Durham, North Carolina.
authors.forename: Jonathan D
authors.initials: JD
authors.lastname: Jou
authors.affiliation: 1 Department of Computer Science, Duke University , Durham, North Carolina.|2 Department of Biochemistry, Duke University Medical Center , Durham, North Carolina.|3 Department of Computational Biology and Bioinformatics Program, Duke University , Durham, North Carolina.
authors.forename: Swati
authors.initials: S
authors.lastname: Jain
authors.affiliation: 1 Department of Computer Science, Duke University , Durham, North Carolina.
authors.forename: Ivelin S
authors.initials: IS
authors.lastname: Georgiev
authors.affiliation: 1 Department of Computer Science, Duke University , Durham, North Carolina.|2 Department of Biochemistry, Duke University Medical Center , Durham, North Carolina.|4 Department of Chemistry, Duke University , Durham, North Carolina.
authors.forename: Bruce R
authors.initials: BR
authors.lastname: Donald
mesh_terms: D000465:Algorithms; D000595:Amino Acid Sequence; D019295:Computational Biology / Q000379:methods*; D008958:Models, Molecular; D011487:Protein Conformation; D011506:Proteins / Q000737:chemistry*; D012984:Software
chemical_list: D011506:Proteins
keywords: OSPREY; branch-decomposition; dynamic programming; ensemble-based algorithms; protein design; provable algorithms; sparse residue interaction graphs