Protein Folding and NP-Completeness

[cobalt124]

I'm looking to understand how protein folding has been shown to be NP-complete, but from the computational side rather than the biological side (if this is possible). Is there an analogous NP-complete problem that is similar? I read that self avoiding random walks might have something to do with it, but I can't visualise how. Maybe a simple introduction/model to/of protein folding would help (if one exists).

 

[jedishrfu]

My understanding of protein folding is that given a string of amino acids linked together as a string of beads you must try to fold it into a stable structure of lowest energy.

To do this then you would start by adjusting the degrees of freedom of each amino acid link which may take on any value within an angular range. The angular range is the limit is established by one amino bead colliding with another bead.

The sequence order of adjustment and the value of the angles would correspond to a traveling salesman
Selecting the starting city and the direction of travel.

It may be that you will have go through several adjustments for each link as you attempt to properly fold the structure.

 

[cobalt124]

Thankyou that looks like a foot in the door. I did come across traveling salesman when I was reading but forgot because I didn't understand the biology it was being related to. Going to do some further reading starting from your analogy see where I get.

 

[jedishrfu]

Here’s a diagram of the dihedral angles of protein folding.

https://goo.gl/images/AeBCZL

So for each connecting point you have two angles that can be adjusted. In some cases, the angle may be invalid because the protein string may have collided. As an example, if you have a string of pearls then bend them so far before one pearl collides with another. That test would be part of your fitness function if you were using genetic algorithms to solve the folding.

You might find a better description on Wikipedia.

 

[jedishrfu]

I fund this video talk on protein folding that could get you started conceptwise:



and this one that gets into the details:

 

[cobalt124]

OK I've managed to narrow down what I am looking for. I maybe should have been more specific in my initial question, but I was less wise then. I'm trying to write a simple to understand explanation of PvsNP and my example NP problems are to be traveling salesman and protein folding. I want to show explicitly how the input string on a Turing Machine would grow exponentially in relation to the number of cities/amino acids. This I understand with Travelling Salesman. For protein folding I've had another search starting from the links above and have come up with two possible ways of explaining simply how protein folding is NP-Complete. The first is from:

http://www.brown.edu/Research/Istrail_Lab/papers/1998/p30-berger.pdf

which shows a complicated proof for a simple model of protein folding using a self avoiding walk on a 3D lattice being NP-Complete. This is a simple to understand model, but I can't extract a correspondingly simple explanation of why it would be NP-Complete using the Turing Machine model. The other approach is the one suggested for Travelling Salesman above:

Nodes are cities, edges are distances between cities, find the minimum distance from a starting city to visit a list of cities

Is there an analogous statement for a simple protein folding model:

Nodes are all the possible folded configurations, edges are the change in energy levels between folds, find the minimum energy level configuration. The "starting city" is a string of amino acids.

This looks different to Travelling Salesman, is an analogy like this too simple, or even possible? I may have misunderstood what was being said. Though given the two examples I am using this might be the better approach.