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.

Continue Reading

Acknowledgments.

We thank the members of the Foldit team for their help designing and developing the game and all the Foldit players who have made this work possible. This work was supported by the Center for Game Science, Defense Advanced Research Projects Agency (DARPA) Grant N00173-08-1-G025, the DARPA Protein Design Processes (PDP) program, National Science Foundation (NSF) Grants IIS0811902 and IIS0812590, the Howard Hughes Medical Institute (D.B.), a Henry Wellcome Postdoctoral Fellowship (M.D.T), Adobe and Microsoft. This material is based upon work supported by the National Science Foundation under Grant 0906026.

Supporting Information

Supporting Information (PDF)
Supporting Information

References

1
C Lintott, et al., Galaxy Zoo: ‘Hanny’s Voorwerp’, a quasar light echo? Mon Not R Astron Soc 399, 129–140 (2009).
2
AJ Westphal, et al., Non-destructive search for interstellar dust using synchrotron microprobes. X-ray Optics and Microanalysis: Proceedings of the 20th International Congress (American Institute of Physics (AIP), Melville, NY) CP1221, 131–138 (2010).
4
S Cooper, et al., The challenge of designing scientific discovery games. Proceedings of the Fifth international Conference on the Foundations f Digital Games (FDG ACM, New York, NY) 10, 40–47 (2010).
5
S Cooper, et al., Predicting protein structures with a multiplayer online game. Nature 466, 756–760 (2010).
6
CA Rohl, CE Strauss, KM Misura, D Baker, Protein structure prediction using Rosetta. Methods Enzymol 383, 66–93 (2004).
7
F Khatib, et al., Crystal structure of monomeric retroviral protease solved by protein folding game players. Nat Struct Mol Biol 18, 1175–1177 (2011).
9
M Banerji, et al., Galaxy Zoo: Reproducing galaxy morphologies via machine learning. Mon Not R Astron Soc 406, 342–353 (2010).
10
S Cooper, et al., Analysis of social gameplay macros in the Foldit cookbook. Proceedings of the Sixth international Conference on the Foundations f Digital Games (FDG ACM, New York, NY) 11 (2011).
11
M Levitt, A Warshel, Computer simulation of protein folding. Nature 253, 694–698 (1975).
12
B Kuhlman, et al., Design of a novel globular protein fold with atomic-level accuracy. Science 302, 1364–1368 (2003).
13
M Levitt, Protein folding by restrained energy minimization and molecular dynamics. J Mol Biol 170, 723–764 (1983).
14
The Programming Language Luahttp://www.lua.org/.

Information & Authors

Information

Published in

Go to Proceedings of the National Academy of Sciences
Go to Proceedings of the National Academy of Sciences
Proceedings of the National Academy of Sciences
Vol. 108 | No. 47
November 22, 2011
PubMed: 22065763

Classifications

Submission history

Published online: November 7, 2011
Published in issue: November 22, 2011

Keywords

  1. citizen science
  2. crowd-sourcing
  3. optimization
  4. structure prediction
  5. strategy

Acknowledgments

We thank the members of the Foldit team for their help designing and developing the game and all the Foldit players who have made this work possible. This work was supported by the Center for Game Science, Defense Advanced Research Projects Agency (DARPA) Grant N00173-08-1-G025, the DARPA Protein Design Processes (PDP) program, National Science Foundation (NSF) Grants IIS0811902 and IIS0812590, the Howard Hughes Medical Institute (D.B.), a Henry Wellcome Postdoctoral Fellowship (M.D.T), Adobe and Microsoft. This material is based upon work supported by the National Science Foundation under Grant 0906026.

Authors

Affiliations

Firas Khatib
Department of Biochemistry;
Seth Cooper
Department of Computer Science and Engineering; and
Michael D. Tyka
Department of Biochemistry;
Kefan Xu
Department of Computer Science and Engineering; and
Ilya Makedon
Department of Computer Science and Engineering; and
Zoran Popović
Department of Computer Science and Engineering; and
Department of Biochemistry;
Howard Hughes Medical Institute, University of Washington, Box 357370, Seattle, WA 98195

Notes

1
To whom correspondence should be addressed. E-mail: [email protected].
Contributed by David Baker, October 5, 2011 (sent for review June 29, 2011)
Author contributions: F.K., S.C., Z.P., and D.B. designed research; F.K., S.C., M.D.T., and F.P. performed research; F.K., S.C., M.D.T., K.X., and I.M. analyzed data; and F.K., S.C., Z.P., and D.B. wrote the paper.

Competing Interests

The authors declare no conflict of interest.

Metrics & Citations

Metrics

Note: The article usage is presented with a three- to four-day delay and will update daily once available. Due to ths delay, usage data will not appear immediately following publication. Citation information is sourced from Crossref Cited-by service.


Citation statements

Altmetrics

Citations

If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.

Cited by

    Loading...

    View Options

    View options

    PDF format

    Download this article as a PDF file

    DOWNLOAD PDF

    Get Access

    Login options

    Check if you have access through your login credentials or your institution to get full access on this article.

    Personal login Institutional Login

    Recommend to a librarian

    Recommend PNAS to a Librarian

    Purchase options

    Purchase this article to get full access to it.

    Single Article Purchase

    Algorithm discovery by protein folding game players
    Proceedings of the National Academy of Sciences
    • Vol. 108
    • No. 47
    • pp. 18855-19096

    Media

    Figures

    Tables

    Other

    Share

    Share

    Share article link

    Share on social media