Answering “how will this protein most likely fold?” is computationally much easier (as far as we can tell) than answering “what protein will fold like this?”
Got a reference for that? It’s not obvious to me (CS background, not bio).
What if you have an algorithm that attempts to solve the “how will this protein most likely fold?” problem, but is only tractable on 1% of possible inputs, and just gives up on the other 99%? As long as the 1% contains enough interesting structures, it’ll still work as a subroutine for the “what protein will fold like this?” problem. The search algorithm just has to avoid the proteins that it doesn’t know how to evaluate. That’s how human engineers work, anyway: “what does this pile of spaghetti code do?” is uncomputable in the worst case, but that doesn’t stop programmers from solving “write a program that does X”.
Sure, see for example here which discusses some of the issues involved. Although your essential point may still have merit, because it is likely that many of the proteins we would want will have much more restricted shapes than those in general problem. Also, I don’t know much about what work has been done in the last few years, so it is possible that the state of the art has changed substantially.
Got a reference for that? It’s not obvious to me (CS background, not bio).
What if you have an algorithm that attempts to solve the “how will this protein most likely fold?” problem, but is only tractable on 1% of possible inputs, and just gives up on the other 99%? As long as the 1% contains enough interesting structures, it’ll still work as a subroutine for the “what protein will fold like this?” problem. The search algorithm just has to avoid the proteins that it doesn’t know how to evaluate. That’s how human engineers work, anyway: “what does this pile of spaghetti code do?” is uncomputable in the worst case, but that doesn’t stop programmers from solving “write a program that does X”.
Sure, see for example here which discusses some of the issues involved. Although your essential point may still have merit, because it is likely that many of the proteins we would want will have much more restricted shapes than those in general problem. Also, I don’t know much about what work has been done in the last few years, so it is possible that the state of the art has changed substantially.