title: 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.
authors.affiliation: Institute for Interdisciplinary Information Sciences, Tsinghua University, Beijing, P. R. China.
authors.forename: Yichao
authors.initials: Y
authors.lastname: Zhou
authors.affiliation: Department of Computer Science, Duke University, Durham, NC, USA.|Department of Biochemistry, Duke University Medical Center, Durham, NC, USA.
authors.forename: Bruce R
authors.initials: BR
authors.lastname: Donald
authors.affiliation: Institute for Interdisciplinary Information Sciences, Tsinghua University, Beijing, P. R. China. zengjy321@tsinghua.edu.cn.
authors.forename: Jianyang
authors.initials: J
authors.lastname: Zeng
mesh_terms: D000465:Algorithms; D000595:Amino Acid Sequence; D019295:Computational Biology / Q000379:methods*; D003198:Computer Simulation; D008958:Models, Molecular; D011487:Protein Conformation; D015202:Protein Engineering / Q000379:methods*; D011506:Proteins / Q000737:chemistry / Q000235:genetics; D015203:Reproducibility of Results; D012984:Software; D013329:Structure-Activity Relationship
chemical_list: D011506:Proteins
keywords: A*; CUDA; Dead-end elimination; GPGPU; Parallel computing; Protein design