MaSk-LMM: A Matrix Sketching Framework for Linear Mixed Models in Association Studies

Myson Burch, Aritra Bose, Gregory Dexter, Laxmi Parida, Petros DrineasmedRxiv 2023 · DOI

Abstract

Linear mixed models (LMMs) have been widely used in genome-wide association studies (GWAS) to control for population stratification and cryptic relatedness. Unfortunately, estimating LMM parameters is computationally expensive, necessitating large-scale matrix operations to build the genetic relatedness matrix (GRM). Over the past 25 years, Randomized Linear Algebra has provided alternative approaches to such matrix operations by leveraging matrix sketching, which often results in provably accurate fast and efficient approximations. We leverage matrix sketching to develop a fast and efficient LMM method called Matrix-Sketching LMM (MaSk-LMM) by sketching the genotype matrix to reduce its dimensions and speed up computations. Our framework comes with both theoretical guarantees and a strong empirical performance compared to current state-of-the-art.

Introduction

Genome-Wide Association Studies (GWAS) are essential for identifying genetic markers (SNPs) linked to diseases. However, these studies are often plagued by "population stratification"—genetic similarities between individuals that can lead to false-positive results. Linear Mixed Models (LMMs) are the gold standard for correcting these biases, but they come with a heavy computational price tag.

Standard LMMs require matrix operations (like inversions and multiplications) that scale cubically ($O(n^3)$) with the number of samples ($n$). As modern biobanks grow to include hundreds of thousands or even millions of individuals, these calculations become a massive bottleneck. While existing tools like BOLT-LMM and Regenie use heuristics to speed things up, they often lack a rigorous theoretical foundation to guarantee accuracy.

Methods

The authors propose MaSk-LMM (Matrix-Sketching LMM), which leverages techniques from Randomized Linear Algebra. The core idea is to "sketch" the massive genotype matrix $Z$ ($n$ individuals by $m$ markers) into a much smaller matrix by multiplying it with random sketching matrices ($S_1$ for samples and $S_2$ for markers).

Overview of the MaSk-LMM framework comparing standard LMM computation with the proposed matrix sketching approach.

Key methodological highlights include:

  • Dual Sketching: It reduces dimensions in both the sample space and the marker space simultaneously.
  • Gaussian Sketching: The framework uses random matrices where entries are drawn from a Gaussian distribution, which simplifies the math and provides strong theoretical properties.
  • Approximate GRM: Instead of building a full Genetic Relatedness Matrix (GRM), MaSk-LMM computes a sketched version that is much faster to invert and manipulate during variance estimation.

Experimental Evaluation

The researchers evaluated MaSk-LMM using both synthetic and real-world data:

  • Simulated Genotypes: They used a "mosaic-chromosome" scheme to create datasets mimicking British and Irish ancestries, ranging from 10,000 to 500,000 samples.
  • Real-World Biobank Data: They utilized the UK Biobank for two major conditions: Hypertension (HYP) (~330,000 samples and 4.5 million SNPs) and Coronary Artery Disease (CAD) (~50,000 samples and 5.3 million SNPs).

Key Insights and Results

Theoretical and Empirical Accuracy

This paper provides the first theoretical result of its type for LMMs, proving that marker sketching results in "bounded accuracy loss." This moves the field from heuristic-based approaches to mathematically guaranteed ones. Furthermore, the success of the method highlights that the genetic marker space is highly redundant; the data can be compressed significantly (using only 5-10% of original dimensions) while still capturing the essential signal.

Comparison of causal and spurious associations across different sample sizes for MaSk-LMM, Regenie, and BoltLMM.

Performance Benchmarks

MaSk-LMM demonstrated massive performance gains without sacrificing biological relevance:

  • Speed: On simulated data, MaSk-LMM was 49x faster than BOLT-LMM and 68x faster than Regenie. Even on the largest 500k sample dataset, it maintained a nearly 20x speedup over BOLT-LMM.
  • Noise Reduction: Surprisingly, in simulations, MaSk-LMM captured fewer spurious (false) associations than state-of-the-art methods at large scales, suggesting that sketching might act as a form of regularization that filters out noise.
  • Biological Discovery: In the Hypertension dataset, MaSk-LMM identified 723 significant SNPs, sharing 22 of the top associations with Regenie and identifying several novel "Loss of Function" markers.

Conclusion and Future Work

MaSk-LMM offers a scalable, theoretically grounded alternative for large-scale genomic studies. Despite its strengths, the authors note areas for improvement, such as implementing "Leave-One-Chromosome-Out" (LOCO) cross-validation to prevent proximal contamination. While they proved the accuracy of marker sketching, theoretical guarantees for sample sketching remain an open research question. Future software optimizations, including porting the Python-based library to C++ with MPI, could unlock even greater performance for massive biobank-scale data.

Summary updated

Abstract

Abstract Linear mixed models (LMMs) have been widely used in genome-wide association studies (GWAS) to control for population stratification and cryptic relatedness. Unfortunately, estimating LMM parameters is computationally expensive, necessitating large-scale matrix operations to build the genetic relatedness matrix (GRM). Over the past 25 years, Randomized Linear Algebra has provided alternative approaches to such matrix operations by leveraging matrix sketching , which often results in provably accurate fast and efficient approximations. We leverage matrix sketching to develop a fast and efficient LMM method called Ma trix- Sk etching LMM ( MaSk-LMM ) by sketching the genotype matrix to reduce its dimensions and speed up computations. Our framework comes with both theoretical guarantees and a strong empirical performance compared to current state-of-the-art.
BibTeX
@misc{burch2023mask,
  author = {Myson Burch and Aritra Bose and Gregory Dexter and Laxmi Parida and Petros Drineas},
  title = {{MaSk-LMM: A Matrix Sketching Framework for Linear Mixed Models in Association Studies}},
  year = {2023},
  doi = {10.1101/2023.11.13.23298469},
  howpublished = {medRxiv},
}
Figure