Protein Structure Prediction with Large Neighborhood Constraint Programming Search

1. Abagyan, R.A., Totrov, M.M., Kuznetsov, D.A.: ICM: a new method for structure modeling and design: Applications to docking and structure prediction from the distorted native conformation. J. Comp. Chem. 15, 488–506 (1994)

   Article  Google Scholar 

2. Anfinsen, C.B.: Principles that govern the folding of protein chains. Science 181 (1973)

   Google Scholar 

3. Arnold, K., Bordoli, L., Kopp, J., Schwede, T.: The SWISS-MODEL workspace: a web-based environment for protein structure homology modelling. Bioinformatics 22(2) (2006)

   Google Scholar 

4. Backofen, R.: The protein structure prediction problem: A constraint optimization approach using a new lower bound. Constraints 6(2-3), 223–255 (2001)

   Article  MATH  MathSciNet  Google Scholar 

5. Backofen, R., Will, S., Bornberg-Bauer, E.: Application of constraint programming techniques for structure prediction of lattice proteins with extended alphabets. Bioinformatics 15(3), 234–242 (1999)

   Article  Google Scholar 

6. Backofen, R., Will, S., Clote, P.: Algorithmic approach to quantifying the hydrophobic force contribution in protein folding. In: Pacific Symposium on Biocomputing, vol. 5, pp. 92–103 (2000)

   Google Scholar 

7. Backofen, R.: Using constraint programming for lattice protein folding. In: Workshop on Constraints and Bioinformatics/Biocomputing (1997)

   Google Scholar 

8. Backofen, R., Will, S.: A constraint-based approach to structure prediction for simplified protein models that outperforms other existing methods. In: Palamidessi, C. (ed.) ICLP 2003. LNCS, vol. 2916, pp. 49–71. Springer, Heidelberg (2003)

   Google Scholar 

9. Berger, B., Leighton, T.: Protein folding in the hydrophobic-hydrophilic (hp) model is NP-complete. Journal of Computational Biology 5, 27–40 (1998)

   Article  Google Scholar 

10. Berman, H.M., Battistuz, T., Bhat, T.N., Bluhm, W.F., Bourne, P.E., Burkhardt, K., Feng, Z., Gilliland, G.L., Iype, L., Jain, S., Fagan, P., Marvin, J., Padilla, D., Ravichandran, V., Schneider, B., Thanki, N., Weissig, H., Westbrook, J.D., Zardecki, C.: The Protein Data Bank. Acta Crystallogr. D. Biol. Crystallogr. 58(Pt), 899–907 (2002)

    Article  Google Scholar 

11. Bornberg-Bauer, E.: Chain growth algorithms for HP-type lattice proteins. In: RECOMB, pp. 47–55. ACM Press, New York (1997)

    Chapter  Google Scholar 

12. Bradley, P., Misura, K.M., Baker, D.: Toward high-resolution de novo structure prediction for small proteins. Science 309(5742), 1868–1871 (2005)

    Article  Google Scholar 

13. Cebrian, M., Dotu, I., Van Hentenryck, P., Clote, P.: Protein Structure Prediction on the Face Centered Cubic Lattice by Local Search. In: AAAI 2008 (to appear, 2008)

    Google Scholar 

14. Brooks, B.R., Bruccoleri, R.E., Olafson, B.D., States, D.J., Swaminathan, S., Karplus, M.: CHARMM: A program for macromolecular energy, minimization, and dynamics calculations. J. Comput. Chem. 4, 187–217 (1983)

    Article  Google Scholar 

15. Cipra, B.: Packing challenge mastered at last. Science 281, 1267 (1998)

    Article  Google Scholar 

16. Conway, J.H., Sloane, N.J.A.: Sphere Packing, Lattices and Groups. Springer, Heidelberg (1998)

    Google Scholar 

17. Crescenzi, P., Goldman, D., Papadimitriou, C., Piccolboni, A., Yannakakis, M.: On the complexity of protein folding. J. Comp. Biol. 5(3), 523–466 (1998)

    Google Scholar 

18. Dal Palu, A., Dovier, A., Fogolari, F.: Constraint Logic Programming approach to protein structure prediction. BMC. Bioinformatics 5, 186 (2004)

    Article  Google Scholar 

19. Dalton, J.A., Jackson, R.M.: An evaluation of automated homology modelling methods at low target template sequence similarity. Bioinformatics 23(15), 1901–1908 (2007)

    Article  Google Scholar 

20. Duan, Y., et al.: A point-charge force field for molecular mechanics simulations of proteins based on condensed-phase quantum mechanical calculations. J. Comput. Chem. 24(16), 1999–2012 (2003)

    Article  Google Scholar 

21. Floudas, C.A.: Computational methods in protein structure prediction. Biotechnol. Bioeng. 97(2), 207–213 (2007)

    Article  Google Scholar 

22. Go, N., Taketomi, H.: Respective roles of short- and long-range interactions in protein folding. Proc. Natl. Acad. Sci. U.S.A. 75(2), 559–563 (1978)

    Article  Google Scholar 

23. Go, N., Taketomi, H.: Studies on protein folding, unfolding and fluctuations by computer simulation. III. Effect of short-range interactions. Int. J. Pept. Protein. Res. 13(3) (1979)

    Google Scholar 

24. Helles, G.: A comparative study of the reported performance of ab initio protein structure prediction algorithms. J. R. Soc. Interface 5(21), 387–396 (2008)

    Article  Google Scholar 

