TL;DR
Researchers have developed SCOPE, a novel computational method that can infer human population structure from massive genomic datasets much faster than existing tools, making it practical for biobank-scale analyses. SCOPE achieves this speedup by employing efficient linear algebra techniques and can also leverage prior population frequency data for more interpretable results.
What Problem Does This Paper Address?
Understanding human population structure – how genetic variation is distributed across different groups – is crucial for fields ranging from evolutionary biology to personalized medicine. This knowledge helps researchers identify distinct ancestral groups, understand migration patterns, and account for genetic differences that can influence disease risk (a phenomenon known as population stratification). Traditionally, this has been done by analyzing genetic markers (like SNPs) across many individuals. However, the explosion of large-scale genomic datasets, such as the UK Biobank with nearly half a million individuals, has outpaced the capabilities of existing population structure inference methods. These older methods become computationally prohibitive, requiring excessive time and memory to process such vast amounts of data, thus limiting their application to these valuable resources.
Methods
The core of SCOPE builds upon a previously proposed likelihood-free framework for population structure inference. This framework involves two main steps:
- Latent Subspace Estimation (LSE): This step aims to estimate the underlying ancestral population structure by approximating a matrix derived from the genotype data. Instead of forming large, memory-intensive matrices, SCOPE uses randomized eigendecomposition (specifically, the implicitly restarted Arnoldi method). This allows it to efficiently compute the necessary components by repeatedly multiplying smaller matrices, significantly reducing memory requirements and computational cost.
- Alternating Least-Squares (ALS): Once the latent subspace is estimated, this step factorizes a derived matrix into two components: the ancestral population allele frequencies (P) and the individual admixture proportions (Q). SCOPE employs a truncated ALS approach, which, combined with the efficient LSE, allows for scalable estimation. Crucially, SCOPE avoids explicitly forming and storing the full admixture proportion matrix, further reducing memory demands.
A key innovation is the use of the Mailman algorithm for efficient matrix multiplications, especially when dealing with genotype matrices that contain only 0s, 1s, and 2s. This algorithm is particularly effective when there are repeated multiplications involving matrices with a finite alphabet, leading to substantial computational savings.
SCOPE also offers a supervised mode, where known allele frequencies from reference populations can be provided. This allows SCOPE to directly infer admixture proportions corresponding to those reference populations, enhancing interpretability.
Datasets
The authors evaluated SCOPE using a combination of simulated datasets and real-world genomic data:
- Simulated Datasets:
- Pritchard-Stephens-Donnelly (PSD) model simulations: These simulations mimic the assumptions of many existing population structure models.
- Spatial model simulations: These simulations introduce a spatial relationship between admixture proportions, testing the robustness of methods when model assumptions are violated.
- Simulations were generated using parameters derived from real datasets like the 1000 Genomes Project (TGP) and the Human Origins (HO) dataset.
- Real Datasets:
- 1000 Genomes Project (TGP): A widely used dataset for population genetics research.
- Human Origins (HO): Another dataset focused on human genetic variation.
- Human Genome Diversity Project (HGDP): A collection of samples from diverse human populations.
- UK Biobank (UKB): A large-scale resource containing genetic and phenotypic data from hundreds of thousands of individuals. The authors specifically used subsets of the UK Biobank data, including a PCA SNP set for exploring higher numbers of latent populations.
The paper also mentions using publicly available datasets and provides links to scripts for preprocessing and analysis, making their work reproducible.
Key Insights and Ideas
- Scalability is Paramount: The paper highlights that existing methods simply don't scale to biobank-sized datasets, creating a critical bottleneck for leveraging these rich resources. SCOPE directly addresses this by fundamentally rethinking the computational approach.
- Leveraging Linear Algebra for Speed: The core insight is that by using randomized linear algebra techniques and efficient matrix multiplication algorithms (like Mailman), SCOPE can perform the necessary calculations without the prohibitive memory and time costs of traditional methods.
- Memory Efficiency is Crucial: The authors emphasize that storing intermediate matrices for biobank-scale data is often impossible on standard hardware. SCOPE's design, avoiding explicit matrix formation, is key to its practicality.
- Supervised Inference for Interpretability: The ability to incorporate prior population allele frequencies is a powerful feature, allowing researchers to directly map inferred structures to known ancestral groups, which is invaluable for biological interpretation.
- Consistency Across Runs: SCOPE demonstrates good consistency in its results across multiple runs, even with stochastic approximations, which is important for reliable inference.
Key Results
- Speed: SCOPE is dramatically faster than existing methods. It can infer population structure on a simulated dataset of one million individuals and variants in about a day. For the UK Biobank dataset (488,363 individuals, 569,346 variants), it also takes about a day. Compared to the previous state-of-the-art scalable method, TeraStructure, SCOPE is 3 to 144 times faster. In some cases, it's over 1,800 times faster than other methods.
- Accuracy: SCOPE achieves comparable accuracy to existing methods, particularly under the PSD model. Under a spatial model, it performs very well, often being among the most accurate methods.
- Memory Usage: SCOPE has a manageable memory footprint, requiring less than 250 GB for the UK Biobank dataset and 750 GB for a one million individual/SNP dataset. This is significantly less than what would be required by methods that store full matrices.
- Supervised Analysis: In supervised settings, SCOPE shows improved accuracy, especially under the spatial model, and its results align well with self-reported ethnicity and ancestry labels.
Limitations and Future Work
- Choosing k (Number of Latent Populations): The paper acknowledges that while SCOPE allows users to run analyses with different values of k, it does not provide a definitive criterion for selecting the optimal number of latent populations. This remains an open question for future research.
- Interpretability of High k: While SCOPE can infer finer population structures with a large number of latent populations (k), interpreting these structures can be challenging. The authors note that the UK Biobank's PCA SNP set, while good for continental structure, might not be ideal for resolving very fine-scale intracontinental structure.
- Semi-Supervised Approaches: The authors suggest extending SCOPE to semi-supervised methods, where both known and unknown populations are present, potentially by combining supervised and unsupervised inference stages.
- Leveraging Linkage Disequilibrium (LD): Current methods, including SCOPE, largely ignore correlation patterns like LD. Developing scalable methods that can incorporate LD information is a promising direction for improving inference.
- Beyond Admixture: The paper points to other approaches for structure inference (e.g., non-linear dimensionality reduction, IBD analysis) and suggests exploring ways to scalably bridge these with admixture models.
- Domain Extension: The techniques used in SCOPE could potentially be extended to other domains like metagenomics and single-cell transcriptomics.
Summary updated