Abstract
Simplified protein models are used for investigating general properties of proteins and principles of protein folding. Furthermore, they are suited for hierarchical approaches to protein structure prediction. A well known protein model is the HP-model of Lau and Dill [Lau, K. F., & Dill, K. A. (1989)]. A lattice statistical mechanics model of the conformational and sequence spaces of proteins. Macromolecules, 22, 3986–3997) which models the important aspect of hydrophobicity. One can define the HP-model for various lattices, among them two-dimensional and three-dimensional ones. Here, we investigate the three-dimensional case. The main motivation for studying simplified protein models is to be able to predict model structures much more quickly and more accurately than is possible for real proteins. However, up to now there was a dilemma: the algorithmically tractable, simple protein models can not model real protein structures with good quality and introduce strong artifacts.
We present a constraint-based method that largely improves this situation. It outperforms all existing approaches for lattice protein folding in HP-models. This approach is the first one that can be applied to two three-dimensional lattices, namely the cubic lattice and the face-centered-cubic (FCC) lattice. Moreover, it is the only exact method for the FCC lattice. The ability to use the FCC lattice is a significant improvement over the cubic lattice. The key to our approach is the ability to compute maximally compact sets of points (used as hydrophobic cores), which we accomplish for the first time for the FCC lattice.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Abkevich, V. I., Gutin, A. M., & Shakhnovich, E. I. (1995). Impact of local and non-local interactions on thermodynamics and kinetics of protein folding. Journal of Molecular Biology, 252, 460–471.
Abkevich, V. I., Gutin, A. M., & Shakhnovich, E. I. (1997). Computer simulations of prebiotic evolution. In Proc. of the Pacific Symposium on Biocomputing (PSB'97), pp. 27–38.
Agarwala, R., Batzoglou, S., Dancik, V., Decatur, S. E., Farach, M., Hannenhalli, S., Muthukrishnan, S., et al. (1997). Local rules for protein folding on a triangular lattice and generalized hydrophobicity in the HP-model. Journal of Computational Bioliology, 4(2), 275–296.
Backofen, R. (1999). Optimization techniques for the protein structure prediction problem. Habilitationsschrift. University of Munich.
Backofen, R. (2000). An upper bound for number of contacts in the HP-model on the facecentered-cubic lattice (FCC). In Proc. of the 11th Annual Symposium on Combinatorial Pattern Matching (CPM2000). Lecture Notes in Computer Science, Vol. 1848. Berlin. pp. 277–292.
Backofen, R. (2001). The protein structure prediction problem: A constraint optimization approach using a new lower bound. Constraints, 6, 223–255.
Backofen, R. (2003). A polynomial time upper bound for the number of contacts in the HP-model on the face-centered-cubic lattice (FCC). Journal of Discrete Algorithms.
Backofen, R., & Will, S. (1999). Excluding symmetries in constraint-based search. In Proc. of 5th International Conference on Principle and Practice of Constraint Programming (CP'99). Lecture Notes in Computer Science, Vol. 1713. Berlin. pp. 73–87.
Backofen, R., & Will, S. (2001a). Fast, constraint-based threading of HP-sequences to hydrophobic cores. In Proc. of 7th International Conference on Principle and Practice of Constraint Programming (CP'2001). Lecture Notes in Computer Science, Vol. 2239. Berlin.
Backofen, R., & Will, S. (2001b). Optimally compact finite sphere packings—hydrophobic cores in the FCC. In Proc. of the 12th Annual Symposium on Combinatorial Pattern Matching (CPM 2001). Lecture Notes in Computer Science, Vol. 2089. Berlin.
Backofen, R., & Will, S. (2002). Excluding symmetries in constraint-based search. Constraints, 7(3), 333–349.
Backofen, R., Will, S., & Clote, P. (2000). Algorithmic approach to quantifying the hydrophobic force contribution in protein folding. In Pacific Symposium on Biocomputing (PSB 2000). 5, 92–103.
Bagci, Z., Jernigan, R. L., & Bahar, I. (2002a). Residue coordination in proteins conforms to the closest packing of spheres. Polymer, 43, 451–459.
Bagci, Z., Jernigan, R. L., & Bahar, I. (2002b). Residue packing in proteins: Uniform distribution on a coarse-grained scale. Journal of Chemical Physics, 116, 2269–2276.
Berger, B., & Leighton, T. (1998). Protein folding in the hydrophobic-hydrophilic (HP) model is NP-complete. In Proc. of the Second Annual International Conference on Research in Computational Molecular Biology (RECOMB'98), pp. 30–39.
Bornberg-Bauer, E. (1997). Chain growth algorithms for HP-type lattice proteins. In Proc. of the First Annual International Conference on Research in Computational Molecular Biology (RECOMB'97), pp. 47–55.
Bornberg-Bauer, E., & Chan, H. S. (1999). Modeling evolutionary landscapes: mutational stability, topology, and superfunnels in sequence space. PNAS, 96(19), 10689–10694.
Chan, H. S., & Dill, K. A. (1990). The effects of internal constraints on the configurations of chain molecules. Journal Chemical Analysis, 92, 3118–3135.
Cipra, B. (1998). Packing challenge mastered at last. Science, 281, 1267.
Crescenzi, P., Goldman, D., Papadimitriou, C., Piccolboni, A., & Yannakakis, M. (1998). On the complexity of protein folding. In Proc. of STOC, pp. 61–62.
Cui, Y., Wong, W. H., Bornberg-Bauer, E., & Chan, H. S. (2002). Recombinatoric exploration of novel folded structures: A heteropolymer-based model of protein evolutionary landscapes. PNAS, 99(2), 809–814.
Dill, K. A., Bromberg, S., Yue, K., Fiebig, K. M., Yee, D. P., Thomas, P. D., & Chan, H. S. (1995). Principles of protein folding—a perspective of simple exact models. Protein Sci., 4, 561–602.
Dill, K. A., Fiebig, K. M., & Chan, H. S. (1993). Cooperativity in protein-folding kinetics. PNAS 90, 1942–1946.
Dinner, A. R., Šali, A., & Karplus, M. (1996). The folding mechanism of larger model proteins: Role of native structure. PNAS, 93(16), 8356–8361.
Dovier, A., Burato, M., & Fogolari, F. (2002). Using secondary structure information for protein folding in CLP(FD). In Proc. of Workshop on Functional and Constraint Logic Programming. ENTCS Vol. 76.
Freuder, E. C. (1982). A sufficient condition for backtrack-free search. Journal of the ACM, 29, 24–32.
Govindarajan, S., & Goldstein, R. A. (1997). The foldability landscape of model proteins. Biopolymers, 42(4), 427–438.
Hart, W. E., & Istrail, S. (1997). Lattice and off-lattice side chain models of protein folding: Linear time structure prediction better than 86% of optimal. Journal of Molecular Biology, 4(3), 241–259.
Hart, W. E., & Istrail, S. C. (1996). Fast protein folding in the hydrophobic-hydrophilic model within three-eighths of optimal. Journal Computer Biology, 3(1), 53–96.
Hinds, D. A., & Levitt, M. (1996). From structure to sequence and back again. Journal Molecular Biology, 258, 201–209.
Kaya, H., & Chan, H. S. (2000). Energetic components of cooperative protein folding. Physics Review Letter, 85(22), 4823–4826.
Koehl, P., & Levitt, M. (1999). A brighter future for protein structure prediction. National Structunal Biology, 6, 108–111.
Lau, K. F., & Dill, K. A. (1989). A lattice statistical mechanics model of the conformational and sequence spaces of proteins. Macromolecules, 22, 3986–3997.
Li, H., Helling, R., Tang, C., & Wingreen, N. (1996). Emergence of preferred structures in a simple model of protein folding. Science, 273, 666–669.
MacDonald, D., Joseph, S., Hunter, D. L., Moseley, L. L., Jan, N., & Guttmann, A. J. (2000). Self-avoiding walks on the simple cubic lattice. Journal of Physics A: Math. Gen., 33, 5973–5983.
Madras, N., & Slade, G. (1993). The self-avoiding walk. Boston: Birkhäuser, 425 pp.
Ortiz, A. R., Kolinski, A., & Skolnick, J. (1998). Combined multiple sequence reduced protein model approach to predict the tertiary structure of small proteins. In Proc. of the Pacific Symposium on Biocomputing 1998 (PSB'98). 3, 375–386.
Park, B. H., & Levitt, M. (1995). The complexity and accuracy of discrete state models of protein structure. Journal Molecular Biology, 249, 493–507.
Regin, J.-C. (1994). A filtering algorithm for constraints of difference. In Proc. of the 12th National Conference of the American Association for Artificial Intelligence, pp. 362–367.
Shakhnovich, E. I., & Gutin, A. M. (1990). Enumeration of all compact conformations of copolymers with random sequence of links. Journal Chemical Physics, 8, 5967–5971.
Sloane, N. J. A. (1998). Kepler's conjecture conformed. Nature, 395(6701), 435–436.
Smolka, G. (1995). The Oz programming model. In Computer Science Today. Lecture Notes in Computer Science, pages 324–343. Berlin Heidelberg New York: Springer-Verlag.
Unger, R., & Moult, J. (1996). Local interactions dominate folding in a simpleprotein model. Journal Molecular Biology, 259, 988–994.
Šali, A., Shakhnovich, E., & Karplus, M. (1994). Kinetics of protein folding. Journal Molecular Biology, 235, 1614–1636.
Will, S. (2002). Constraint-based hydrophobic core construction for protein structure prediction in the face-centered-cubic lattice. In Proc. of the Pacific Symposium on Biocomputing 2002 (PSB 2002). Singapore.
Xia, Y., Huang, E. S., Levitt, M., & Samudrala, R. (2000). Ab initio construction of protein tertiary structures using a hierarchical approach. Journal Molecular Biology, 300, 171–185.
Yue, K., & Dill, K. A. (1993). Sequence-structure relationships in proteins and copolymers. Physics Review E, 48(3), 2267–2278.
Yue, K., & Dill, K. A. (1995). Forces of tertiary structural organization in globular proteins. PNAS, 92, 146–150.
Yue, K., Fiebig, K. M., Thomas, P. D., Chan, H. S., Shakhnovich, E. I., & Dill, K. A. (1995). A test of lattice protein folding algorithms. PNAS, 92(1), 325–329.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Backofen, R., Will, S. A Constraint-Based Approach to Fast and Exact Structure Prediction in Three-Dimensional Protein Models. Constraints 11, 5–30 (2006). https://doi.org/10.1007/s10601-006-6848-8
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10601-006-6848-8