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 continuous problem which has some local convexity characteristics in real life into an integer programming problem, because protein folding resembles the problem of finding the global minimum on some continuous energy "cost function", also known as the energy landscape as 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.

  • 1
    $\begingroup$ Not all simple to state problems have simple to state solutions. It is common for a simple-to-state theorem to have a complex proof. $\endgroup$
    – D.W.
    Jul 18 '20 at 18:06
  • $\begingroup$ @D.W. True, I am aiming to have the outline of a potential proof. $x^n+y^n=z^n$ $\endgroup$
    – 0x90
    Jul 18 '20 at 18:10
  • $\begingroup$ But don't papers in the literature already contain a proof that protein folding is NP hard? You can find citations to such papers in the ones you cited. It seems like they answer your first question. $\endgroup$
    – D.W.
    Jul 18 '20 at 19:24

It follows immediately from the fact that protein folding is NP-hard that there exists a reduction from 3SAT to protein folding. The definition of NP-hard says that there is a reduction from every NP problem to protein folding; and 3SAT is a NP problem.

There are papers in the literature that state that protein folding is NP-hard. I'm not an expert on them, so I don't know to what extent they do or don't address your specific concerns, but you should be able to find them immediately and review their proof. See, e.g.,

P. Crescenzi et al. "On the complexity of protein folding." Journal of computational biology 5.3 (1998): 423-465.

B. Berger et al. "Protein folding in the hydrophobic-hydrophilic (HP) is NP-complete." Proceedings of the second annual international conference on Computational molecular biology, pp. 30-39. 1998.

Our normal rules are to ask only one question per post.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.