Abstract
Inspired by the NP-hardness of string folding problems modeling the natural process of protein folding, we discuss the idea of solving instances of NP-hard problems (e.g., string folding problems) of moderate size by letting artificially assembled proteins to fold. The accuracy with which one can combinatorially model the protein folding process, e.g., by string folding, as well as the precision with which one could experimentally estimate the energy of folded artificial proteins are crucial issues.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Atkins, P., de Paula, J.: Elements of Physical Chemistry, 4th edn. Oxford University Press, Oxford (2005)
Berger, B., Leighton, T.: Protein folding in the hydrophobic-hydrophilic (HP) model is NP-complete. In: Proceedings of the RECOMB 1998, New York (1998)
Crescenzi, P., Goldman, D., Papadimitriou, C.H., Piccolboni, A., Yannakakis, M.: On the complexity of protein folding. J. Comput. Biol. 5(3), 423–466 (1998)
Dessmark, A., Lingas, A., Lundell, E.-M.: Subexponential-time framework for optimal embeddings of graphs in integer lattices. In: Hagerup, T., Katajainen, J. (eds.) SWAT 2004. LNCS, vol. 3111, pp. 248–259. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-27810-8_22
Dill, K.A.: Theory for the folding and stability of globular proteins. Biochemistry 24, 1501 (1985)
Fu, B., Wang, W.: A \(2^{O(n^{1-{1\over d}}\log n)}\) time algorithm for d-dimensional protein folding in the HP-model. In: DÃaz, J., Karhumäki, J., Lepistö, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol. 3142, pp. 630–644. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-27836-8_54
Irbäck., A.: Personal communication, 2019 December
Levinthal, C.: Are there pathways for protein folding? Journal de Chimie Physique et de Physico-Chimie Biologique 65, 44–45 (1968)
Mauri, G., Pavesi, G., Piccolboni, A.: Approximation algorithms for protein folding prediction. In: Proceedings of the SODA 1999, pp. S945–S946 (1999)
Nayak, A., Sinclair, A., Zwick, U.: Spatial codes and the hardness of string folding problems (extended abstract). In: Proceedings of the SODA 1998, pp. 639–648 (1998)
Paterson, M., Przytycka, T.: On the complexity of string folding. In: Meyer, F., Monien, B. (eds.) ICALP 1996. LNCS, vol. 1099, pp. 658–669. Springer, Heidelberg (1996). https://doi.org/10.1007/3-540-61440-0_167
Acknowledgements
The author is thankful to Eva-Marta Lundell and Mia Persson for some preliminary discussions and to Anders Irbäck for answering my question on the temperatures required by Conjecture 1. The research has been supported in part by Swedish Research Council grant 621-2017-03750.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Lingas, A. (2020). Solving Hard Problems by Protein Folding?. In: MartÃn-Vide, C., Vega-RodrÃguez, M.A., Yang, MS. (eds) Theory and Practice of Natural Computing. TPNC 2020. Lecture Notes in Computer Science(), vol 12494. Springer, Cham. https://doi.org/10.1007/978-3-030-63000-3_3
Download citation
DOI: https://doi.org/10.1007/978-3-030-63000-3_3
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-62999-1
Online ISBN: 978-3-030-63000-3
eBook Packages: Computer ScienceComputer Science (R0)