|Home | About | Journals | Submit | Contact Us | Français|
People exert significant amounts of problem solving effort playing computer games. Simple image- and text-recognition tasks have been successfully crowd-sourced through gamesi, ii, iii, but it is not clear if more complex scientific problems can be similarly solved with human-directed computing. Protein structure prediction is one such problem: locating the biologically relevant native conformation of a protein is a formidable computational challenge given the very large size of the search space. Here we describe Foldit, a multiplayer online game that engages non-scientists in solving hard prediction problems. Foldit players interact with protein structures using direct manipulation tools and user-friendly versions of algorithms from the Rosetta structure prediction methodologyiv, while they compete and collaborate to optimize the computed energy. We show that top Foldit players excel at solving challenging structure refinement problems in which substantial backbone rearrangements are necessary to achieve burial of hydrophobic residues. Players working collaboratively develop a rich assortment of new strategies and algorithms; unlike computational approaches, they explore not only conformational space but also the space of possible search strategies. The integration of human visual problem-solving and strategy development capabilities with traditional computational algorithms through interactive multiplayer games is a powerful new approach to solving computationally-limited scientific problems.
While it has been known for over 40 years that the three dimensional structures of proteins are determined by their amino acid sequencesv, protein structure prediction remains a largely unsolved problem for all but the smallest protein domains. The state-of-the-art Rosetta structure prediction methodology, for example, is limited primarily by conformational sampling; the native structure almost always has lower energy than any non-native conformation, but the free energy landscape that must be searched is extremely large—even small proteins have on the order of 1000 degrees of freedom—and rugged due to unfavorable atom-atom repulsion which can dominate the energy even quite close to the native state. To search this landscape, Rosetta uses a combination of stochastic and deterministic algorithms: rebuilding all or a portion of the chain from fragments, random perturbation to a subset of the backbone torsion angles, combinatorial optimization of protein sidechain conformations, gradient based energy minimization, and energy-dependent acceptance or rejection of structure changesvi, vii, viii.
We hypothesized that human spatial reasoning could improve both the sampling of conformational space and the determination of when to pursue suboptimal conformations if the stochastic elements of the search were replaced with human decision making while retaining the deterministic Rosetta algorithms as user tools. We developed a multiplayer online game, Foldit, with the goal of producing accurate protein structure models through gameplay (Fig. 1). Improperly folded protein conformations are posted online as puzzles for a fixed amount of time, during which players interactively reshape them in the direction they believe will lead to the highest score (the negative of the Rosetta energy). The player’s current status is shown, along with a leaderboard of other players, and groups of players working together, competing in the same puzzle (Fig. 1, arrows 8-9). To make the game approachable by players with no scientific training, many technical terms are replaced by terms in more common usage. We remove protein elements that hinder structural problem solving, and highlight energetically frustrated areas of the protein where the player can likely improve the structure (Fig. 1, arrows 1-5). Sidechains are colored by hydrophobicity and the backbone is colored by energy. There are specific visual cues depicting hydrophobicity (“exposed hydrophobics”), interatomic repulsion (“clashes”), and cavities (“voids”). The players are given intuitive direct manipulation tools. The most immediate method of interaction is directly pulling on the protein. It is also possible to rotate helices and rewire beta sheet connectivity (“tweak”). Players are able to guide moves by introducing soft constraints (“rubber bands”) and fixing degrees of freedom (“freezing”) (Fig. 1, arrows 6-7). They are also able to change the strength of the repulsion term to allow more freedom of movement. Available automatic moves—combinatorial sidechain rotamer packing (“shake”), gradient-based minimization (“wiggle”), fragment insertion (“rebuild”)—are Rosetta optimizations modified to suit direct protein interaction and simplified to run at interactive speeds.
To engage players with no previous exposure to molecular biology, it was essential to introduce these concepts through a series of introductory levels (Fig. S1 and Table S1): puzzles that are always available, and can be completed by reaching a goal score. These levels teach the game’s tools and visualizations, and certain strategies. We have found the game to be approachable by a wide variety of people, not only those with a scientific background (Fig. S2); in fact, few top players are professionally involved in biochemistry (Fig. S3).
To evaluate players’ abilities to solve structure prediction problems, we posted a series of prediction puzzles. Puzzles in this series were blind, in the sense that neither the target protein nor homologous proteins had structures contained within publicly available databases for the duration of the puzzles. Detailed information for these 10 blind structures, including comparisons between the best scoring Foldit predictions and the best scoring Rosetta predictions using the rebuild and refine protocol7, is given in Table 1. We found that Foldit players were particularly adept at solving puzzles requiring substantial backbone remodeling to bury exposed hydrophobic residues into the protein core (Fig. 2). When a hydrophobic residue points outward into solvent, and no corresponding hole within the core is evident, stochastic Monte Carlo trajectories are unlikely to sample the coordinated backbone and sidechain shifts needed to properly bury the residue in the core. By adjusting the backbone to allow the exposed hydrophobic residue to pack properly in the core, players were able to solve these problems in a variety of blind scenarios including a register shift and a remodeled loop (Fig. 2a-b), a rotated helix (Fig. 2c), two remodeled loops (Fig. 2d), and a helix rotation and remodeled loop (Fig. 2e).
Players were also able to restructure beta sheets in order to improve hydrophobic burial and hydrogen bond quality. Automated methods have difficulty performing major protein restructuring operations to change beta sheet hydrogen-bond patterns, especially once the solution has settled in a local low-energy basin. Players were able to carry out these restructuring operations in such scenarios as strand swapping (Fig. 3) and register shifting (Fig. 2a). In one strand swap puzzle, Foldit players were able to get within 1.06 Å of the native, with the top scoring Foldit prediction being 1.36 Å away. A superposition between the starting Foldit puzzle, the top scoring Foldit solution, and model 1 of the native NMR structure 2kpo are shown in Fig. 3b. Rosetta’s rebuild and refine protocol, however, was unable to get within 2 Å of the native structure (Fig. 3a, yellow points). This example highlights a key difference between humans and computers. As shown in Fig. 3c, solving the strand swap problem required substantially unraveling the structure (Fig. 3c, bottom), with a corresponding unfavorable increase in energy (Fig. 3c, top). Players persisted with this reconfiguration despite the energy increase because they correctly recognized the swap could ultimately lead to lower energies. In contrast, while the Rosetta rebuild and refine protocol did sample some partially swapped conformations (Fig. 3a, leftmost yellow point), these were not retained in subsequent generations due to their relatively high energies, resulting in the top Rosetta prediction being further from the native than the starting structure (Fig. S5).
Human players are also able to distinguish which starting point will be most useful to them. Fig. 3d-e shows a case where players were given ten different Rosetta predictions to choose from. Players were able to identify the model closest to the native structure, and to improve it further. Given the same 10 starting models, the Rosetta rebuild and refine protocol was unable to get as close to the native as the top scoring Foldit predictions.
Foldit players performed similarly to the Rosetta rebuild and refine protocol for three of the 10 blind puzzles (Fig. S6). They outperformed Rosetta on five of the puzzles (Figs. 3, S5, and S7), including the two above cases where players performed significantly better. A larger set of successful solutions for similar, though non-blind, puzzles are described in Figs. S8, S9, and S10. For two of the 10 blind puzzles, the top Rosetta rebuild and refine prediction was numerically better than the Foldit solution (Table 1) but still basically incorrect (RMSD to native structure > 5.7 Å) (Fig. S11).
Despite the promising results described above, there still exists room for improvement. For one particularly difficult class of problems, players are only given an extended protein chain to start from. Although the Foldit tools are sufficient to reach the native conformation from this unfolded start (Fig. S12), players can have trouble reaching it from so far away (Fig. S11a). This indicates the need to find the right balance between humans and computational methods; players guided by visual cues perform better in resolving incorrect features in partially correct models than “blank slate” de novo folding of an extended featureless protein chain.
As interesting as the Foldit predictions themselves is the complexity, variation and creativity of the human search process. Foldit gameplay supports both competition and collaboration between players. For collaboration, players can share structures with their group members, and help each other out with strategies and tips through the game’s chat function, or across the wiki. The competition and collaboration create a large social aspect to the game, which alters the aggregate search progress of Foldit and heightens player motivation. As groups compete for higher rankings and discover new structures, other groups appear to be motivated to play more (Fig. S14a), and within groups the exchange of solutions can help other members catch up to the leaders (Fig. S14b).
Humans use a much more varied range of exploration methods than computers. Different players use different move sequences, both according to the puzzle type and throughout the duration of a puzzle (Fig. 4a). For example, some players prefer to manually adjust sidechains; some will forego large amounts of continuous minimization at the beginning of a puzzle, but increase it as the puzzle progresses; and some prefer a more direct approach and use more rubber bands when the puzzle begins from an extended chain. Within teams, there is often a division of labor; some players specialize in early stage openings, others in middle and end game polishing. Our informal investigation revealed a fascinating array of thought processes, insights and previously unexplored methodologies developed solely through Foldit gameplay (see Supplemental Text, Player Testimonials section and Table S3 for more information).
In designing Foldit we sought to maximize both engagement by a wide range of players (a requirement common to all games), and the scientific relevance of the game outcomes (unique to Foldit). We fine-tuned the game through continuous iterative refinement based on observations of player activity and feedback, taking approaches from players who did well and making them accessible to all players. Most of the tools available to players today are a product of this refinement. They either did not initially exist or have undergone major revision. The introductory levels were also iteratively tuned to reduce player attrition due to difficulty or lack of engagement. Just as Foldit players gained expertise by playing Foldit, both individually and collectively, the game itself adapted to players’ best practices and skill sets. We suspect that this process of co-adaptation of game and players should be applicable to similar scientific discovery games.
To attract the widest possible audience for the game and encourage prolonged engagement, we designed the game so that the supported motivations and the reward structure are diverse, including short-term rewards (game score), long-term rewards (player status and rank), social praise (chats and forums), the ability to work individually or in a team, and the connection between the game and scientific outcomes. A survey of Foldit players (Fig. S4) revealed that while the purpose of contributing to science is a motivating factor for many players, Foldit also attracts players interested in achievement through competition and point accumulation, social interaction through chat and web-based communication, and immersion through engaging gameplay and exploration of protein shapesix. We expect generally future scientific discovery games will also benefit from varied motivation sets.
There is still much to be learned about the basis for human achievement with Foldit, which will require more specific analysis of how players acquire domain expertise through gameplay, and can discover promising solutions. Such insights could also lead to improved automated algorithms for protein structure prediction.
The solution of challenging structure prediction problems by Foldit players demonstrates the considerable potential of a hybrid human-computer optimization framework in the form of a massively multiplayer game. The approach should be readily extendable to related problems, such as protein design and other scientific domains where human 3D structural problem solving can be leveraged. Our results suggest that scientific advancement is possible if even a small fraction of the energy that goes into playing computer games can be channeled into scientific discovery.
The authors would like to thank David Salesin, Kathleen Tuite, Joshua Snyder, Daniel Suskin, Philipp Krahenbuhl, Alex Cho Snyder, Hao Lu, Lu Sien Tan, Alex Chia, Ming Yao, Eric Butler, Chris Carrico, Philip Bradley, Ian Davis, David Kim, Rhiju Das, Will Sheffler, James Thompson, Oliver Lange, Robert Vernon, Bruno Correia, David Anderson, Yutong Zhao, Sayer Herin, and Benjamin Bethurum for their help. We would like to thank Nobuyashu Koga, Rie Koga, and Ashley Deacon and the JCSG for providing us with protein structures before their public release. We would also like to acknowledge all the Foldit players who have made this work possible. Players whose solutions were used in figures can be found in Table S4. This work was supported by NSF grants IIS0811902 and 0906026, DARPA grant N00173-08-1-G025, the DARPA PDP program, the Howard Hughes Medical Institute (D.B.), Microsoft, and an NVIDIA Fellowship. This material is based upon work supported by the National Science Foundation under a grant awarded in 2009.
All authors contributed extensively to the work presented in this paper.
Supplementary Information accompanies the paper on www.nature.com/nature.