Algorithm discovery by protein folding game players

Abstract

Foldit is a multiplayer online game in which players collaborate and compete to create accurate protein structure models. For specific hard problems, Foldit player solutions can in some cases outperform state-of-the-art computational methods. However, very little is known about how collaborative gameplay produces these results and whether Foldit player strategies can be formalized and structured so that they can be used by computers. To determine whether high performing player strategies could be collectively codified, we augmented the Foldit gameplay mechanics with tools for players to encode their folding strategies as "recipes" and to share their recipes with other players, who are able to further modify and redistribute them. Here we describe the rapid social evolution of player-developed folding algorithms that took place in the year following the introduction of these tools. Players developed over 5,400 different recipes, both by creating new algorithms and by modifying and recombining successful recipes developed by other players. The most successful recipes rapidly spread through the Foldit player population, and two of the recipes became particularly dominant. Examination of the algorithms encoded in these two recipes revealed a striking similarity to an unpublished algorithm developed by scientists over the same period. Benchmark calculations show that the new algorithm independently discovered by scientists and by Foldit players outperforms previously published methods. Thus, online scientific game frameworks have the potential not only to solve hard scientific problems, but also to discover and formalize effective new strategies and algorithms.

Fig. 1.

Foldit recipes are used with very different frequencies. Each bar represents a different Foldit recipe; the height of the bar shows the number of times the recipe was used, and the colors denote different Foldit players. Blue Fuse, at the very left, was run by many players a total of 24,273 times; the creator of Blue Fuse alone (large pink region) used it over 2,000 times. Most recipes (those represented by many colors) were run by different players; in contrast, 0 bounce 00.080 (all pink bar) is a private unshared recipe.

Fig. 2.

Foldit players employ different recipes at different stages of gameplay. The relative frequency of usage for each recipe category is shown for three different stages of gameplay (blue, first third of gameplay; red, second third; green, final third) for all players (A) and for top ranked players (B). All players use local optimize recipes more frequently as gameplay progresses (A), and this trend is even stronger among top players (B). The usage frequency for each individual recipe is shown in detail in Fig. S2. The actual context dependence of the use of different recipes is likely greater than that shown in the figure; the division based on elapsed game time used here is relatively crude because different players in different puzzles may spend very different amounts of time on the opening, middle game, and end game.

Fig. 3.

Rapid proliferation of Foldit recipes between June 2009 and August 2010. Each different shade of gray represents an individual recipe with the size of the gray bar denoting how many times that recipe was run that particular week. The most heavily used script recipe is Blue Fuse, shown in yellow. The most popular GUI recipe is Quake, shown in red, which has been used consistently by Foldit players weekly since its creation.

Fig. 4.

Social evolution of Foldit recipes. Each circle represents a different Foldit recipe, each color denotes a different author, and the size is the logarithm of the number of times a recipe was used. Arrows represent the process of copying and subsequent modification: the recipe at the tip of an arrow was created from the recipe at the base of the arrow. Acid Tweeker v0.5 is the parent of all of the recipes shown here with Blue Fuse its most popular offspring. The popularity of Blue Fuse led many Foldit players to create their own modified versions of the recipe.

Fig. 5.

Performance comparison between Rosetta Relax protocols and Foldit recipes. Each optimization protocol was run on a benchmark set of 6,758 models from 62 different proteins, and the average energy was calculated over all models after different numbers of iterations. The x-axis denotes the total CPU time in seconds and the y-axis represents the Rosetta energy. Foldit recipe Blue Fuse samples lower energies than Classic Relax and reaches these energies in much less time, but Fast Relax is even faster and more effective at energy optimization. A Deep Breath combines two other recipes (Breathe and Breathe Too) with Blue Fuse, resulting in a longer average runtime but lower overall energies compared to Blue Fuse.

Fig. 6.

Similarity between the unpublished Rosetta protocol Fast Relax and the Foldit recipe Blue Fuse. Equivalent steps in the two algorithms are represented with the same color. The repulsive interaction strength is reset from high to low in each cycle of Fast Relax; in Rosetta 5–15 iterations are typically used.

Fig. 7.

Performance comparison between Blue Fuse and Rosetta Fast Relax protocol using the streamlined Foldit minimization and side chain optimization routines. The dark green line shows the performance of Fast Relax encoded using the Foldit scripting interface. Fast Relax still samples lower energies than Blue Fuse, but takes longer to do so than Fast Relax in Rosetta. Blue Fuse is more effective than the Foldit version of Fast Relax on time scales most compatible with gameplay: the average Blue Fuse runtime during actual gameplay of 122 s is indicated by the dotted line.