Abstract
Recent algorithmic advances have enabled the inference of genome-wide ancestral recombination graphs (ARGs) from large genomic cohorts, providing detailed models of genealogical relatedness along the genome. These inferred ARGs can complement genotype imputation by capturing the effects of unobserved variants, but their use in large-scale linear mixed-model analyses has been computationally prohibitive. Here, we develop methods that leverage the ARG to perform genotype-matrix multiplications in sublinear time and implement scalable randomized algorithms for mixed-model analyses. We introduce ARG-RHE, a randomized Haseman-Elston approach for estimating narrow-sense heritability and performing region-based association testing using ARGs, enabling parallel analysis of multiple quantitative traits. Through extensive simulations, we demonstrate the computational efficiency and statistical power of this approach. Applied to 21,159 genes and 52 blood traits in 337,464 UK Biobank participants, ARG-RHE identifies 8% more gene-trait associations than imputation alone, demonstrating that genome-wide genealogies may be leveraged to complement genotype imputation in complex trait analyses.