Motivation: Structure-based computational protein design is an important topic in protein engineering. Under the assumption of a rigid backbone and a finite set of discrete conformations for 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 paper, 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 GPUs in a massively parallel fashion. In addition, we made some efforts to address the memory exceeding problems in A* search. As a result, our enhancements can achieve a significant speedup of the original A* search for protein design by four orders of magnitude on large scale test data, while still maintaining an acceptable memory overhead. Our parallel A* search algorithm can be combined with iMinDEE, a recent DEE criterion for rotamer pruning to further improve structure-based computational protein design with the consideration of side-chain flexibility.
Availability: Our software is distributed open-source under the GNU Lesser General License Version 2.1 (GNU, February 1999).
Keywords: GPU, A*, structure-based protein redesign, dead-end elimination, parallel computing, optimization problem, protein secondary structure