Gamers beat algorithms at finding protein structures
36 replies, posted
[url=http://arstechnica.com/science/news/2010/08/gamers-beat-algorithms-for-finding-protein-structures.ars]Source[/url]
[release][img]http://static.arstechnica.com/assets/2010/08/Foldit_screen-thumb-640xauto-15678.jpg[/img]
Today's issue of Nature contains a paper with a rather unusual author list. Read past the standard collection of academics, and the final author credited is... an online gaming community.
Scientists have turned to games for a variety of reasons, having studied virtual epidemics and tracked online communities and behavior, or simply used games to drum up excitement for the science. But this may be the first time that the gamers played an active role in producing the results, having solved problems in protein structure through the Foldit game.
According to a news feature on Foldit, the project arose from an earlier distributed computing effort called Rosetta@home. That project used what has become the standard approach for home-based scientific work: a screensaver that provided a graphical frontend to a program that uses spare processor time to solve weighty scientific problems. For Rosetta, that problem was the task of figuring out how proteins, which are composed of a chain of chemicals called amino acids, adopt their final, three-dimensional shape.
This is typically an energy minimization problem. Proteins tend to form structures that keep hydrophobic parts buried internally, away from the water they're dissolved in. They also form bridges between neighboring sections by hydrogen bonds and charge interactions. Maximize these sorts of interactions and you minimize the energy involved.
It sounds simple, but with anything more than a short chain of amino acids, there are a tremendous number of potential configurations to be sampled in 3D space, which can bring powerful computers to their knees.
The Rosetta algorithm handles the huge energy landscape it needs to scan by taking big leaps between different configurations, then attempting to minimize the energy by making smaller tweaks. This lets it sample large portions of the structural landscape, but sometimes leaves it stuck: the path between its current location and an energy minimum may take it through a high energy state, which would keep Rosetta from finding the solution.
Apparently, the program's home users noticed that the screensaver would often show the program stuck close to a much better structure. One of Foldit's developers is quoted as saying, "People started writing in, saying, 'I can see where it would fit better this way.'"
The Rosetta team decided to give them a chance to see if they really could.
[b]Starting with algorithms, ending with brains[/b]
Foldit takes a hybrid approach. The Rosetta algorithm is used to create some potential starting structures, but users are then given a set of controls that let them poke and prod the protein's structure in three dimensions; displays provide live feedback on the energy of a configuration.
Foldit uses some of the same conventions typical of other computer games, like a few simple structural problems to give new users a smooth learning curve. It also borrows from other online gaming communities; there are leaderboards, team and individual challenges, user forums, and so on.
Though very few of those who played Foldit had any significant background in biochemistry, the gamers tended to beat Rosetta when it came to solving structures. In a series of ten challenges, they outperformed the algorithms on five and drew even on another three.
By tracing the actions of the best players, the authors were able to figure out how the humans' excellent pattern recognition abilities gave them an edge over the computer. For example, people were very good about detecting a hydrophobic amino acid when it stuck out from the protein's surface, instead of being buried internally, and they were willing to rearrange the structure's internals in order to tuck the offending amino acid back inside. Those sorts of extensive rearrangements were beyond Rosetta's abilities, since the energy changes involved in the transitions are so large.
Similarly, Rosetta was good at linking up stretches of protein through charge interactions and hydrogen bonds, but it would often get things slightly off (think of a zipper that's off by a single tooth). Shifting every bond by a single partner was beyond Rosetta's abilities, but it's something a human can do trivially.
That's not to say the Rosetta algorithm didn't play a valuable role in Foldit. Humans turn out to be really bad at starting from a simple linear chain of proteins; they need a rough idea of what the protein might look like before they can recognize patterns to optimize. Given a set of 10 potential structures produced by Rosetta, however, the best players were very adept at picking the one closest to the optimal configuration.
The authors also note that different players tended to have different strengths. Some were better at making the big adjustments needed to get near an energy minimum, while others enjoyed the fine-scale tweaking needed to fully optimize the structure. That's where Foldit's ability to enable team competitions, where different team members could handle the parts of the task most suited to their interests and abilities, really paid off.
The Nature article makes it clear that researchers in other fields, including astronomy, are starting to try similar approaches to getting the public to contribute something other than spare processor time to scientific research. As long as the human brain continues to outperform computers on some tasks, researchers who can harness these differences should get a big jump in performance.
[/release]
We > Math. It's a fact now.
:buddy:
I love how even though Eli found that code thing by playing a game, he is known as math boy.
Very cool. Then again, this isn't too surprising. An algorithm is only as smart as you allow it to be, and from what the article lets on, it's pattern recognition skills are very strict.
[QUOTE=Maloof?;23841559][IMG_thumb]http://josephmallozzi.files.wordpress.com/2009/09/nup_133849_0109.jpg[/IMG_thumb][/QUOTE]
i dont think i get it
[QUOTE=wonkadonk;23841748]i dont think i get it[/QUOTE]
It's one of the main characters in Stargate Universe; he solved some mathematical problem embedded into a game.
[QUOTE=Sgt-NiallR;23841705]I love how even though Eli found that code thing by playing a game, he is known as math boy.[/QUOTE]
he's called math boy because of his skills in math 'n' that.
[QUOTE=Sgt-NiallR;23841705]I love how even though Eli found that code thing by playing a game, he is known as math boy.[/QUOTE]
He solved the energy problem within Months when Rush had been working on it for almost Two Years.
He solved the Address Code in Minutes when Rush had been working on it for Hours.
I don't understand why you guys are crediting yourselves, you guys didn't do shit.
[QUOTE=Dylan Clayton;23842618]I don't understand why you guys are crediting yourselves, you guys didn't do shit.[/QUOTE]
We gamers are all linked together. We are basically the same person.
[QUOTE=TheThing;23842654]We gamers are all linked together. We are basically the same person.[/QUOTE]
I agree with me. I'm right. We're all part of the same collective. We're... a hivemind, more or less.
this really is about as shocking as the sun rising in the morning...
it's well documented that humans are better at matching patterns. besides they still need the algorithm to generate the basic structure. still useful though, maybe we can get more science done :v:
[QUOTE=Dylan Clayton;23842618]I don't understand why you guys are crediting yourselves, you guys didn't do shit.[/QUOTE]
the fact still remains that most people i come across in games are stupid
Interesting way to let people do free work.
[QUOTE]the fact still remains that most people i come across in games are stupid[/QUOTE]
You don't get it, do you? I mean, everyone who plays games is not a gamer. Gamers are enthusiasts, not people who just sit down and play games as an idle distraction, but people whose lives are centered on gaming and take them as a way of life. The people you see on an average Counter-Strike or MW2 server aren't gamers: They're idiots. Turf out the trolls, the whiny 14-year-olds, the faggots and the simply thick, and there would be tumbleweed in de_dust2.
[QUOTE]I agree with me. I'm right. We're all part of the same collective. We're... a hivemind, more or less.[/QUOTE]
I agree with me. Whatever demographic or opinion you may have, as a gamer you can associate and relate with just about any other gamer. It's all about sharing a common experience.
As for the topic - I'm not surprised. Humans tend to do better than programs where the only option is brute force. For example, a program designed to break a password code would have to use some kind of trial-and-error algorithm, whereas a human could guess words and phrases, use outside information to their advantage, and even use gut instinct. Not sure what it proves about gamers, but hey, it's cool.
Yeah^ The definition of "gamer" no longer includes any person that plays a video game.
[QUOTE=ThePuska;23841817]It's one of the main characters in Stargate Universe; he solved some mathematical problem embedded into a game.[/QUOTE]
Fuck dude I'm a huge nerd and even that sounds dorky to me.
I like how you guys all try to associate yourselves with these gamers but if a gamer murders someone you say "we're not all like that!"
[QUOTE=Uberslug;23849107]I like how you guys all try to associate yourselves with these gamers but if a gamer murders someone you say "we're not all like that!"[/QUOTE]
We're not :rolleyes: :angel:
Yeah, take that you fucking algorithms
Where do I sign up?
[URL]http://fold.it/[/URL]
I'm playing it right now. It's amazingly fun.
What this mean is that the algorithm is flawed, not that we've got some kind of super ability at folding proteins.
[QUOTE=sltungle;23842769]I agree with me. I'm right. We're all part of the same collective. We're... a hivemind, more or less.[/QUOTE]
There is no "individual" we are gamer.
maybe when the robot overlords take over they'll spare the gamers
[QUOTE=Aperture fan;23841406]We're smarter then we let on.[/QUOTE]
The word is "than", not "then"
Cool stuff. It was in today's paper :smile:
Sorry, you need to Log In to post a reply to this thread.