Parallel Computational Protein Design

Abstract

Computational structure-based protein design (CSPD) is an important problem in computational biology, which aims to design or improve a prescribed protein function based on a protein structure template. It provides a practical tool for real-world protein engineering applications. A popular CSPD method that guarantees to find the global minimum energy solution (GMEC) is to combine both dead-end elimination (DEE) and A* tree search algorithms. However, in this framework, the A* search algorithm can run in exponential time in the worst case, which may become the computation bottleneck of large-scale computational protein design process. To address this issue, we extend and add a new module to the OSPREY program that was previously developed in the Donald lab (Gainza et al., Methods Enzymol 523:87, 2013) to implement a GPU-based massively parallel A* algorithm for improving protein design pipeline. By exploiting the modern GPU computational framework and optimizing the computation of the heuristic function for A* search, our new program, called gOSPREY, can provide up to four orders of magnitude speedups in large protein design cases with a small memory overhead comparing to the traditional A* search algorithm implementation, while still guaranteeing the optimality. In addition, gOSPREY can be configured to run in a bounded-memory mode to tackle the problems in which the conformation space is too large and the global optimal solution cannot be computed previously. Furthermore, the GPU-based A* algorithm implemented in the gOSPREY program can be combined with the state-of-the-art rotamer pruning algorithms such as iMinDEE (Gainza et al., PLoS Comput Biol 8:e1002335, 2012) and DEEPer (Hallen et al., Proteins 81:18-39, 2013) to also consider continuous backbone and side-chain flexibility.

Keywords: A*; CUDA; Dead-end elimination; GPGPU; Parallel computing; Protein design.

Figure 1

An illustration of the traditional A* tree search algorithm. (a) An example of the A* search tree at a certain time. Nodes in dark shade represent the nodes that have already been expanded and visited. Nodes in light shade represent the frontier nodes which are stored in the priority queue and waiting to be expanded. The node labeled with a is the node with minimum heuristic function value in the priority queue and thus is currently being expended. (b) The workflow of the node expansion operation for current node a.

Figure 1

An illustration of the traditional A* tree search algorithm. (a) An example of the A* search tree at a certain time. Nodes in dark shade represent the nodes that have already been expanded and visited. Nodes in light shade represent the frontier nodes which are stored in the priority queue and waiting to be expanded. The node labeled with a is the node with minimum heuristic function value in the priority queue and thus is currently being expended. (b) The workflow of the node expansion operation for current node a.

Figure 2

The illustration of the parallel node expansion operations in our parallel A* search algorithm. (a) An example of the A* search tree at a certain time. The meaning of Figure 2a is as same as that of Figure 1a except that now the algorithm is expanding nodes a, b, and c in parallel. The nodes labeled with a, b, and c are the nodes with the minimum heuristic function values in their respective priority queues. (b) The workflow on how multiple nodes are expanded simultaneously.

Figure 2

The illustration of the parallel node expansion operations in our parallel A* search algorithm. (a) An example of the A* search tree at a certain time. The meaning of Figure 2a is as same as that of Figure 1a except that now the algorithm is expanding nodes a, b, and c in parallel. The nodes labeled with a, b, and c are the nodes with the minimum heuristic function values in their respective priority queues. (b) The workflow on how multiple nodes are expanded simultaneously.

Figure 3

Semi-log plots about the ratios of speedups and memory overhead of our GPU-based A* search algorithm. The x axes represent the magnitude of the design problem, while the y axes of Figure 3a and 3b represent the ratios of speedups and memory overhead of our GPU-based algorithm comparing to the traditional sequential A* search algorithm, respectively. The circle and square marks represent the results of our GPU-based A* search algorithm with 768 and 4992 parallel priority queues, respectively.

Figure 3

Semi-log plots about the ratios of speedups and memory overhead of our GPU-based A* search algorithm. The x axes represent the magnitude of the design problem, while the y axes of Figure 3a and 3b represent the ratios of speedups and memory overhead of our GPU-based algorithm comparing to the traditional sequential A* search algorithm, respectively. The circle and square marks represent the results of our GPU-based A* search algorithm with 768 and 4992 parallel priority queues, respectively.