4 ms·

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 consi

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.
  - roundsquare 17y ago
    I'm curious: -- How long would they stay around for? -- What sorts of problems? Would you need a lot of "bad" proteins to cause problems or just a few? What I'm trying to get at is wondering if nature uses very good heuristic/approximate/probabilistic algorithm. I.e. if there is an algorithm that almost always works and having a few proteins that aren't at global minima isn't an issue and they dissipate very quickly, then observation would make it look like nature is solving the problem exactly even if its not. Alternatively, the proteins we find in nature might be more tractable than the general problem described in all its mathematical glory (i.e. the inputs might be restricted to some subset of the input space which is solvable very quickly).
    - jballanc 17y ago
      How long would they stay around for? That depends on the thermodynamics. Specifically, it depends on the depth of the local minimum and the energy in the system. With some random chance, a protein can get out of a local minimum and fold into a different conformation. If nature is depending on the fold not changing, this could be a problem. What sorts of problems? Would you need a lot of "bad" proteins to cause problems or just a few? Again, it depends. In general, unfolded proteins are a bad thing. They are also a fairly common thing to find in cells, and cells have a specific "unfolded protein response" that kicks into gear if there are too many. Too many unfolded proteins literally "gum up the works". For prions, tau (in Alzheimer's), and others, the story is a bit different. In these cases, the presence of even a few improperly folded proteins can catalyze further misfolding. Alternatively, the proteins we find in nature might be more tractable than the general problem described in all its mathematical glory This is almost certainly the case, but more tractable != not intractable. Solving the problem also requires clever solutions and a better understanding of physics. If your curious, I did my Ph.D. preliminary exam on one example (modern methods of handling side-chain entropy, including belief propagation techniques). The LaTeX source is at: http://github.com/jballanc/prelim/ http://github.com/jballanc/prelim/
      - roundsquare 17y ago
        They are also a fairly common thing to find in cells Interesting. You mean totally unfolded or not folded correctly (i.e. proteins that haven't started the process or proteins that went through it and got to the wrong state)? Also, does this mean that "nature has solved this problem" aren't true? I.e. "nature" doesn't get it right all the time, just often enough that we're generally okay?
jballanc 17y ago
So, as I've alluded to elsewhere, the thing to remember about P vs NP is that you can solve NP problems very quickly, but it takes NP time to verify that the solution is correct. In other words, you can walk a traveling salesman to all the houses in the time it takes to walk to all the houses (that's a solution), but in order to verify that the path you walked was the shortest, you'd have walk all the possible paths (or at least, walk them until they were longer than the original path you walked, which is part of how heuristic methods of solving the problem work). The way this works with proteins is assuming that proteins fold to a conformation that is a global minimum. For any given combination of atoms, you would have to consider all possible conformations (which, as you point out, can more easily be expressed in terms of pair-wise and higher-order interactions). This is the classic NP-complete, traveling-salesman type problem. Now, not all proteins fold to a global energy minimum, but many or most do. So really, whether protein folding is P or NP depends on what you mean by the "protein folding problem". If, by "protein folding problem", you mean determining the global energy minimum for any given chain of amino acids, then yes, this is NP. However, what Levinthal realized (with his paradox) was that if this was how proteins actually folded, it would take more than the age of the universe for a single protein to fold. This is even more paradoxical when you consider that most proteins fold on the millisecond to microsecond time scale. In other words, nature isn't solving an NP problem. If, by "protein folding problem", you mean figuring out how a protein reaches its final conformation, then this is where the funnel comes in. Think of a protein on a surface in conformation space. Each spatial arrangement of atoms represents a different point in space. The surface represents the region of space that is accessible to the protein at a given energy. So, at high energy, the protein can wiggle around pretty much at will. All conformation space is open to it. However, as you lower the energy, fewer and fewer conformations are energetically allowed (that is, the protein no longer has enough energy to break certain hydrogen bonds or ionic interactions). Eventually, you lower the energy enough, and you find the global energy minimum. Where this gets tricky is that there could be "traps" in the funnel; local energy minima that the protein can't escape from. If the protein gets caught in one of these traps, then it hasn't solved the NP problem of finding the global energy minimum. What's remarkable about proteins, however, is that the path they do follow (the one that's kinetically favorable) almost always avoids these traps. So, the protein is solving a P problem (finding the steepest path down the funnel), but in doing so also solves an NP problem (finding the global minimum). If you think about it then, it's actually the funnel that has solved the NP problem (or rather, turned it into a P problem). This funnel is constructed by the laws of physics as they pertain to proteins, and it seems as though the unique properties of the 20 amino acids that make up proteins are the key to this NP to P conversion. Now, do I think this means that P = NP? No. The protein folding funnel is a heuristic, just like any other. Just because proteins usually find the global energy minimum, doesn't mean they always do. To absolutely, positively verify that they are at their global minimum, you still have to solve an NP hard problem.

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.
- roundsquare 17y ago
  I'm curious: -- How long would they stay around for? -- What sorts of problems? Would you need a lot of "bad" proteins to cause problems or just a few? What I'm trying to get at is wondering if nature uses very good heuristic/approximate/probabilistic algorithm. I.e. if there is an algorithm that almost always works and having a few proteins that aren't at global minima isn't an issue and they dissipate very quickly, then observation would make it look like nature is solving the problem exactly even if its not. Alternatively, the proteins we find in nature might be more tractable than the general problem described in all its mathematical glory (i.e. the inputs might be restricted to some subset of the input space which is solvable very quickly).
  - jballanc 17y ago
    How long would they stay around for? That depends on the thermodynamics. Specifically, it depends on the depth of the local minimum and the energy in the system. With some random chance, a protein can get out of a local minimum and fold into a different conformation. If nature is depending on the fold not changing, this could be a problem. What sorts of problems? Would you need a lot of "bad" proteins to cause problems or just a few? Again, it depends. In general, unfolded proteins are a bad thing. They are also a fairly common thing to find in cells, and cells have a specific "unfolded protein response" that kicks into gear if there are too many. Too many unfolded proteins literally "gum up the works". For prions, tau (in Alzheimer's), and others, the story is a bit different. In these cases, the presence of even a few improperly folded proteins can catalyze further misfolding. Alternatively, the proteins we find in nature might be more tractable than the general problem described in all its mathematical glory This is almost certainly the case, but more tractable != not intractable. Solving the problem also requires clever solutions and a better understanding of physics. If your curious, I did my Ph.D. preliminary exam on one example (modern methods of handling side-chain entropy, including belief propagation techniques). The LaTeX source is at: http://github.com/jballanc/prelim/ http://github.com/jballanc/prelim/
    - roundsquare 17y ago
      They are also a fairly common thing to find in cells Interesting. You mean totally unfolded or not folded correctly (i.e. proteins that haven't started the process or proteins that went through it and got to the wrong state)? Also, does this mean that "nature has solved this problem" aren't true? I.e. "nature" doesn't get it right all the time, just often enough that we're generally okay?

jballanc 17y ago

So, as I've alluded to elsewhere, the thing to remember about P vs NP is that you can solve NP problems very quickly, but it takes NP time to verify that the solution is correct. In other words, you can walk a traveling salesman to all the houses in the time it takes to walk to all the houses (that's a solution), but in order to verify that the path you walked was the shortest, you'd have walk all the possible paths (or at least, walk them until they were longer than the original path you walked, which is part of how heuristic methods of solving the problem work). The way this works with proteins is assuming that proteins fold to a conformation that is a global minimum. For any given combination of atoms, you would have to consider all possible conformations (which, as you point out, can more easily be expressed in terms of pair-wise and higher-order interactions). This is the classic NP-complete, traveling-salesman type problem. Now, not all proteins fold to a global energy minimum, but many or most do. So really, whether protein folding is P or NP depends on what you mean by the "protein folding problem". If, by "protein folding problem", you mean determining the global energy minimum for any given chain of amino acids, then yes, this is NP. However, what Levinthal realized (with his paradox) was that if this was how proteins actually folded, it would take more than the age of the universe for a single protein to fold. This is even more paradoxical when you consider that most proteins fold on the millisecond to microsecond time scale. In other words, nature isn't solving an NP problem. If, by "protein folding problem", you mean figuring out how a protein reaches its final conformation, then this is where the funnel comes in. Think of a protein on a surface in conformation space. Each spatial arrangement of atoms represents a different point in space. The surface represents the region of space that is accessible to the protein at a given energy. So, at high energy, the protein can wiggle around pretty much at will. All conformation space is open to it. However, as you lower the energy, fewer and fewer conformations are energetically allowed (that is, the protein no longer has enough energy to break certain hydrogen bonds or ionic interactions). Eventually, you lower the energy enough, and you find the global energy minimum. Where this gets tricky is that there could be "traps" in the funnel; local energy minima that the protein can't escape from. If the protein gets caught in one of these traps, then it hasn't solved the NP problem of finding the global energy minimum. What's remarkable about proteins, however, is that the path they do follow (the one that's kinetically favorable) almost always avoids these traps. So, the protein is solving a P problem (finding the steepest path down the funnel), but in doing so also solves an NP problem (finding the global minimum). If you think about it then, it's actually the funnel that has solved the NP problem (or rather, turned it into a P problem). This funnel is constructed by the laws of physics as they pertain to proteins, and it seems as though the unique properties of the 20 amino acids that make up proteins are the key to this NP to P conversion. Now, do I think this means that P = NP? No. The protein folding funnel is a heuristic, just like any other. Just because proteins usually find the global energy minimum, doesn't mean they always do. To absolutely, positively verify that they are at their global minimum, you still have to solve an NP hard problem.