title: An efficient parallel algorithm for accelerating computational protein design.
abstract: BACKGROUND
  Structure-based computational protein design (SCPR) is an important topic in protein engineering. Under the assumption of a rigid backbone and a finite set of discrete conformations of side-chains, various methods have been proposed to address this problem. A popular method is to combine the dead-end elimination (DEE) and A* tree search algorithms, which provably finds the global minimum energy conformation (GMEC) solution.
  
  
  RESULTS
  In this article, we improve the efficiency of computing A* heuristic functions for protein design and propose a variant of A* algorithm in which the search process can be performed on a single GPU in a massively parallel fashion. In addition, we make some efforts to address the memory exceeding problem in A* search. As a result, our enhancements can achieve a significant speedup of the A*-based protein design algorithm by four orders of magnitude on large-scale test data through pre-computation and parallelization, while still maintaining an acceptable memory overhead. We also show that our parallel A* search algorithm could be successfully combined with iMinDEE, a state-of-the-art DEE criterion, for rotamer pruning to further improve SCPR with the consideration of continuous side-chain flexibility.
  
  
  BACKGROUND
  Our software is available and distributed open-source under the GNU Lesser General License Version 2.1 (GNU, February 1999). The source code can be downloaded from http://www.cs.duke.edu/donaldlab/osprey.php or http://iiis.tsinghua.edu.cn/∼compbio/software.html.
authors.affiliation: Institute for Theoretical Computer Science (ITCS), Institute for Interdisciplinary Information Sciences, Tsinghua University, Beijing 100084, P. R. China, Department of Computer Science, Duke University, Durham, NC 27708, USA and Department of Biochemistry, Duke University Medical Center, Durham, NC 27708, USA.
authors.forename: Yichao
authors.initials: Y
authors.lastname: Zhou
authors.affiliation: Institute for Theoretical Computer Science (ITCS), Institute for Interdisciplinary Information Sciences, Tsinghua University, Beijing 100084, P. R. China, Department of Computer Science, Duke University, Durham, NC 27708, USA and Department of Biochemistry, Duke University Medical Center, Durham, NC 27708, USA.
authors.forename: Wei
authors.initials: W
authors.lastname: Xu
authors.affiliation: Institute for Theoretical Computer Science (ITCS), Institute for Interdisciplinary Information Sciences, Tsinghua University, Beijing 100084, P. R. China, Department of Computer Science, Duke University, Durham, NC 27708, USA and Department of Biochemistry, Duke University Medical Center, Durham, NC 27708, USAInstitute for Theoretical Computer Science (ITCS), Institute for Interdisciplinary Information Sciences, Tsinghua University, Beijing 100084, P. R. China, Department of Computer Science, Duke University, Durham, NC 27708, USA and Department of Biochemistry, Duke University Medical Center, Durham, NC 27708, USA.
authors.forename: Bruce R
authors.initials: BR
authors.lastname: Donald
authors.affiliation: Institute for Theoretical Computer Science (ITCS), Institute for Interdisciplinary Information Sciences, Tsinghua University, Beijing 100084, P. R. China, Department of Computer Science, Duke University, Durham, NC 27708, USA and Department of Biochemistry, Duke University Medical Center, Durham, NC 27708, USA.
authors.forename: Jianyang
authors.initials: J
authors.lastname: Zeng
mesh_terms: D000465:Algorithms; D000595:Amino Acid Sequence; D019295:Computational Biology / Q000379:methods; D011487:Protein Conformation; D015202:Protein Engineering / Q000379:methods*