News for hackers. Stuff that matters.
Re:Gamers solve molecular puzzle by schlomie on Sunday September 18, 2011 @04:08PM (#3011121)
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.

Re:Gamers solve molecular puzzle by InclinedPlane on Sunday September 18, 2011 @07:22PM (#3011566)
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).
Re:Gamers solve molecular puzzle by cousin_it on Monday September 19, 2011 @12:01PM (#3014036)
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).
Re:Gamers solve molecular puzzle by asdkl234890 on Sunday September 18, 2011 @07:48PM (#3011616)
Yet proteins fold in polynomial time in all living things.
Re:Gamers solve molecular puzzle by timr on Sunday September 18, 2011 @08:11PM (#3011670)
That's meaningless. They're not folding on a Turing machine, so "polynomial time" isn't defined.
Re:Gamers solve molecular puzzle by shiven on Sunday September 18, 2011 @10:06PM (#3011926)
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 !!!

Re:Gamers solve molecular puzzle by jbri on Sunday September 18, 2011 @11:02PM (#3012034)
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.

Re:Gamers solve molecular puzzle by sid0 on Monday September 19, 2011 @12:11AM (#3012202)
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.
Re:Gamers solve molecular puzzle by xyzzyz on Sunday September 18, 2011 @08:12PM (#3011674)
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?
Re:Gamers solve molecular puzzle by irollboozers on Monday September 19, 2011 @02:09AM (#3012515)
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.

Re:Gamers solve molecular puzzle by shiven on Sunday September 18, 2011 @04:22PM (#3011158)
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!!

Re:Gamers solve molecular puzzle by kayhi on Monday September 19, 2011 @09:02AM (#3013349)
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.
Re:Gamers solve molecular puzzle by shiven on Tuesday September 20, 2011 @10:29PM (#3020483)
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!

Re:Gamers solve molecular puzzle by Haraldson on Sunday September 18, 2011 @06:09PM (#3011418)
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..?

Re:Gamers solve molecular puzzle by silentific on Sunday September 18, 2011 @07:42PM (#3011603)
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

Re:Gamers solve molecular puzzle by earl on Sunday September 18, 2011 @06:42PM (#3011492)
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.

Re:Gamers solve molecular puzzle by archangel_one on Monday September 19, 2011 @02:39AM (#3012595)
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

Re:Gamers solve molecular puzzle by Haraldson on Monday September 19, 2011 @04:46AM (#3012804)
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?

Re:Gamers solve molecular puzzle by tintin on Monday September 19, 2011 @06:18AM (#3012991)
FoldIt = game (http://fold.it)

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

Both "to understand protein folding".

Re:Gamers solve molecular puzzle by yters on Monday September 19, 2011 @02:41PM (#3014717)
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?
Re:Gamers solve molecular puzzle by stryker on Monday September 19, 2011 @11:18PM (#3016133)
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.

Re:Gamers solve molecular puzzle by mhb on Monday September 19, 2011 @11:14AM (#3013831)
How come they're not offering large cash prizes for solving these in order to encourage more participation?
Re:Gamers solve molecular puzzle by td on Monday September 19, 2011 @11:57AM (#3014016)
Because up until now, it's working just fine without large cash prizes, I guess.
Re:Gamers solve molecular puzzle by mhb on Monday September 19, 2011 @12:52PM (#3014260)
I suppose that depends on your sense of urgency.
Re:Gamers solve molecular puzzle by eavc on Monday September 19, 2011 @03:36PM (#3014927)
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.

Re:Gamers solve molecular puzzle by mhb on Monday September 19, 2011 @07:54PM (#3015697)
They seem to have worked pretty well for Netflix and the X prizes.
Re:Gamers solve molecular puzzle by rooshdi on Monday September 19, 2011 @01:16PM (#3014348)
Or sense of purpose.