An efficient parallel algorithm for accelerating computational protein design.


Journal Article

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.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.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 or∼compbio/software.html.

Full Text

Cited Authors

  • Zhou, Y; Xu, W; Donald, BR; Zeng, J

Published Date

  • June 2014

Published In

Volume / Issue

  • 30 / 12

Start / End Page

  • i255 - i263

PubMed ID

  • 24931991

Pubmed Central ID

  • 24931991

Electronic International Standard Serial Number (EISSN)

  • 1367-4811

International Standard Serial Number (ISSN)

  • 1367-4803

Digital Object Identifier (DOI)

  • 10.1093/bioinformatics/btu264


  • eng