TL;DR
This paper introduces two novel algorithms, SLDF_REML and L_FOMC_REML, that significantly speed up the computationally intensive process of estimating variance components in linear mixed-effects models (LMMs). These methods leverage the principle of Krylov subspace shift-invariance to achieve faster and more accurate results compared to existing approaches, making them highly suitable for large-scale genomic studies.
What Problem Does This Paper Address?
Genome-Wide Association Studies (GWAS) often rely on Linear Mixed-Effects Models (LMMs) to identify genetic variants associated with complex traits. A crucial step in LMM analysis is estimating variance components using Residual Maximum Likelihood (REML). However, traditional REML methods involve computationally demanding matrix operations (often cubic or quadratic in the number of individuals or markers), making them infeasible for the massive datasets common in modern genomics (e.g., biobanks with hundreds of thousands of individuals). Previous efforts have focused on reducing these computational costs by using iterative methods or looser tolerances. This paper tackles the challenge of making REML estimation computationally tractable for large-scale genomic data by developing novel algorithms that exploit the underlying mathematical structure of the problem more effectively.
Methods
The core innovation lies in two new algorithms: Stochastic Lanczos Derivative-Free REML (SLDF_REML) and Lanczos First-Order Monte Carlo REML (L_FOMC_REML). Both algorithms exploit the principle of "Krylov subspace shift-invariance." This mathematical property allows them to perform the most computationally expensive operations (involving iterative matrix operations) only once. Subsequent evaluations of the REML criterion and its derivatives can then be done using much faster vector operations.
- SLDF_REML: This algorithm is particularly efficient when precomputed genomic relatedness matrices (GRMs) are available, further accelerating computation. It's designed for derivative-free optimization.
- L_FOMC_REML: This algorithm is a first-order Monte Carlo approach, extending the ideas from existing methods like BOLT-LMM.
Both methods leverage the Lanczos procedure and stochastic trace estimation techniques to approximate complex matrix operations.
Datasets
The numerical experiments were conducted using data from the UK Biobank, specifically focusing on height measurements from unrelated European-ancestry individuals. The study used nested random subsamples ranging from 16,000 to 256,000 individuals, with 330,723 array single nucleotide polymorphisms (SNPs) and 24 covariates.
Key Insights and Ideas
- Krylov Subspace Shift-Invariance is Key: The paper demonstrates how this mathematical principle can be effectively harnessed to drastically reduce the computational burden of REML estimation. By performing expensive operations only once, subsequent calculations become significantly faster.
- Single Round of Expensive Computation: The novel algorithms require only a single round of iterative matrix operations, after which all subsequent evaluations can be performed using efficient vector operations. This is a major departure from methods that require these expensive operations at each iteration.
- SLDF_REML's GRM Advantage: The ability of SLDF_REML to leverage precomputed GRMs offers a significant speedup, especially when the number of markers far exceeds the number of individuals.
- Interpreted vs. Compiled Performance: Remarkably, the authors' interpreted-language (Python) implementations of the novel algorithms matched or exceeded the performance of existing compiled-language software packages in terms of speed, accuracy, and flexibility.
Key Results
- Speed: The novel algorithms, SLDF_REML and L_FOMC_REML, demonstrated significant speed improvements over existing methods, particularly for larger sample sizes. For instance, at n=256,000, L_FOMC_REML achieved a total time of 99.73 minutes, while BOLT-LMM v2.3.2 took 91.09 minutes, and the older BOLT-LMM v2.1 took 177.95 minutes. SLDF_REML with a precomputed GRM was the fastest at 38.60 minutes.
- Accuracy: The heritability estimates generated by SLDF_REML and L_FOMC_REML were highly consistent with those from the deterministic GCTA software package. For large sample sizes, the novel algorithms even showed greater accuracy than BOLT-LMM.
- Flexibility: The algorithms offer greater flexibility, particularly SLDF_REML's ability to use precomputed GRMs.
Limitations and Future Work
- Covariate Dependence (SLDF_REML): SLDF_REML's computational cost scales linearly with the number of covariates, which could become prohibitive if many covariates are included.
- Memory Complexity: Neither algorithm fundamentally reduces the substantial O(mn) or O(n²) memory requirements common to REML estimation, meaning high-memory compute nodes are still necessary for large datasets.
- Two-Component Model Limitation: The shift-invariance property exploited by these methods is limited to the two-component genomic variance model. Extending this to models with three or more variance components remains an open challenge.
- Future Work: The authors suggest that their methods, particularly stochastic trace estimation and stochastic Lanczos quadrature, could find applications in REML estimation for other models of interest in genomics. They also highlight the potential for further optimization through compiled implementations.
Summary updated