UW Center for Game Science / Baker Lab
Foldit players learn to resolve structural conflicts in a protein molecule due to amino acid size (indicated by spiky red balls in this game visualization).
By Alan Boyle, Science Editor, NBC News
Researchers say that players of a protein-folding game called Foldit are coming up with molecular "recipes" that rival their own complex algorithms.
One of the recipes — a computerized tool called "Blue Fuse," which checks whether a protein molecule is in its highest-scoring configuration — knocked Foldit's creators for a loop. "When I saw the Blue Fuse algorithm, I recognized immediately that it was almost identical in concept to the best algorithm that we developed in my research group over a period of years," David Baker, a biochemist at the University of Washington, told me today.
It took the players of the Foldit game only about seven months to come up with their version, and they're continuing to improve the recipe.
"We were shocked to find state-of the art algorithms," Zoran Popovic, director of UW's Center for Game Science and the game's co-creator, said in a university news release.
UW computer scientist Seth Cooper, Foldit's other co-creator as well as lead designer/developer, said the findings demonstrate the power of collaborative game play for solving scientific problems. "It's a great thing to show what kinds of things video games and gamers can accomplish," he told me.
The science behind the recipe-writing process is detailed in a research paper published online this week in the Proceedings of the National Academy of Sciences.
More than a game
Protein-folding isn't just a game: The structures of protein molecules are the keys to a wide range of biological processes. In a sense, proteins literally serve as "keys" and "locks" to open up cellular pathways, to admit or block viruses, to start or stop the machinery of life. If scientists can gain a better understanding of how those keys and locks work, they could actually design their own molecules for future medications and nanomachines.
That's where Foldit and other protein-folding software tools can play a huge role. Foldit is a social game based on a computerized molecule-manipulation program called Rosetta, which was developed a decade ago by Baker and his colleagues at UW. The Foldit game has enlisted hundreds of thousands of players who can work together (or compete against each other) to twist and turn virtual molecules and rack up high scores. The scores are based on how well players can fold molecules to produce the lowest-energy state — the state that is preferred in nature.
Just a couple of months ago, UW researchers credited Foldit players with figuring out the right structure for an enzyme from an AIDS-like virus found in rhesus monkeys. The latest research focuses on the processes used by the players rather than the results.
Players trade recipes
Starting in mid-2009, Foldit's developers made it possible for players to create and share their own algorithms for manipulating molecules automatically. The gamers refer to these software routines as "recipes."
"A lot of them have been shared with their own teammates, of course, and also with the players that they're competing against," UW biochemist Firas Khatib, a co-author for the paper, told me. "In some of the descriptions, they say, 'You might want to put the kettle on for this one,' or 'You might want to let this one run for a few days.'"
Over the months that followed, Foldit players tinkered with the recipes to produce tastier molecules with less time and effort.
"The whole thing was a social process," Cooper explained. "It's really drawing on the collective intelligence of the Foldit players as a whole, to come up with the algorithms and also decide which ones are useful."
Blue Fuse became one of the most popular recipes among the gamers. Khatib said the software tool takes the code for a molecule folded in a particular way, and bends the rules of the game temporarily to check whether there's an even better solution to the puzzle. If there is, the software slowly brings the rules back and heads for that better solution instead. "That's literally how simple the algorithm is, which is why it's so brilliant," Khatib said.
Researchers conduct cook-off
It turned out that Blue Fuse was similar to an algorithm in the more sophisticated Rosetta program, known as Fast Relax. That algorithm was a new, improved (but unpublished) version of an older software tool called Classic Relax. The researchers staged a recipe cook-off to see how the three algorithms compared. Blue Fuse took less time to come up with a low-energy solution to a given protein puzzle than Classic Relax, but more time than the improved Fast Relax.
That wasn't the end of the cook-off, however. "One of the reviewers for our paper pointed out that that's a completely unfair competition," Khatib said.
The reviewer observed that Fast Relax was taking advantage of software routines in Rosetta that were not available in Foldit. When the UW researchers adapted Fast Relax for the Foldit program, they found that Blue Fuse identified low-energy puzzle solutions faster — although Fast Relax could find even lower-energy solutions if it was allowed to run for more than 200 seconds of CPU time. (The average Blue Fuse runtime during gameplay was 122 seconds.)
"For 200 seconds and less, Blue Fuse is actually better than Fast Relax," Khatib said. "It optimizes faster."
Baker said the next step is to give the gamers more power. "What we're doing now is taking many more of the Rosetta options and parameters and exposing them to Foldit players, so that they can use them. ... I'm really excited to see what Foldit players can do once they have access to the full palette of options," he told me.
He said it won't be all that long before the Foldit players are recruited not only to solve protein-folding puzzles, but also to try out molecular designs that could lead to "new virus inhibitors, new carbon-fixation pathways, new routes to vaccines."
"We're now learning enough of the rules that we can actually make our own proteins," Baker said.
Update for 5:45 p.m. ET: The creator of the Blue Fuse "recipe," a Foldit player known as Vertex, was kind enough to answer a few of my questions via email. (Foldit players traditionally prefer not to be identified by their real-world names.) Here's an edited version of the Q&A:
Cosmic Log: What’s your background? Are you the sort of person who deals with molecule-manipulating algorithms for your day job, or is this something generally foreign to you?
Vertex: I'm a retired software engineer, so I know nothing about biochemistry. I wrote Blue Fuse primarily to launch new Foldit puzzles — light the blue fuse and stand back. It was quickly taken up by the Foldit community as a credibility test on new protein shapes generated by the rebuild toolset. Its success in this role is far beyond anything I originally imagined or expected, but this is the key strength of the Foldit democracy — it is natural selection at its very best. Dozens of bright ideas are brought to life through the vision, creativity and collaboration of the players. And then, in recipe form, the scripts fly or die when others use them.
Blue Fuse spawned from Acid Tweeker, a brilliant grandfather script from the genius of Stephen Pletsch, and now has many children of its own. To 'Fuze' has even become a Foldit verb. It's a crazy success story for Blue Fuse, but Foldit is a place where game play meets bioengineering and the next flash of inspiration can come from literally anywhere.
Q: What process did you use to come up with the algorithm? Is it a question of math, or a question of visualization?
A: The development of Blue Fuse was a small exercise in statistics. In Foldit there is an adjustable parameter, "clash behavior," that controls how well the Foldit toolset tolerates proximity between protein side chains. Setting the clash behavior low allows the protein to compress, but at the expense of the overall energy score. Blue Fuse manipulates the clash behavior through various compressions and relaxations. I tried different clash values on the start positions of three puzzles and recorded the scores for a wide range of samples. An unexpected result was the discovery that the best clash values were significantly different for the three puzzles, so I had to choose values that on probability gave a good outcome. I could have made Blue Fuse a bigger script with more combinations, but I wanted a quick answer more than anything else.
Q: Could you explain for a newbie like me exactly what the algorithm does?
A: The core idea is that the clash behavior is adjusted down to a carefully selected level, and the protein is allowed to compress and is then shaken. The clash behaviour is then set back to normal, and the protein is allowed to decompress. This is very much more gentle on the overall shape of the protein than the scripts that use "bands" to compress the structure — which can cause undesired distortions. Blue Fuse is a deliberately simple set of actions based on this core idea. It has been developed to be fast. It will very quickly let you discover if a new shape is fundamentally OK or not.
Q: Has the tool evolved substantially since its creation?
A: Blue Fuse itself has not changed since I posted it, but there are many children citing Blue Fuse as parent, using variations on the core idea. Firas could say how many, but I think it may be as many as 60. I too have a design for a new version of Blue Fuse that will improve its performance — I can't ignore the challenge that Fast Relax is out ahead right now.
Q: The paper indicates that Blue Fuse and other recipes are used in conjunction with human-guided manipulation, and that it’s not a strictly automatic process. Is that pretty much the way it works? How long does it generally take to run the tool?
A: Correct. Blue Fuse is typically used by Foldit players to test the results of the rebuild tool. The choice of what section of the protein to rebuild, and which outcomes are worth testing, are normally human decisions. There are very sophisticated recipes that automate these selection tasks and embed "Fuzers" to test outcomes, but they are generally used to fine-tune a shape rather than perform major surgery. A primary goal of Foldit is to capture ways of automating the human element, and huge progress has been made on this, but judgment of good shape remains our edge over the machine.
The time taken by Blue Fuse varies enormously, depending on the size of the protein and the power of the player's computer. For me it typically takes about a minute. This is fast for a Foldit script.
Q: I’m wondering if there are things that could be adapted from Blue Fuse to Fast Relax or other tools used in other protein-folding software, or more generally, to mathematics and engineering challenges that aren’t directly connected to protein folding.
A: Yes. Blue Fuse (and children) and Fast Relax are actually convergent. Everyone competes and collaborates at the same time. Evolution and natural selection will decide the best script.
Foldit is part of the GWAP ("games with a purpose") world. There are many ways that crowdsourcing through game-play is already bringing a fresh approach to all kinds of academic challenge. Foldit does this supremely well for protein structure. It's an amazing tool. The Foldit community has already solved important biological proteins that previously had unknown structures, and has helped design new proteins for medical research. I would expect this important work to continue strongly in the future, and we will get better at it. I would also expect substantial progress to be made in the automation of protein structure prediction tools — both in Foldit and in the broader academic world, of course.
More about Foldit and other games with a purpose:
In addition to Khatib, Cooper, Popovic and Baker, co-authors of "Algorithm Discovery by Protein Folding Game Players" include Michael Tyka, Kefan Xu, Ilya Makedon and Foldit players. The Foldit project was developed by the UW Center for Game Science in collaboration with UW's Baker Laboratory, with funding from the Defense Advanced Research Projects Agency, the National Science Foundation, the Howard Hughes Medical Institute, Adobe and Microsoft Corp. (Microsoft and NBC Universal are partners in the msnbc.com joint venture.)
Connect with the Cosmic Log community by "liking" the log's Facebook page or following @b0yle on Twitter. You can also add me to your Google+ circle, and check out "The Case for Pluto," my book about the controversial dwarf planet and the search for new worlds.
E-mail updates
Follow on Twitter
Subscribe to RSS
