For what it's worth I attended a seminar by this guy http://www.princeton.edu/~rajchak/ http://www.princeton.edu/~rajchak/ the other day and he was talking ab

For what it's worth I attended a seminar by this guy http://www.princeton.edu/~rajchak/ http://www.princeton.edu/~rajchak/ the other day and he was talking about using optimal control theory to optimize protein sequences for specific enzyme activity. He had a very sophisticated model for how the amino acid sequence determines the shape of the protein's active area. It was way over my head but he treated it as a solved problem. You may find his papers interesting. The combinatorial search results on protein folding are theoretically interesting, but I don't think that they are show stoppers for finding, or optimising the folded configuration of a protein. As you mentioned, most of the degrees of freedom which lead to the exponential size of the search space are irrelevant. A detailed understanding of the physics of how amino acids interact in water with ions can allow one to make approximations that vastly reduce the size of the search space. Plus how much time does it take a protein to find it's native conformation? Let's say the folding time is 10 ms. I think ultrafast pump probe spectroscopy has shown that alpha helices and other secondary structural motifs form on the time scale of 100 ps. Then the protein explores about 10^8 configurations before it finds the native one.