3 ms·
determining the lowest energy conformation would require trying all possible conformations I apologize if it seems like I'm arguing over semantics, but from th
by jdale27 17y ago
determining the lowest energy conformation would require trying all possible conformations
I apologize if it seems like I'm arguing over semantics, but from the computer science perspective, solving the protein folding problem (as opposed to approximating it) means finding an algorithm that does give the lowest energy conformation, without (in order for it to be tractable) trying all conformations.
In some formulation of protein folding that is NP-complete, your statement (require[s] trying all possible conformations) is tantamount to P!=NP. So I'm guessing you don't have a proof of that. ;)
I admit that this is weak reasoning, but consider an analogy from computational biology: the Needleman-Wunsch algorithm for finding the optimal global alignment between two sequences. There are exponentially many possible alignments. Through the magic of dynamic programming, Needleman-Wunsch guarantees us the optimal alignment without trying all of them (it works in polynomial time). We can't rule out the possibility that some similarly clever algorithm can do the same for protein folding.
Now, Needleman-Wunsch works with respect to a scoring function that happens to make the problem tractable. In the case of protein folding, we'd have to ensure that the energy function we're optimizing with whatever clever algorithm we come up with is close enough to reality for the results to be useful to biologists.
- jballanc 17y agoNo need to worry about arguing semantics, I'm learning here. As I've said, I'm what you'd call an applied computer scientist. While I've got a good handle on tractability, dynamic programming, and the like, sometimes I miss the formalisms of the terminology. In some formulation of protein folding that is NP-complete, your statement (require[s] trying all possible conformations) is tantamount to P!=NP. So I'm guessing you don't have a proof of that. ;) Haha, ok, yes. You've got me there. Actually, that also clears up a few issues I was having with the original article. I tend to confound tractability and NP-complete. If I follow you now, an algorithm that can fold a protein to lowest energy is the solution. If that solution can be shown to be correct without trying all possible conformations, then it is P. If the only way to verify it correct would be to explore all fold space, then it would be NP and and P!=NP. In other words, my original assertion that protein folding is not, strictly speaking, NP relates to the fact that nature does not try all possible conformations. We could write an NP solution that does, but this is not what happens in reality. So, either nature is solving a slightly different problem (it doesn't worry about finding the global energy minimum exactly), or P=NP and the "algorithm" (in this sense a combination of physical laws) used by nature solves the same problem as our NP search of all conformation space.