Abstract
Existing methods for identifying human population structure often require prior knowledge of individual ancestry. We present a novel, unsupervised algorithm based on Principal Component Analysis (PCA) that selects small subsets of SNPs (PCA-correlated SNPs) to reproduce the structure found in complete genome-wide datasets. Validated on global populations and HapMap data, our method achieves perfect intercontinental differentiation with as few as 14 SNPs and distinguishes closely related populations like Han Chinese and Japanese with fewer than 100 SNPs. The algorithm also effectively predicts ancestry proportions in admixed populations, such as Puerto Ricans, and runs in seconds on large datasets, facilitating stratification assessment in association studies and demographic research.
Introduction
The identification of population structure is a cornerstone of modern human genetics. It provides insights into our evolutionary past and is essential for the integrity of medical genetic research. In genome-wide association studies (GWAS), "population stratification"—unobserved ancestral differences between cases and controls—can lead to spurious associations, masking true biological signals. Traditionally, selecting informative genetic markers to account for this structure has relied on supervised methods that require pre-labeled ancestry information. However, such information is not always available or accurate.
The PCA-Correlated SNP Algorithm
To address these limitations, we developed an unsupervised approach leveraging Principal Component Analysis (PCA) and Singular Value Decomposition (SVD). While standard PCA identifies "eigenSNPs" (mathematical abstractions), our algorithm selects a small subset of actual, physical SNPs that are most highly correlated with the top principal components of the entire dataset.
The selection process involves calculating a score ($p_j$) for every SNP based on its contribution to the significant eigenvectors. We utilize random matrix theory to determine the number of significant principal components, ensuring the selection captures real biological structure rather than random noise. Once these PCA-correlated SNPs are identified, simple clustering algorithms like k-means can be used to assign individuals to populations with high accuracy.
Experimental Results and Validation
Our method was rigorously tested across several diverse datasets. In a worldwide dataset of 11 populations, we achieved perfect intercontinental differentiation using only 14 PCA-correlated SNPs. When applied to the HapMap Phase II dataset, which contains 1.7 million SNPs, the algorithm successfully differentiated Han Chinese from Japanese populations—a task requiring high resolution—using fewer than 100 SNPs.
A key finding of our study is that structure-informative SNPs are generally not portable across different geographic regions. Markers that are highly informative for European populations may provide little to no resolution for African or Asian groups. Despite this, we identified a general panel of 50 SNPs that effectively assigns individuals to one of nine worldwide populations, demonstrating the extreme data compression possible with this approach.
Analysis of Admixed Populations
The utility of PCA-correlated SNPs extends to admixed populations, where individuals possess ancestry from multiple source groups. Analyzing Puerto Rican datasets, we demonstrated that our unsupervised method could successfully predict ancestry proportions and identify population substructure without prior knowledge of individual origins. This capability is crucial for studying populations with complex demographic histories.
Conclusion
The algorithm presented here is highly efficient, processing millions of markers in less than a minute on standard hardware. By enabling the rapid identification of population-informative markers without the need for prior ancestry labels, this method facilitates more robust association studies and deeper investigations into human demographic history. While future iterations may need to account for local linkage disequilibrium in increasingly dense datasets, PCA-correlated SNPs offer a powerful and practical solution for structure identification in global human populations.
Summary updated