Algorithm discovery by protein folding game players
Algorithm discovery by protein folding game players
复制标题
DOI：
10.1073/pnas.1115898108
复制
发表时间：
2011-11-22
影响因子：
11.1
通讯作者：
Baker, David
中科院分区：
文献类型：
--
作者：
Khatib, Firas;Cooper, Seth;Baker, David
Foldit 是一款多人在线游戏，玩家可以合作并竞争来创建准确的蛋白质结构模型。对于特定的难题，Foldit 播放器解决方案在某些情况下可以超越最先进的计算方法。然而，对于协作游戏如何产生这些结果以及 Foldit 玩家策略是否可以形式化和结构化以便计算机可以使用，人们知之甚少。为了确定高性能玩家策略是否可以集体编码，我们通过工具增强了 Foldit 游戏机制，让玩家将其折叠策略编码为“食谱”，并与其他玩家分享他们的食谱，其他玩家可以进一步修改和重新分发它们。在这里，我们描述了玩家开发的折叠算法在引入这些工具后的一年中发生的快速社会演变。玩家通过创建新算法以及修改和重新组合其他玩家开发的成功食谱，开发了超过 5,400 种不同的食谱。最成功的食谱在 Foldit 玩家群体中迅速传播，其中两个食谱变得尤其占主导地位。对这两个配方中编码的算法的检查发现，它与科学家在同一时期开发的未发表的算法有着惊人的相似性。基准计算表明，科学家和 Foldit 玩家独立发现的新算法优于之前发布的方法。因此，在线科学游戏框架不仅有可能解决科学难题，而且有可能发现并形式化有效的新策略和算法。
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.