Is protein folding NP-hard and how to prove that?


This question has two facets that are related.

Is the general problem of protein folding really NP-hard?

The hydrophobic-polar protein folding model (Ken Dill et al., 1985) stated the problem on a lattice (similar to self-avoiding walk):

Simplification significantly reduces the computational effort in handling the model, although even in this simplified scenario the protein folding problem is NP-complete.

However, this simplification takes a problem which has some local convexity characteristics in real life, since protein folding can be thought as the problem of finding the global minimum on some energy "cost function", also known as the enemy landscape that was illustrated by Ken Dill et al., 2012:

enter image description here

As stated by others, translating a problem defined over continuous domain into problems over the integers or a binary lattice may introduce higher complexity cost. You may think about it as taking a linear problem and solve it using 3SAT solver, any problem in $ P$ is presumably reducible to 3SAT. I assume that there is a convex nature to the energy landscape, and this piecewise convexity is beneficial for the search for the minimal energy state.

How to reduce hydrophobic-polar protein folding to TSP/3SAT/CNF?

The work by Bahi et al. really confused me. I expected it to be something relatively simple to reduce 3SAT or TSP to the problem of protein lattice, because intuitively it seems that finding Hamiltonian path could be stated as finding a protein conformation on a lattice.

Bahi, Jacques M., et al. Computational investigations of folded self-avoiding walks related to protein folding. Computational biology and chemistry 47 (2013): 246-256.

Bahi, Jacques M., et al. Chaos of protein folding. In IJCNN 2011, Int. Joint Conf. on Neural Networks, pages 1948–1954, San Jose, California, United States, July 2011.

Bahi, Jacques M., et al. Protein folding in the 2D hydrophobic-hydrophilic (HP) square lattice model is chaotic. Cognitive Computation, 4(1):98–114, 2012.

Bahi, Jacques M., et al. Is protein folding problem really a NP-complete one ? First investigations. arXiv:1306.1372, October 2012. Submitted to Journal of Bioinformatics and Computational Biology (Elsevier).

Bahi, Jacques M., et al. Unfoldable self-avoiding walks are infinite. Consequences for the protein structure prediction problem. arXiv.org, 2013.

Bahi, Jacques M., et al. Protein structure prediction software generate two different sets of conformations. Or the study of unfolded self-avoiding walks. arXiv:1306.1439, 2013.