Exact methods for lattice protein models

Mann, M.; Backofen, R.

doi:10.1515/bams-2014-0014

Artykuł - szczegóły

Tytuł artykułu

Exact methods for lattice protein models

Autorzy

Mann M. , Backofen R.

Wybrane pełne teksty z tego czasopisma

Identyfikatory

DOI

10.1515/bams-2014-0014

Warianty tytułu

Języki publikacji

Abstrakty

Lattice protein models are well-studied abstractions of globular proteins. By discretizing the structure space and simplifying the energy model over regular proteins, they enable detailed studies of protein structure formation and evolution. However, even in the simplest lattice protein models, the prediction of optimal structures is computationally difficult. Therefore, often, heuristic approaches are applied to find such conformations. Commonly, heuristic methods find only locally optimal solutions. Nevertheless, there exist methods that guarantee to predict globally optimal structures. Currently, only one such exact approach is publicly available, namely the constraint-based protein structure prediction method and variants. Here, we review exact approaches and derived methods. We discuss fundamental concepts like hydrophobic core construction and their use in optimal structure prediction, as well as possible applications like combinations of different energy models.

Słowa kluczowe

CPSP HP-model lattice protein optimal structure protein structure prediction

Wydawca

Uniwersytet Jagielloński - Collegium Medicum
Index Copernicus Sp. z o.o.

Czasopismo

Bio-Algorithms and Med-Systems

Rocznik

2014

Tom

Vol. 10, no. 4

Strony

213--225

Opis fizyczny

Bibliogr. 95 poz., rys., wykr.

Twórcy

autor

Mann M.

mmann@informatik.uni-freiburg.de

Bioinformatics Group, Department of Computer Science, University of Freiburg, Freiburg, Germany

autor

Backofen R.

backofen@informatik.uni-freiburg.de

Bioinformatics Group, Department of Computer Science, University of Freiburg, Freiburg, Germany
Center for Biological Signaling Studies (BIOSS), University of Freiburg, Freiburg, Germany
Center for Biological Systems Analysis (ZBSA), University of Freiburg, Freiburg, Germany
Center for Non-coding RNA in Technology and Health, University of Copenhagen, Frederiksberg C, Denmark

Bibliografia

