Gamers solve molecular puzzle

http://cosmiclog.msnbc.msn.com/_news/2011/09/16/7802623-gamers-solve-molecular-puzzle-that-baffled-scientists

by sew • 15 years ago

137 27 15 years ago

cosmiclog.msnbc.msn.com

schlomie• 15 years ago

Explanation of the problem: 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• 15 years 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).

asdkl234890• 15 years ago

Yet proteins fold in polynomial time in all living things.

cousin_it• 15 years 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).

shiven3• 15 years 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• 15 years 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.

shiven3• 15 years ago

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!

Haraldson2• 15 years 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• 15 years 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• 15 years 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

silentific• 15 years ago

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

irollboozers• 15 years 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

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• 15 years ago

FoldIt = game (http://fold.it)

Folding@home = distributed computing (http://folding.stanford.edu/)

Both "to understand protein folding".

mhb3• 15 years ago

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

td• 15 years ago

Because up until now, it's working just fine without large cash prizes, I guess.

mhb3• 15 years ago

I suppose that depends on your sense of urgency.

yters• 15 years 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• 15 years 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

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.

Gamers solve molecular puzzle

Related Stories