Gamers solve molecular puzzle(cosmiclog.msnbc.msn.com)
cosmiclog.msnbc.msn.com
Gamers solve molecular puzzle
http://cosmiclog.msnbc.msn.com/_news/2011/09/16/7802623-gamers-solve-molecular-puzzle-that-baffled-scientists
8 comments
Protein folding is quite possibly an NP-complete problem. Determining the relative energy of a given protein-chain conformation can be done in polynomial time, it's a pretty simple problem. However, minimizing the energy is very difficult because there are so many degrees of freedom (on the order of the number of amino-acids in the protein).
You can build a machine that physically creates a specified protein and watches it fold. Will that qualify as a solver of NP-complete problems in polynomial time? Not likely! I'm pretty sure some proteins don't fold into their lowest possible energy configuration, they just find a local minimum. It's like computing minimum spanning trees with soap bubbles (there still exist cranks who think it works).
Yet proteins fold in polynomial time in all living things.
That's meaningless. They're not folding on a Turing machine, so "polynomial time" isn't defined.
Quite right! However, all we have are (imperfect?) versions of a Turing machine to solve the folding problem!
Maybe a Lisp machine would do better ;-)
At the end of the day, a linear sequence of amino acids has to end up in a three-dimensional conformation with short-range contacts being formed between atoms far away in the primary (linear) sequence. Add to this the complexity from long-range effects critical for the final structural stability and biological/biochemical function.
And don't even get me started on Intrinsically Disordered Proteins -- where, frankly, the future of the entire field lies !!!
Maybe a Lisp machine would do better ;-)
At the end of the day, a linear sequence of amino acids has to end up in a three-dimensional conformation with short-range contacts being formed between atoms far away in the primary (linear) sequence. Add to this the complexity from long-range effects critical for the final structural stability and biological/biochemical function.
And don't even get me started on Intrinsically Disordered Proteins -- where, frankly, the future of the entire field lies !!!
Assuming this is an NP problem, then a nondeterministic turing machine is capable of solving it in polynomial time (by definition).
So it stands to reason that a properly-constructed quantum computer (being an approximation of a nondeterministic turing machine) would probably be able to solve the protein folding problem in polynomial time.
It's also not out of the bounds of possibility for similar quantum effects to explain how proteins fold the same way every time - an individual protein in fact being a superposition of all possible foldings, and the lowest-energy folding being the one that is actually observed whenever it interacts with anything.
So it stands to reason that a properly-constructed quantum computer (being an approximation of a nondeterministic turing machine) would probably be able to solve the protein folding problem in polynomial time.
It's also not out of the bounds of possibility for similar quantum effects to explain how proteins fold the same way every time - an individual protein in fact being a superposition of all possible foldings, and the lowest-energy folding being the one that is actually observed whenever it interacts with anything.
There is no known way of getting a quantum computer to solve an NP-complete problem in polynomial time. Integer factoring is in NP but not complete for it.
In order to talk about "polynomial time", you need to introduce some computational model. What computational model of living things do you have in mind?
I worked in the Baker Lab, which developed the game, with the UW iGEM team. We actually used Foldit to make point mutations in a decapsulating protein in Anthrax.
http://2010.igem.org/Team:Washington
I wasn't too aware of the large community of Foldit players at the time, but it was really cool to see the lab bring in some of the top ranked players into the lab to get their opinion on specific folding problems. A friend of mine wanted to find the best design for a novel enzyme, and they actually brought in a guy as a consult.
http://2010.igem.org/Team:Washington
I wasn't too aware of the large community of Foldit players at the time, but it was really cool to see the lab bring in some of the top ranked players into the lab to get their opinion on specific folding problems. A friend of mine wanted to find the best design for a novel enzyme, and they actually brought in a guy as a consult.
Excellent! As a structural biologist, I found the coolest part of the entire approach to be the use of energetically favorable FoldIt model as a staring point for "molecular replacement".
I guess, this story highlights quite elegantly the "protein folding problem" to be a canonical "P vs NP" problem! Exciting times!!
I guess, this story highlights quite elegantly the "protein folding problem" to be a canonical "P vs NP" problem! Exciting times!!
I've had some success using the Zhang server (I-TASSER) to generate a model for MR. The benefit ended up being finding a domain, which we hadn't known based on our amino acid sequence. Exciting times indeed.
This seems to be in the same vein, kayhi :
http://www.slideshare.net/ijstokes/wide-search-molecular-rep...
Will be used for my next project!
http://www.slideshare.net/ijstokes/wide-search-molecular-rep...
Will be used for my next project!
I don't know much about molecular structures, but it's a really interesting subject. The crowdsourcing aspect of this is also something that makes me believe a little more in human kind.
Of course, if some idealistic crowd were to find the cure for AIDS or a HIV vaccine, some big corporation would surely claim the patents on it or something; it is of course highly ethical to earn big bucks on others' misery, instead of just getting the cure out there to the masses.
This story reminds me of the pilot of Stargate Universe, by the way. The gamers will get to go to space now, right..?
Of course, if some idealistic crowd were to find the cure for AIDS or a HIV vaccine, some big corporation would surely claim the patents on it or something; it is of course highly ethical to earn big bucks on others' misery, instead of just getting the cure out there to the masses.
This story reminds me of the pilot of Stargate Universe, by the way. The gamers will get to go to space now, right..?
Had the same thought about Stargate.
"Sometime in 2009, Wallace started playing an online game called Prometheus, and in the course of the game he solved a math problem in order to advance to the game's next level. But unbeknownst to him, the problem that Eli solved was actually an Ancient mathematical proof that was procured from the Ancient Database, and that Stargate Command had created the game in an effort to find someone who could solve it."
http://en.wikipedia.org/wiki/Eli_Wallace
"Sometime in 2009, Wallace started playing an online game called Prometheus, and in the course of the game he solved a math problem in order to advance to the game's next level. But unbeknownst to him, the problem that Eli solved was actually an Ancient mathematical proof that was procured from the Ancient Database, and that Stargate Command had created the game in an effort to find someone who could solve it."
http://en.wikipedia.org/wiki/Eli_Wallace
[deleted]
To be fair:
(1) Finding the molecular conformation is only a tiny piece of the puzzle.
(2) If we were to discover a vaccine for HIV, many countries such as India, Thailand, Brazil, and China would instantly break any necessary patents. This is at it should be -- the countries that can afford it fund R&D and those that can't share in the results.
(1) Finding the molecular conformation is only a tiny piece of the puzzle.
(2) If we were to discover a vaccine for HIV, many countries such as India, Thailand, Brazil, and China would instantly break any necessary patents. This is at it should be -- the countries that can afford it fund R&D and those that can't share in the results.
Something along the lines of a smaller version of (2) happened some years back in South Africa, since they've got a higher rate of HIV than any other country. IIRC, they were ignoring patents and manufacturing various medicines locally instead.
Token citation: http://en.wikipedia.org/wiki/HIV/AIDS_in_South_Africa#2001
Token citation: http://en.wikipedia.org/wiki/HIV/AIDS_in_South_Africa#2001
Yeah, good to know. These countries are probably too big even for big drug corps to take on.
Do you know anything about the quality of the locally manufactured drugs you mentioned, by the way?
Do you know anything about the quality of the locally manufactured drugs you mentioned, by the way?
[deleted]
FoldIt = game (http://fold.it)
Folding@home = distributed computing (http://folding.stanford.edu/)
Both "to understand protein folding".
Folding@home = distributed computing (http://folding.stanford.edu/)
Both "to understand protein folding".
Sweet, but it's strange a slow human brain can solve this even when we have super computers and the like working on the problem for many years. What's so special about our brains?
It's not so surprising if you consider that humans are much better at pattern recognition in general, where the space of possibilities is too large for a brute force search (even with clever optimizations, such as minimax, alpha-beta pruning, and hard-coded openings/endings).
Here is a specific example: http://en.wikipedia.org/wiki/Go_(game)#Computers_and_Go
They've made a bit of progress with Go, putting in heuristics and strategies specific to Go. But it basically amounts to translating human intelligence into code, or what researchers refer to as "domain knowledge".
Surely, machines are orders of magnitude faster than humans, for certain things. Just not all.
Here is a specific example: http://en.wikipedia.org/wiki/Go_(game)#Computers_and_Go
They've made a bit of progress with Go, putting in heuristics and strategies specific to Go. But it basically amounts to translating human intelligence into code, or what researchers refer to as "domain knowledge".
Surely, machines are orders of magnitude faster than humans, for certain things. Just not all.
How come they're not offering large cash prizes for solving these in order to encourage more participation?
Because up until now, it's working just fine without large cash prizes, I guess.
I suppose that depends on your sense of urgency.
Are cash prizes all that helpful in fostering insight?
I recall a demonstration at TED where cash incentives cause a worse performance, maybe due to pressure.
So if people are showing up on intrinsic motivation alone, it might be good to let that lie.
I recall a demonstration at TED where cash incentives cause a worse performance, maybe due to pressure.
So if people are showing up on intrinsic motivation alone, it might be good to let that lie.
They seem to have worked pretty well for Netflix and the X prizes.
Or sense of purpose.
Protein structure prediction: As described above, knowing the structure of a protein is key to understanding how it works and to targeting it with drugs. A small proteins can consist of 100 amino acids, while some human proteins can be huge (1000 amino acids). The number of different ways even a small protein can fold is astronomical because there are so many degrees of freedom. Figuring out which of the many, many possible structures is the best one is regarded as one of the hardest problems in biology today and current methods take a lot of money and time, even for computers. Foldit attempts to predict the structure of a protein by taking advantage of humans' puzzle-solving intuitions and having people play competitively to fold the best proteins.
...
What shape will a protein fold into? Even though proteins are just a long chain of amino acids, they don't like to stay stretched out in a straight line. The protein folds up to make a compact blob, but as it does, it keeps some amino acids near the center of the blob, and others outside; and it keeps some pairs of amino acids close together and others far apart. Every kind of protein folds up into a very specific shape -- the same shape every time. Most proteins do this all by themselves, although some need extra help to fold into the right shape. The unique shape of a particular protein is the most stable state it can adopt. Picture a ball at the top of a hill -- the ball will always roll down to the bottom. If you try to put the ball back on top it will still roll down to the bottom of the hill because that is where it is most stable.