4 ms·
Protein folding is suspected to be an NP-complete problem <http://www.liebertonline.com/doi/abs/10.1089/cmb.1998.5.27 http://www.liebertonline.com/doi/abs/10.10
by dhs 16y ago
Protein folding is suspected to be an NP-complete problem <http://www.liebertonline.com/doi/abs/10.1089/cmb.1998.5.27 http://www.liebertonline.com/doi/abs/10.1089/cmb.1998.5.27 >, so it seems to me that having reason to believe it will someday be solved equals having reason to believe that someday NP-complete problems can be computed in polynomial time. Alternatively, you might hope for a domain-specific approximative algorithm, but this seems tricky, too, since mis-folded proteins can end up as really bad stuff, e.g. prions <http://en.wikipedia.org/wiki/Prion http://en.wikipedia.org/wiki/Prion >.
- jerf 16y agoSaying it's NP-complete doesn't prove we can't solve it well enough for simulation. As a physical problem become "pathologically NP", Nature becomes non-deterministic too; it seems unlikely that Nature will make extensive use of a protein that doesn't reliably fold in a certain way, or some small constrained set of ways. See http://www.scottaaronson.com/papers/npcomplete.pdf http://www.scottaaronson.com/papers/npcomplete.pdf
- dhs 16y agoNot that I wouldn't like to be as optimistic, too, but Nature does seem to have made enough use of unreliably folding proteins to have come up with BSE, Parkinson's disease, and some others <http://en.wikipedia.org/wiki/Protein_folding#Incorrect_protein_folding_and_neurodegenerative_disease http://en.wikipedia.org/wiki/Protein_folding#Incorrect_prote... >. I'm a big fan of Scott Aaronson, too, btw :-) Here's a pic of him demoing the soap bubbles experiment he refers to in that paper you linked to <http://www.scottaaronson.com/soapbubble.jpg http://www.scottaaronson.com/soapbubble.jpg >.
- jerf 16y agoI thought of mentioning that, actually, but figured it would be extraneous. However, if they are all indeed pathological then perhaps we can do our simulated humans a favor and not simulate the pathological path. Still, as discussed in another comment I made, I seriously, seriously doubt that we will ever simulate any sort of intelligence by raw physical simulation. It just isn't feasible with any realistic computational technique.
- rsheridan6 16y agoThe article says that the HP model is NP-complete. But water folds protein very quickly. I may be misunderstanding things here, but if protein folding (as opposed to a particular model of protein folding) is NP-complete, shouldn't it be slow in real life too? I recall reading an interview with someone who founded a company that builds computers for simulating biological systems in silico who thought that there were much better algorithms waiting to be discovered because nature can do it quickly. I can't find it now.