Format

Send to

Choose Destination
Bioinformatics. 2014 Jun 15;30(12):i255-i263. doi: 10.1093/bioinformatics/btu264.

An efficient parallel algorithm for accelerating computational protein design.

Author information

1
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.
2
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.

Abstract

MOTIVATION:

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.

AVAILABILITY:

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.

PMID:
24931991
PMCID:
PMC4058937
DOI:
10.1093/bioinformatics/btu264
[Indexed for MEDLINE]
Free PMC Article

Supplemental Content

Full text links

Icon for Silverchair Information Systems Icon for PubMed Central
Loading ...
Support Center