A near-exact linear mixed model for genome-wide association studies

Linear mixed models (LMM) are widely adopted in genome-wide association studies (GWAS) to account for population stratification and cryptic relatedness. However, the parameter estimation of LMMs imposes substantial computational burdens due to large-scale operations on genetic similarity matrices (GSM). We introduced the near-exact linear mixed model (NExt-LMM), a novel LMM framework that overcomes critical computational bottlenecks in GWAS through the following key innovations. Firstly, we exploit the inherent low-rank structure of the GSM iteratively with the Hierarchical Off-Diagonal Low-Rank (HODLR) format, which is much faster than traditional decomposition methods. Secondly, we leverage the HODLR-approximated GSM to dramatically accelerate the further maximum likelihood estimation with the shared heritability ratios. Moreover, we establish rigorous error bounds for the NExt-LMM estimator, proving that Kullback-Leibler divergence between the approximated and exact estimators can be arbitrarily small. Consequently, our proposed dual approach accelerates inference of LMMs while guaranteeing low approximation errors. We use numerical experiments to demonstrate that the NExt-LMM significantly improves inference efficiency compared to existing methods. We develop a Python package that is available at https://github.com/ZhibinPU/NExt-LMM.