An Experimental Analysis of the Performance of SideChain Packing Algorithms

ABSTRACT

This paper presents a brief description of the protein side chain packing problem (PSCPP) and a performance assessment, on this problem, of three state-of-the-art algorithms: SCWRL4, OPUS-Rota, and CIS-RR. In order to perform a fair comparison, the algorithms are evaluated on three data sets, two of them were previously proposed in the literature and a set of 723 protein structures proposed here. Experimental results show that the achieved accuracy when evaluating the side chain's first torsion angle (χ₁) is of approximately 86% and around 69% for the first and the second torsion angles (χ₁₊₂), for all methods. Although all the algorithms achieve similar accuracies, SCWRL4 requires on average, less computation effort than the others. We highlight relevant aspects that need to be considered in order to verify whether or not this 86% is a theoretical upper bound for the algorithms' performance as well as what might become a promising direction to follow in case an improvement is possible.

References

1. T. Akutsu. Np-hardness results for protein side-chain packing. Genome Informatics, 8:180--186, 1997.
2. A. Canutescu, A. Shelenkov, and R. Dunbrack. A graph-theory algorithm for rapid protein side-chain prediction. Protein Science: A Publication of the Protein Society, 12(9):2001--2014, sep 2003. PMID: 12930999.
3. Y. Cao, L. Song, Z. Miao, Y. Hu, L. Tian, and T. Jiang. Improved side-chain modeling by coupling clash-detection guided iterative search with rotamer relaxation. Bioinformatics, jan 2011.
4. R. Das. 'Four small puzzles that Rosetta doesn't solve'. PLOS One, 6(5):e20044, 2011.
5. J. Desmet, M. Maeyer, B. Hazes, and I. Lasters. The dead-end elimination theorem and its use in side-chain positioning. Nature, 356:539--542, 1992.
6. R. Dunbrack and F. Cohen. Bayesian statistical analysis of protein side-chain rotamer preferences. Protein Science, 6:1661--1681, 1997.
7. R. Dunbrack and M. Karplus. Backbone-dependent rotamer library for proteins. application to side-chain prediction. Journal of Molecular Biology, 230:543--574, 1993.
8. P. Francis-Lyon and P. Koehl. Protein side-chain modeling with a protein-dependent optimized rotamer library. Proteins: Structure, Function, and Bioinformatics, 82(9):2000--2017, 2014.
9. P. Gainza, K. Roberts, and B. Donald. 'Protein Design Using Continuous Rotamers'. PLOS Computational Biology, (8):1--15, 2012.
10. T. Jain, D. Cerutti, and J. McCammon. Configurational-bias sampling technique for predicting side-chain conformations in proteins. Protein Science: A Publication of the Protein Society, 15(9):2029--2039, sep 2006. PMID: 16943441.
11. G. Krivov, M. Shapovalov, and R. Dunbrack. Improved prediction of protein side-chain conformations with SCWRL4. Proteins, 27(6):785--790, may 2009. PMID: 19603484.
12. Z. Li, Y. Yang, J. Zhan, L. Dai, and Y. Zhou. Energy functions in de novo protein design: Current challenges and future prospects. Annual Review of Biophysics, 42:315--335, 2013.
13. S. Liang and N. Grishin. Side-chain modeling with an optimized scoring function. Protein Science, 11(2):322--331, 2002.
14. S. Liang, D. Zheng, C. Zhang, and D. Standley. Fast and accurate prediction of protein side-chain conformations. Bioinformatics, 27(20):2913--2914, 2011.
15. S. Liang, Y. Zhou, N. Grishin, and D. Standley. Protein side chain modeling with orientation-dependent atomic force fields derived by series expansions. Journal of Computacional Chemistry, 32(8):1680--1686, jun 2011.
16. M. Lu, A. Dousis, and J. Ma. OPUS-Rota: a fast and accurate method for side-chain modeling. Protein Science, 17(9):1576--1585, 2008.
17. Z. Miao, Y. Cao, and T. Jiang. RASP: rapid modeling of protein side chain conformations. Bioinformatics, 27(22):3117--3122, sep 2011.
18. K. Nagata, A. Randall, and P. Baldi. Sidepro: A novel machine learning approach for the fast and accurate prediction of side-chain conformations. Proteins: Structure, Function, and Bioinformatics, 80(1):142--153, 2012.
19. L. X. Peterson, X. Kang, and D. Kihara. Assessment of protein side-chain conformation prediction methods in different residue environments. Proteins: Structure, Function, and Bioinformatics, 82(9):1971--1984, 2014.
20. R. Peterson, P. Dutton, and A. Wand. Improved side-chain prediction accuracy using an ab initio potential energy function and a very large rotamer library. Protein Science: A Publication of the Protein Society, 13(3):735--751, mar 2004. PMID: 14978310.
21. M. Shapovalov and R. Dunbrack. A smoothed backbone-dependent rotamer library for proteins derived from adaptive kernel density estimates and regressions. Bioinformatics, 19(22):844--858, jun 2011.
22. H. Venselaar, E. Krieger, and G. Vriend. Homology modeling. Structural Bioinformatics, pages 715--732, 2009.
23. P. Widera, J. M. Garibaldi, and N. Krasnogor. Gp challenge: Evolving energy function for protein structure prediction. Genetic Programming and Evolvable Machines, 11(1):61--88, Mar. 2010.
24. Z. Xianga and B. Honig. 'Extending the accuracy limits of prediction for side-chain conformations'. Journal of Molecular Biology, 311(2):421--430, 2001.

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Control methods

    • Search methodologies

• Theory of computation

  • Design and analysis of algorithms

    • Algorithm design techniques

      • Dynamic programming