25. Holm, L., Sander, C.: Database algorithm for generating protein backbone and side-chain co-ordinates from a C alpha trace application to model building and detection of co-ordinate errors. J. Mol. Biol. 218(1), 183–194 (1991)

    Article  Google Scholar 

26. John, B., Sali, A.: Comparative protein structure modeling by iterative alignment, model building and model assessment. Nucleic. Acids. Res. 31(14), 3982–3992 (2003)

    Article  Google Scholar 

27. Klepeis, J.L., Floudas, C.A.: Prediction of β-sheet topology and disulfide bridges in polypeptides. Journal of Computational Chemistry 24(2), 191–208 (2002)

    Article  Google Scholar 

28. Kyte, J., Doolittle, R.F.: A simple method for displaying the hydropathic character of a protein. J. Mol. Biol. 157(1), 105–132 (1982)

    Article  Google Scholar 

29. Lam, P.Y., Jadhav, P.K., Eyermann, C.J., Hodge, C.N., Ru, Y., Bacheler, L.T., Meek, J.L., Otto, M.J., Rayner, M.M., Wong, Y.N., et al.: Rational design of potent, bioavailable, nonpeptide cyclic ureas as HIV protease inhibitors. Science 263(5145), 380–384 (1994)

    Article  Google Scholar 

30. Lathrop, R.H.: The protein threading problem with sequence amino acid interaction preferences is NP-complete. Protein. Eng. 7(9), 1059–1068 (1994)

    Article  Google Scholar 

31. Lathrop, R.H., Smith, T.F.: Global optimum protein threading with gapped alignment and empirical pair score functions. J. Mol. Biol. 255(4), 641–665 (1996)

    Article  Google Scholar 

32. Lau, K.F., Dill, K.A.: A lattice statistical mechanics model of the conformational and sequence spaces of proteins. Journal of the American Chemical Society 22 (1989)

    Google Scholar 

33. Madras, N., Slade, G.: The Self-Avoiding Walk. Probability and its Applications, 448 p. Birkhäuser, Boston (1996)

    MATH  Google Scholar 

34. Michel, L., See, A., Van Hentenryck, P.: Parallelizing Constraint Programs Transparently. In: Bessière, C. (ed.) CP 2007. LNCS, vol. 4741, pp. 514–528. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

35. Miyazawa, S., Jernigan, R.L.: Self-consistent estimation of inter-residue protein contact energies based on an equilibrium mixture approximation of residues. Proteins 34(1) (1999)

    Google Scholar 

36. Papadimitriou, C.: Computational Complexity. Addison Wesley, Reading (1994)

    MATH  Google Scholar 

37. Pokarowski, P., Kloczkowski, A., Jernigan, R.L., Kothari, N.S., Pokarowska, M., Kolinski, A.: Inferring ideal amino acid interaction forms from statistical protein contact potentials. Proteins 59(1), 49–57 (2005)

    Article  Google Scholar 

38. Shaw, P.: Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems. In: Maher, M.J., Puget, J.-F. (eds.) CP 1998. LNCS, vol. 1520. Springer, Heidelberg (1998)

    Chapter  Google Scholar 

39. Siew, N., Fischer, D.: Convergent evolution of protein structure prediction and computer chess tournaments: CASP, Kasparov, and CAFASP. IBM Systems Journal 40(2) (2001)

    Google Scholar 

40. Sippl, M.: Calculation of conformation ensembles from potentials of mean force. J. Mol. Biol. 213, 859–883 (1990)

    Article  Google Scholar 

41. Skolnick, J., Kolinski, A.: Simulations of the Folding of a Globular Protein. Science 250(4984), 1121–1125 (1990)

    Article  Google Scholar 

42. Taketomi, H., Kano, F., Go, N.: The effect of amino acid substitution on protein-folding and -unfolding transition studied by computer simulation. Biopolymers 27(4) (1988)

    Google Scholar 

43. Unger, R., Moult, J.: Genetic algorithms for protein folding simulations. Journal of Molecular Biology 231, 75–81 (1993)

    Article  Google Scholar 

44. Van Hentenryck, P., Michel, L.: Constraint-Based Local Search. The MIT Press, Cambridge (2005)

    Google Scholar 

45. Will, S.: Constraint-based hydrophobic core construction for protein structure prediction in the face-centered-cubic lattice. In: Pacific Symposium on Biocomputing (2002)

    Google Scholar 

46. Will, S.: Exact, Constraint-Based Structure Prediction in Simple Protein Models. In: PhD thesis, Friedrich-Schiller-Universität Jena (April 2005)

    Google Scholar 

47. Wu, S., Skolnick, J., Zhang, Y.: Ab initio modeling of small proteins by iterative TASSER simulations. BMC. Biol. 5, 17 (2007)

    Article  Google Scholar 

48. Yue, K., Dill, K.A.: Folding proteins with a simple energy function and extensive conformational searching. Protein. Sci. 5(2), 254–261 (1996)

    Article  Google Scholar 

49. Yue, K., Fiebig, K.M., Thomas, P.D., Chan, H.S., Shakhinovich, E.I., Dill, K.A.: A test of lattice protein folding algorithms. National Academy of Science 92, 325–329 (1995)

    Article  Google Scholar 

50. Zaki, M.J.: Protein Structure Prediction, 2nd edn. Humana Press (2007)

    Google Scholar 

51. Zhang, Y.: I-TASSER server for protein 3D structure prediction. Bioinformatics (2008)

    Google Scholar 

52. Zhang, Y., Skolnick, J.: The protein structure prediction problem could be solved using the current PDB library. Proc. Natl. Acad. Sci. U.S.A. 102(4), 1029–1034 (2005)

    Article  Google Scholar 

Download references