Residue-rotamer-reduction for fast protein side-chain conformation prediction

Energy minimization is a widely used technique for predicting protein side-chain conformation as well as determining amino acid sequences that fold to desired three-dimensional structures. When the side-chain rotations are allowed to take continuous values, these energy minimization problems become intractable. For this reason, rotamer libraries have recently been proposed and minimization is carried out by assuming that each residue will assume one of its "statistically significant conformations." However, even this problem is known to be NP-hard and remains very challenging to solve. Amongst the algorithms that have been proposed for this important problem, "dead-end-elimination" [1] and its variants are currently the most efficient. However, the efficiency of these algorithms deteriorates significantly for large proteins and when realistic potential energy functions are employed. In this work, we develop a novel algorithmic to predict side-chain conformations of realistic size proteins. In particular, a residue-rotamer- reduction (R3) algorithm is proposed that integrates residue reduction and rotamer reduction for the first time, in contrast to traditional dead-end-elimination methods that only focus on rotamer reduction. We also describe the data structures that are needed for an efficient implementation of our algorithm. The implementation results in the R3P package that we provide free to the research community. Computational results are presented on a set of test problems from the literature for which R3P is compared with a mixed-integer linear programming formulation [2] and the widely used SCWRL 3.0 package [3]. These results show that R3P is one to two orders of magnitude faster than the mixed-integer linear programming formulation and SCWRL 3.0. Furthermore, our approach is capable of solving in a few seconds even the largest test protein with about 2,000 residues. The predicted side-chain dihedral angles are comparable to those reported in the literature [2] and also close to those in the crystal structures.