7 ms·

Gamers solve molecular puzzle

137 points by sew 15y ago

deleted 15y ago
[deleted]
schlomie 15y ago
Explanation of the problem: http://fold.it/portal/info/science#whygame http://fold.it/portal/info/science#whygame 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.
- InclinedPlane 15y ago
  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).
  - cousin_it 15y ago
    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).
  - asdkl234890 15y ago
    Yet proteins fold in polynomial time in all living things.
    - timr 15y ago
      That's meaningless. They're not folding on a Turing machine, so "polynomial time" isn't defined.
      - shiven 15y ago
        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 !!!
        jbri 15y ago
        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.
shiven 15y ago
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!!
- kayhi 15y ago
  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.
  - shiven 15y ago
    This seems to be in the same vein, kayhi : http://www.slideshare.net/ijstokes/wide-search-molecular-replacement-and-the-nebiogrid-portal-interface http://www.slideshare.net/ijstokes/wide-search-molecular-rep... Will be used for my next project!
Haraldson 15y ago
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..?
- earl 15y ago
  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.
  - archangel_one 15y ago
    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 http://en.wikipedia.org/wiki/HIV/AIDS_in_South_Africa#2001
    - Haraldson 15y ago
      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?
- deleted 15y ago
  [deleted]
- silentific 15y ago
irollboozers 15y ago
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 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.
tintin 15y ago
FoldIt = game (http://fold.it http://fold.it) Folding@home = distributed computing (http://folding.stanford.edu/ http://folding.stanford.edu/) Both "to understand protein folding".
mhb 15y ago
How come they're not offering large cash prizes for solving these in order to encourage more participation?
- td 15y ago
  Because up until now, it's working just fine without large cash prizes, I guess.
  - mhb 15y ago
    I suppose that depends on your sense of urgency.
    - rooshdi 15y ago
      Or sense of purpose.
    - eavc 15y ago
      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.
      - mhb 15y ago
        They seem to have worked pretty well for Netflix and the X prizes.
yters 15y ago
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?
- stryker 15y ago
  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 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.

137 points by sew 15y ago

deleted 15y ago

[deleted]

Explanation of the problem: http://fold.it/portal/info/science#whygame http://fold.it/portal/info/science#whygame 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.

InclinedPlane 15y ago
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).
- cousin_it 15y ago
  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).
- asdkl234890 15y ago
  Yet proteins fold in polynomial time in all living things.
  - timr 15y ago
    That's meaningless. They're not folding on a Turing machine, so "polynomial time" isn't defined.
    - shiven 15y ago
      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 !!!
      - jbri 15y ago
        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.

shiven 15y ago

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!!

kayhi 15y ago
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.
- shiven 15y ago
  This seems to be in the same vein, kayhi : http://www.slideshare.net/ijstokes/wide-search-molecular-replacement-and-the-nebiogrid-portal-interface http://www.slideshare.net/ijstokes/wide-search-molecular-rep... Will be used for my next project!

Haraldson 15y ago

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..?

earl 15y ago
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.
- archangel_one 15y ago
  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 http://en.wikipedia.org/wiki/HIV/AIDS_in_South_Africa#2001
  - Haraldson 15y ago
    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?
deleted 15y ago
[deleted]
silentific 15y ago

irollboozers 15y ago

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 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.

tintin 15y ago

FoldIt = game (http://fold.it http://fold.it) Folding@home = distributed computing (http://folding.stanford.edu/ http://folding.stanford.edu/) Both "to understand protein folding".

mhb 15y ago

How come they're not offering large cash prizes for solving these in order to encourage more participation?

td 15y ago
Because up until now, it's working just fine without large cash prizes, I guess.
- mhb 15y ago
  I suppose that depends on your sense of urgency.
  - rooshdi 15y ago
    Or sense of purpose.
  - eavc 15y ago
    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.
    - mhb 15y ago
      They seem to have worked pretty well for Netflix and the X prizes.

yters 15y ago

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?

stryker 15y ago
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 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.