1. Tyers M, Mann M. From genomics to proteomics. Nature 2003;422:193-7.
2. Anfinsen CB. Principles that govern the folding of protein chains. Science 1973:181:223-30.
3. Crippen GM. Prediction of protein folding from amino acid sequence over discrete conformation spaces. Biochemistry 1991;30:4232-7.
4. Jefferys B, Kelley L, Sternberg MJ. Protein folding requires crowd control in a simulated cell. J Mol Biol 2010;397:1329-38.
5. Wittung-Stafshede P. Role of cofactors in protein folding. Ace Chem Res 2002:35:201-8.
6. Ying BW, Taguchi H, Ueda T. Co-translational binding of groel to nascent potypeptides is followed by post-translational encapsulation by GroES to mediate protein folding. J Biol Chem 2006;281:21813-9.
7. Clark PL. Protein folding in the cell: reshaping the folding funnel. Trends Biochem Sci 2004;29:527-34.
8. Rose GD, Fleming PJ, Banavar JR, Maritan A. A backbone- based theory of protein folding. Proc Natl Acad Sci USA 2O06;103:16623-33.
9. Smith A. Protein misfolding. Special Insight issue on protein misfolding edited by A. Smith. Nature 2003:426:883-909.
10. Lauren J, Gimbel DA, Nygaard HB, Gilbert JW, Strittmatter SM. Cellular prion protein mediates impairment of synaptic plasticity by amyloid-P oligomers. Nature 2009;457:1128-32.
11. Nunnally BK, Krull IS, editors. Prions and mad cow disease. New York: CRC Press, 2003.
12. Prusiner SB. Prions. Proc Natl Acad Sci USA 1998:95:13363-83.
13. Scott MD, Frydman J. Aberrant protein folding as the molecular basis of cancer. In: Bross, Peter and Gregersen, Niels, editors. Protein misfolding and disease, vol. 232 of Methods in molecular biology. San Francisco, California: Humana Press, 2003:67-76.
14. Karplus M, Kuriyan J. Molecular dynamics and protein function. Proc Natl Acad Sci USA 2005:102:6679-85.
15. Angelani L, Ruocco G. Saddles of the energy landscape and folding of model proteins. Europhys Lett 2009:87:18002.
16. Lau KF, Dill KA. A lattice statistical mechanics model of the conformational and sequence spaces of proteins. Macromolecules 1989:22:3986-97.
17. Finkelstein AV, Badretdinov AY. Rate of protein folding near the point of thermo-dynamic equilibrium between the coil and the most stable chain fold. Fold Des 1997;2:115-21.
18. Berger B, Leighton T. Protein folding in the hydrophobic-hydrophilic (HP) model is NP-complete. J Comp Biol 1998;5:27-40.
19. Crescenzi P, Goldman D, Papadimitriou C, Piccolboni A, Yannakakis M. On the complexity of protein folding. J Comput Biol 1998:5:423-65.
20. Irback A, Sandelin E. On hydrophobicity correlations in protein chains. BiophysJ 2000:79:2252-8.
21. Ullah AD, Kapsokalivas L, Mann M, Steinhofel K. Protein folding simulation by two-stage optimization. In: Cai, Zhihua and Li, Zhenhua and Kang, Zhuo and Liu, Yong, editors. Proc. of ISICA'09, vol. 51 of CCIS, Wuhan, China. Heidelberg, Berlin: Springer, 2009:138-45.
22. Ullah AD, Steinhoofel K. A hybrid approach to protein folding problem integrating constraint programming with local search. BMC Bioinform 2010;ll:S39.
23. Perdomo-Ortiz A, Dickson N, Drew-Brook M, Rose G, Aspuru-Guzik A. Finding low-energy conformations of lattice protein models by quantum annealing. Sci Rep 2012;2:571.
24. Nardelli M, Tedesco L, Bechini A. Cross-lattice behavior of general ACO folding for proteins in the HP model. In: Proceedings of the 28th annual ACM symposium on applied computing, SAC'13, Coimbra, Portugal. New York, NY, USA: ACM, 2013:1320-7.
25. Tsay J-J, Su S-C. An effective evolutionary algorithm for protein folding on 3D FCC HP model by lattice rotation and generalized move sets. Proteome Sci 2013;ll:S19.
26. Liu J, Song B, Liu Z, Huang W, Sun Y, Liu W. Energy-landscape paving for prediction of face-centered-cubic hydrophobic-hydrophilic lattice model proteins. Phys Rev E 2013:88:052704.
27. Dotu I, Cebrian M, van Hentenryck P, Clote P. Protein structure prediction with large neighborhood constraint programming search. In: Proc of CP'08, vol. 5202 of LNCS. Heidelberg, Berlin: Springer, 2008:82-96.
28. Dotu I, Cebrian M, van Hentenryck P, Clote P. On lattice protein structure prediction revisited. IEEE/ACM Trans Comput Biol Bioinform 2011;8:1620-32.
29. Dal Palu A, Dovier A, Fogolari F. Constraint logic programming approach to protein structure prediction. BMC Bioinform 2004:5:186.
30. Dal Palu A, Dovier A, Pontelli E. A constraint solver for discrete lattices, its parallelization, and application to protein structure prediction. Softw Pract Exp 2007:37:1405-49.
31. Dal Palu A, Dovier A, Pontelli E. Computing approximate solutions of the protein structure determination problem using global constraints on discrete crystal lattices. J Data Mining Bioinform 2010:4:1-20.
32. Citrolo AG, Mauri G. A local landscape mapping method for protein structure prediction in the HP model. Nat Comput 2014:13:309-19.
33. Maher B, Albrecht AA, Loomes M, Yang X-S, Steinhfel K. A firefly-inspired method for protein structure prediction in lattice models. Biomolecules 2014;4:56-75.
34. Rashid MA, Newton MH, Hoque MT, Shatabda S, Pham D, Sattar A. Spiral search: a hydrophobic-core directed local search for simplified PSP on 3D FCC lattice. BMC Bioinform 2013;14:S16.
35. Shatabda S, Newton MA, Pham DN, Sattar A. A hybrid local search for simplified protein structure prediction. In: International conference on bioinformatics models, methods and algorithms, 2013:6.
36. Hart WE, Istrail SC. Fast protein folding in the hydrophobic-hydrophilic model within three-eighths of optimal. J Comput Biol 1996:3:53-96.
37. Newman A. A new algorithm for protein folding in the HP model. In: Proceedings of the thirteenth annual ACM-SIAM symposium on discrete algorithms, San Francisco, California. PA, USA: Society for Industrial and Applied Mathematics Philadelphia, 2002.
38. Hart WE, Istrail SC. Lattice and off-lattice side chain models of protein folding: linear time structure prediction better than 86% of optimal. J Comput Biol 1997:4:241-59.
39. Heun V. Approximate protein folding in the HP side chain model on extended cubic lattices. Discrete Appl Math 2003:127:163-77.
40. Hart W, Newman A. Protein structure pre-diction with lattice models. In: Handbook of molecular biology. Chapman & Hall, editors. CRC Computer and Information Science Series. New York: CRC Press, 2006:1-24.
41. Istrail S, Lam F. Combinatorial algorithms for protein folding in lattice models: a survey of mathematical results. Commun Inf Syst 2009:9:303-46.
42. Yue K, Dill KA. Forces of tertiary structural organization in globular proteins. Proc Natl Acad Sci USA 1995;92:146-50.
43. Backofen R, Will S. A constraint-based approach to fast and exact structure prediction in three-dimensional protein models. Constraints 2006;ll:5-30.
44. Mann M, Smith C, Rabbath M, Edwards M, Will S, Backofen R. CPSP-web-tool: a server for 3D lattice protein studies. Bioinformatics 2009:25:676-7.
45. Mann M, Will S, Backofen R. CPSP-tools - exact and complete algorithms for high-throughput 3D lattice protein studies. BMC Bioinform 2008;9:230.
46. Backofen R, Will S, Bornberg-Bauer E. Application of constraint programming techniques for structure prediction of lattice proteins with extended alphabets. Bioinformatics 1999:15:234-42.
47. Bornberg-Bauer E. Chain growth algorithms for HP-type lattice proteins. In: Proceedings of RECOMB'97, Santa Fe, New Mexico, USA:ACM, 1997:47-55.
48. Rashid MA, Newton MH, Hoque MT, Sattar A. Mixing energy models in genetic algorithms for on-lattice protein structure prediction. Biomed Res Int 2013;2013:15.
49. Mann M, Backofen R, Will S. Equivalence classes of optimal structures in HP protein models including side chains. In: Proceedings of the fifth workshop on constraint based methods for bioinformatics (WCB09), 2009.
50. Mann M. Computational methods for lattice protein models. PhD thesis, Albert-Ludwigs-University Freiburg, 2011. Available at: http://www.freidok.uni-freiburg.de/volltexte/8156/. Accessed on 29 October, 2014.
51. Park B, Levitt M. The complexity and accuracy of discrete state models of protein structure. J Mol Biol 1995;249:493-507.
52. Mann M, Dal Palŭ A. Lattice model refinement of protein structures. In: Proc of WCB'10, 2010:7, arXiv:1005.1853.
53. Mann M, Saunders R, Smith C, Backofen R, Deane CM. Producing high-accuracy lattice models from protein atomic co-ordinates including side chains. Adv Bioinform 2012;2012:6.
54. Unger R, Moult J. Finding the lowest free energy conformation of a protein is an NP-hard problem: proof and implications. Bull Math Biol 1993:55:1183-98.
55. Ngo JT, Marks J. Computational complexity of a problem in molecular structure prediction. Protein Engl992;5:313-21.
56. Perunov N, England JL. Quantitative theory of hydrophobic effect as a driving force of protein structure. Protein Sci 2014:23:387-99.
57. Pace C, Shirley B, McNutt M, Gajiwala K. Forces contributing to the conformational stability of proteins. FASEB J 1996;10:75-83.
58. Dill KA, Bromberg S, Yue K, Fiebig KM, Yee DP, Thomas PD, et al. Principles of protein folding - a perspective of simple exact models. Protein Sci 1995;4:561-602.
59. Li H, Helling R, Tang C, Wingreen N. Emergence of preferred structures in a simple model of protein folding. Science 1996:273:666-9.
60. Banavar JR, Cieplak M, Maritan A. Lattice tube model of proteins. Phys Rev Lett 2004;93:238101.
61. Hoque T, Chetty M, Sattar A. Extended HP model for protein structure prediction. J Comput Biol 2009;16:85-103.
62. Miyazawa S, Jernigan RL. Estimation of effective interresidue contact energies from protein crystal structures: quasi-chemical approximation. Macromolecules 1985;18:534-52.
63. Miyazawa S, Jernigan RL. Residue-residue potentials with a favorable contact pair term and an unfavorable high packing density term, for simulation and threading. J Mol Biol 1996:256:623-44.
64. Berrera M, Molinari H, Fogolari F. Amino acid empirical contact energy definitions for fold recognition in the space of contact maps. BMC Bioinform 2003;4:8.
65. Chan HS, Dill KA. Origins of structure in globular proteins. Proc Natl Acad Sci USA 1990:87:6388-92.
66. Vendruscolo M, Domany E. Pairwise contact potentials are unsuitable for protein folding. J Chem Phys 1998;109:11101-8.
67. Dal Palŭ A, Dovier A, Pontelli E. A new constraint solver for 3D lattices and its application to the protein folding problem. In: Proc. of logic for programming, artificial intelligence, and reasoning (LPAR'O5). Heidelberg, Berlin: Springer, 2005:48-63.
68. Pötzsch S, Scheuermann G, Wolfinger M, Flamm C, Stadler P. Visualization of lattice-based protein folding simulations. In: Proc. of V"06: conference on information visualization, Los Alamitos, CA, USAMEEE Computer Society, 2006:89-94.
69. Bornberg-Bauer E. Randomness, structural uniqueness, modularity and neutral evolution in sequence space of model proteins. Z Phys Chem 2002;216:139-54.
70. Citossi M, Guigliaretli G. Lattice protein models: a computational approach to folding and aggregation phenomena. In: Frontiers of fundamental physics, vol. IV. Netherlands: Springer, 2005:355-8.
71. Huard FP, Deane CM, Wood GR. Modelling sequential protein folding under kinetic control. Bioinformatics 2006;22:e203-10.
72. Saunders R, Mann M, Deane C. Signatures of co-translational folding. Special issue: Protein folding in vivo. Biotechnol J 2011;6:742-51.
73. Backofen R, Will S. Fast, constraint-based threading of HP-sequences to hydrophobic cores. In: Toby Walsh, editor. Proc. of the 7th international conference on principle and practice of constraint programming (CP'2001), vol. 2239 of LNCS, Paphos, Cyprus. Heidelberg, Berlin, Springer, 2001:494-508.
74. Will S. Exact, constraint-based structure prediction in simple protein models. PhD thesis, Friedrich-Schiller-Universitatjena, 2005. Available at http://www.bioinf.uni-freiburg.de/Publications/. Accessed on 29 October, 2014.
75. Backofen R, Will S. Structure prediction in an HP-type lattice with an extended alphabet. In: Proc. of German conference on bioinformatics (GCB'98), Koln, Germany, 1998.
76. CPSP-home. CPSP-tools: constraint-based protein structure prediction, 2008. Available as an open-source package from http://www.bioinf.uni-freiburg.de/sw/cpsp/. Accessed on 29 October, 2014.
77. CPSP-webtools. CPSP-webtools: constraint-based protein structure prediction webserver, 2009. Available at http://cpsp.informatik.uni-freiburg.de. Accessed on 29 October, 2014.
78. Mann M, Maticzka D, Saunders R, Backofen R. Classifying protein-like sequences in arbitrary lattice protein models using LatPack. Special issue on protein folding: experimental and theoretical approaches. HFSPJ 2008;2:396-404.
79. LatPack-home. LatPack: lattice protein folding package, 2008. Available as an open-source package from http://www.bioinf.uni-freiburg.de/Software/. Accessed on 29 October, 2014.
80. Rossi F, van Beek P, Walsh T. editors. Handbook of constraint programming (foundations of artificial intelligence). New York: Elsevier Science Inc., 2006.
81. Régin J-C. A filtering algorithm for constraints of difference in CSPs. In: Proc. of 12th national conference on At, Seattle, Washington, USA: American Association for Artificial Intelligence, 1994:362-7.
82. Backofen R, Will S. Excluding symmetries in constraint-based search. Constraints 2002;7:333-49.
83. Backofen R. Optimization techniques for the protein structure prediction problem. Habilitation. Ludwig-Maximilians-Universitat Miinchen, 2000. Available at: http://www.bioinf.uni-freiburg.de/Publications/. Accessed on 29 October, 2014.
84. Shortle D, Chan HS, Dill KA. Modeling the effects of mutations on the denatured states of proteins. Prot Sci 1992;l:201-15.
85. Backofen R. The protein structure prediction problem: a constraint optimisation approach using a new lower bound. Constraints 2001;6:223-55.
86. Backofen R. An upper bound for number of contacts in the HP-model on the face-centered-cubic lattice (FCC). In: Giancarto R, Sankoff D, editors. Proceedings of the 11th annual symposium on combinatorial pattern matching (CPM 2000), vol. 1848 of LNCS, Montreal, Canada. Berlin: Springer-Verlag, 2000:277-92.
87. Backofen R. A polynomial time upper bound for the number of contacts in the HP-model on the face-centered-cubic lattice (FCC). J Discr Alg 2004;2:161-206.
88. Backofen R, Will S. Optimally compact finite sphere packings - hydrophobic cores in the FCC. In: Amir A, Landau, GM, editors. Proc. of CPM'01, vol. 2089 of LNCS, Jerusalem, Israel. Berlin: Springer, 2001:257-72.
89. Will S. Constraint-based hydrophobic core construction for protein structure prediction in the face-centered-cubic lattice. In: Altman, Dunker, Hunter, Lauderdale & Klein, editors. Proc. of the Pacific symposium on biocomputing, Kauai, Hawaii. Singapore: World Scientific, 2002:661-72.
90. Kirkpatrick S, Gelatt CD, Vecchi MP. Optimization by simulated annealing. Science 1983;220:671-80.
91. Černy V. Thermodynamical approach to the traveling salesman problem: an efficient simulation algorithm. J Opt Theory Appl 1985:45:41-51.
92. Böckenhauer H-J, Ullah AZ, Kapsokalivas L, Steinhöfel K. A local move set for protein folding in triangular lattice models. In: Crandall KA, Lagergren), editors. Proc. of WABI '08, LNBI. Berlin: Springer, 2008:369-81.
93. Lesh N, Mitzenmacher M, Whitesides S. A complete and effective move set for simplified protein folding. In: Vingron, Martin and Istrail, Sorin and Pevzner, Pavel and Waterman, Michael. Proceedings of the seventh annual international conference on research in computational molecular biology (RECOMB'03), Berlin, Germany:ACM, 2003:188-95.
94. Bornberg-Bauer E, Beaussart F, Kummerfeld S, Teichmann S, Weiner J. The evolution of domain arrangements in proteins and interaction networks. Cell Mol Life Sci 2005;62: 435-45.
95. Bornberg-Bauer E, Chan HS. Modeling evolutionary landscapes: mutational stability, topology, and superfunnels in sequence space. Proc NatlAcad Sci USA1999;96:10689-94.

Typ dokumentu

Bibliografia

Identyfikator YADDA

bwmeta1.element.baztech-ee65d052-42c3-486f-8166-e5cd8e723105