TL;DR
This paper analyzes data from "Phylo," a crowdsourced game for improving DNA sequence alignments, to understand how to build more effective human-computation systems. They found that puzzle difficulty can be predicted, experienced players perform better on harder tasks, and that even simplified scoring can lead to significant improvements in complex biological problems.
What Problem Does This Paper Address?
Multiple Sequence Alignment (MSA) is a fundamental problem in bioinformatics, crucial for understanding DNA and protein function, evolution, and identifying important motifs. While computational algorithms can generate MSAs, they are often suboptimal and require manual curation by experts. This manual process is a bottleneck, especially with the explosion of genomic data. The authors propose using human computation, specifically through a game called "Phylo," to address this challenge. Phylo transforms MSA problems into casual tile-matching puzzles, making them accessible to non-experts. This paper aims to analyze the data generated by Phylo to extract lessons for designing better human-computation systems for genomics and beyond.
Methods
The researchers employed a multi-faceted approach to analyze Phylo's data:
- Puzzle Difficulty Prediction: They developed machine learning models (logistic regression, neural networks, etc.) to predict puzzle difficulty using features derived from the machine-computed alignments (e.g., sequence length, entropy, GC content). They also explored regression models to predict the expected score gain from human input.
- Solution Aggregation: A pipeline was designed to filter and combine user-submitted solutions to improve the original machine-computed alignments. This involved selecting high-scoring and low-entropy solutions.
- User Profiling: They analyzed user behavior and performance, categorizing players into "rookies" vs. "experts" (based on puzzles played) and "casual gamers" vs. "educational players" (based on background knowledge).
- Accuracy Evaluation: The quality of human-improved alignments was assessed using two main methods:
- Robinson-Foulds (RF) distance: Comparing phylogenetic trees inferred from machine-computed vs. human-computed alignments against known phylogenetic trees.
- Entropy: Measuring the conservation of alignment columns, where lower entropy indicates higher conservation.
Datasets
The primary dataset used in this study is the 5-year collection of data from the Phylo game, comprising:
- 1907 alignment puzzles extracted from 575 genomic regions.
- Each puzzle involves 2-8 DNA sequences from vertebrate species, with lengths between 10 and 21 characters.
- A total of 465,027 puzzle solutions were collected from over 400,000 unique users.
The paper also mentions using the UCSC Genome Browser for reference phylogenetic trees.
Key Insights and Ideas
- Difficulty is Predictable: The difficulty of an MSA puzzle can be reasonably predicted using features derived from the initial machine-generated alignment. This is crucial for efficiently routing tasks to appropriate players.
- Experience Matters for Hard Tasks: While casual and experienced players perform similarly on easy puzzles, experts significantly outperform rookies on medium and hard puzzles. This highlights the value of long-term engagement in human-computation systems.
- Background Knowledge Not a Major Factor (for this game): Interestingly, prior knowledge of the biological problem (multiple sequence alignment) did not significantly improve performance compared to casual gamers, suggesting the game's design effectively abstracts the complexity.
- Simplified Scoring Works: Even a basic, simplified scoring scheme for puzzles was sufficient to achieve significant improvements when aggregating user solutions. This implies that intuitive game design can effectively harness collective intelligence.
- No Single "Gold Standard": The paper emphasizes that there isn't one perfect metric to evaluate alignment quality. Combining different evaluation methods (like RF distance and entropy) provides a more robust assessment.
- Rapid Improvement is Key: Most alignment score improvements are achieved relatively quickly (within ~100 days of puzzle release), suggesting that puzzles can be retired after a certain period to optimize resource allocation.
Key Results
- Difficulty Prediction Accuracy: Machine learning models achieved good accuracy in predicting puzzle difficulty, with features like sequence dissimilarity (tree-entropy) and initial alignment score being highly informative. Neural networks achieved an R² value of 72% in predicting score gain.
- User Performance: Experts outperformed rookies on medium (P-value 0.94) and hard (P-value 0.018) puzzles, demonstrating the benefit of accumulated experience.
- Alignment Improvement:
- Using known phylogenetic trees, aggregation of user solutions improved alignments by 36.7%.
- When phylogenetic trees were unknown, aggregation improved alignments by 66.3% based on entropy reduction.
- Efficiency Gains: Predicting puzzle difficulty and routing tasks accordingly led to efficiency gains, particularly for easy puzzles, by avoiding unnecessary calculations.
- Ebola Virus Case Study: Phylo was used to improve alignments of Ebola virus sequences, demonstrating its utility for rapid scientific data curation during emergencies.
Limitations and Future Work
- Limitations:
- The difference in accuracy between human and machine-computed alignments using RF distance was not statistically significant, partly due to many identical solutions.
- The benefit of background knowledge was difficult to assess and disappeared with increasing puzzle difficulty.
- Future Work:
- Further exploration of customized training mechanisms for GWAPs.
- Developing novel alignment heuristics inspired by human strategies, similar to how Foldit has been used.
- Collecting more data on player progression within puzzles to better understand the dynamics of learning and improvement.
- Exploring how to better characterize the nature and magnitude of factors influencing system performance.
Summary updated