7 ms·

Not that I have the biology chops to contribute to it myself, but a Protein Folding != NP debate is exactly the kind of discussion I'd like to see here.

PieSquared 17y ago
I cannot agree more. Then it would get me off my butt and make me learn something about the topic, too.
- biohacker42 17y ago
  Well then lets get the ball rolling. There's a theory that protein folding is like a funnel. That is to say, the initial probability space is huge, much like the wide end of a funnel. But then it quickly collapses and the probability space becomes close enough to be computable by brute force. Now while there are some proteins that will unfold and then fold correctly again, most can't do that. Most don't start out as one long chain that then crumples in the right shape on its own. Most are carefully built from other parts, carefully guided along the desired path of entropy. And if they misfold, and that does happen, they are taken out. Now I personally have always thought of it as a simulation. Think about a can of mixed nuts. Have you ever noticed that the biggest kinds are always on top, and the smallest at the bottom? You might have to shake the can for a while but they will sort by size with the biggest on top. This is a function of friction and volume. If you shake a glass jar of mixed nuts, you can almost see a flow along the sides with the smaller ones flowing down and the bigger ones "floating" to the top. Imagine you were given the starting position of each nut, and the exact time and direction and force of the shaking of the jar. You are asked to write a simulation which will predict the final locations of each nut. If you think about a single threaded algorithm looking at each nut and how it nudges its neighbor and its neighbor and so on, it's a lot of calculations. But if you think of it a multi-threaded simulation then things get interesting.
  - PieSquared 17y ago
    Hah, wow, thanks for the layman's description. That made sense! It also triggered one of those 'holy crap I have so much to learn' moments, followed shortly by a 'what the hell am I doing wasting my time with all these silly things I do' moment. ;)
quantumhobbit 17y ago
Protein-folding can be expressed as a superset of molecular modeling(my area of research). In the strictest physical sense this is not a P problem if you consider the interactions of every atom with every other atom O(n!) for n atoms. No one does it that way of course. Once you ignore all but nearest neighbor interactions you have a problem that is polynomial time for n. Proteins have too many atoms for even these techniques to be efficient. Now we're getting out of my area. As I understand it researchers do a Monte Carlo search of all possible configurations of amino acids(or even protein segments). Naively searching the space of all configurations would be make this NP. Of course you don't have to search the entire space. You can limit each step to make small changes only from an initial configuration and stay along a Markov chain of probable intermediate steps. I don't know enough to say that this would always be solvable in polynomial time, and of course you could miss the true minimum answer. I'd love to hear from someone who knows more.
- adrianbg 17y ago
  I don't think a naive search would even be useful because finding globally minimal energy configurations isn't the goal. It's pretty unlikely that nature would happen to put such large systems as whole proteins in their lowest possible energy configurations when all that is really necessary is that they be stable (ie., locally minimal configurations). Especially if nature uses the tightly controlled folding process biohacker42 describes: http://news.ycombinator.com/item?id=787731 http://news.ycombinator.com/item?id=787731
  - jballanc 17y ago
    It's true that proteins don't have to be in their global minima function, but they do if you want them to stick around for a long time and not cause problems (see: Creutzfeld-Jakob disease, Alzheimer's, Parkinson's, etc.). There was some research a while back that took the question of: what sort of molecule would have it's global minimum conformation also be the quickest to fold to? (Unfortunately, I don't have the citation handy...) The result they came up with was something that looked an awful lot like proteins.
    - 17y ago

PieSquared 17y ago

I cannot agree more. Then it would get me off my butt and make me learn something about the topic, too.

biohacker42 17y ago
Well then lets get the ball rolling. There's a theory that protein folding is like a funnel. That is to say, the initial probability space is huge, much like the wide end of a funnel. But then it quickly collapses and the probability space becomes close enough to be computable by brute force. Now while there are some proteins that will unfold and then fold correctly again, most can't do that. Most don't start out as one long chain that then crumples in the right shape on its own. Most are carefully built from other parts, carefully guided along the desired path of entropy. And if they misfold, and that does happen, they are taken out. Now I personally have always thought of it as a simulation. Think about a can of mixed nuts. Have you ever noticed that the biggest kinds are always on top, and the smallest at the bottom? You might have to shake the can for a while but they will sort by size with the biggest on top. This is a function of friction and volume. If you shake a glass jar of mixed nuts, you can almost see a flow along the sides with the smaller ones flowing down and the bigger ones "floating" to the top. Imagine you were given the starting position of each nut, and the exact time and direction and force of the shaking of the jar. You are asked to write a simulation which will predict the final locations of each nut. If you think about a single threaded algorithm looking at each nut and how it nudges its neighbor and its neighbor and so on, it's a lot of calculations. But if you think of it a multi-threaded simulation then things get interesting.
- PieSquared 17y ago
  Hah, wow, thanks for the layman's description. That made sense! It also triggered one of those 'holy crap I have so much to learn' moments, followed shortly by a 'what the hell am I doing wasting my time with all these silly things I do' moment. ;)

quantumhobbit 17y ago

Protein-folding can be expressed as a superset of molecular modeling(my area of research). In the strictest physical sense this is not a P problem if you consider the interactions of every atom with every other atom O(n!) for n atoms. No one does it that way of course. Once you ignore all but nearest neighbor interactions you have a problem that is polynomial time for n. Proteins have too many atoms for even these techniques to be efficient. Now we're getting out of my area. As I understand it researchers do a Monte Carlo search of all possible configurations of amino acids(or even protein segments). Naively searching the space of all configurations would be make this NP. Of course you don't have to search the entire space. You can limit each step to make small changes only from an initial configuration and stay along a Markov chain of probable intermediate steps. I don't know enough to say that this would always be solvable in polynomial time, and of course you could miss the true minimum answer. I'd love to hear from someone who knows more.

adrianbg 17y ago
I don't think a naive search would even be useful because finding globally minimal energy configurations isn't the goal. It's pretty unlikely that nature would happen to put such large systems as whole proteins in their lowest possible energy configurations when all that is really necessary is that they be stable (ie., locally minimal configurations). Especially if nature uses the tightly controlled folding process biohacker42 describes: http://news.ycombinator.com/item?id=787731 http://news.ycombinator.com/item?id=787731
- jballanc 17y ago
  It's true that proteins don't have to be in their global minima function, but they do if you want them to stick around for a long time and not cause problems (see: Creutzfeld-Jakob disease, Alzheimer's, Parkinson's, etc.). There was some research a while back that took the question of: what sort of molecule would have it's global minimum conformation also be the quickest to fold to? (Unfortunately, I don't have the citation handy...) The result they came up with was something that looked an awful lot like proteins.
  - 17y ago