BetaSCP2: A Program for the Optimal Prediction of Side-Chains in Proteins

The

side-chain prediction problem

(SCP-problem), is a computational problem to predict the optimal structure of proteins by finding the optimal dihedral angles. The SCP-problem is one of key computational cornerstones for many important problems such as protein design, flexible docking of proteins, homology modeling, etc. The SCP-problem can be formulated as a minimization problem of an integer linear program which is NP-hard thus inevitably invites heuristic approach to find the solution. In this paper, we report a heuristic algorithm, called BetaSCP2, which quickly finds an excellent solution of the SCP-problem. The solution process of the BetaSCP2 is facilitated by the Voronoi diagram and its dual structure called the quasi-triangulation. The BetaSCP2 is entirely implemented using the Molecular Geometry engine called BULL! which has been developed by Voronoi Diagram Research Center (VDRC) in C++ programming language. The benchmark test of the BetaSCP2 with other programs is also provided. The BetaSCP2 program is available as both a stand-alone and a web server program from VDRC.