title: Computational Protein Design Using AND/OR Branch-and-Bound Search.
abstract: The computation of the global minimum energy conformation (GMEC) is an important and challenging topic in structure-based computational protein design. In this article, we propose a new protein design algorithm based on the AND/OR branch-and-bound (AOBB) search, a variant of the traditional branch-and-bound search algorithm, to solve this combinatorial optimization problem. By integrating with a powerful heuristic function, AOBB is able to fully exploit the graph structure of the underlying residue interaction network of a backbone template to significantly accelerate the design process. Tests on real protein data show that our new protein design algorithm is able to solve many problems that were previously unsolvable by the traditional exact search algorithms, and for the problems that can be solved with traditional provable algorithms, our new method can provide a large speedup by several orders of magnitude while still guaranteeing to find the global minimum energy conformation (GMEC) solution.
authors.affiliation: 1 Institute for Interdisciplinary Information Sciences, Tsinghua University , Beijing, China .
authors.forename: Yichao
authors.initials: Y
authors.lastname: Zhou
authors.affiliation: 1 Institute for Interdisciplinary Information Sciences, Tsinghua University , Beijing, China .
authors.forename: Yuexin
authors.initials: Y
authors.lastname: Wu
authors.affiliation: 1 Institute for Interdisciplinary Information Sciences, Tsinghua University , Beijing, China .
authors.forename: Jianyang
authors.initials: J
authors.lastname: Zeng
mesh_terms: D000465:Algorithms; D000595:Amino Acid Sequence; D019295:Computational Biology / Q000379:methods*; D008958:Models, Molecular; D011487:Protein Conformation; D011506:Proteins / Q000737:chemistry*
chemical_list: D011506:Proteins
keywords: AND/OR branch-and-bound; global minimum energy conformation; mini-bucket heuristic; protein design; residue interaction network