Sparse Linear Algebra Accelerates Genotype Representation Graph Computation at Biobank Scale
Preprint
Abstract
Biobank-scale genomic analyses are increasingly constrained by computational costs, as hundreds of thousands to millions of samples and variants must be analyzed together. The genotype representation graph (GRG) compactly encodes population genetic variation to accelerate computation, but its graph-traversal implementation does not exploit modern accelerators. This work introduces M ikado , a methodology that expresses GRG-based computation using sparse linear algebra primitives. Under a reverse topological ordering, the GRG adjacency matrix is strictly block-lower-triangular, and the genotype matrix-vector product becomes a sparse triangular solve, decomposed into a pipelined sequence of blocked sparse matrix-vector multiplies. Because GRGs are shallow by construction, the solve completes in only a few sequential stages, exposing fine-grained parallelism and enabling vendor-optimized sparse primitives on GPUs. On the full All of Us cohort, M ikado computes principal components in minutes , where PLINK2 cannot complete one chromosome in 72 hours, and runs genome-wide BOLT-LMM-inf in under 19 minutes on one GPU, where the official BOLT-LMM analysis would be impractical. Our two-stage reformulation is independent of the hardware: the same code runs unchanged across GPU architectures and, on CPUs, gives a 1.8 × single-threaded speedup over the existing GRG library together with multi-threaded scaling, providing a scalable, portable approach for population genetics as biobanks continue to grow.Keywords
Funding Information
- NSF (IIS-243580)
- NIH (R35-GM150579)
This publication has 49 references indexed in Scilit:
- A review of self-scheduled strategies for numerical linear algebra on GPUComputer Science Review, 2026
- Sparse modeling of interactions enables fast detection of genome-wide epistasis in biobank-scale studiesThe American Journal of Human Genetics, 2025
- Distinct explanations underlie gene-environment interactions in the UK BiobankThe American Journal of Human Genetics, 2025
- Genotype × environment interactions in gene regulation and complex traitsNature Genetics, 2024
- Genomic data in the All of Us Research ProgramNature, 2024
- Leveraging phenotypic variability to identify genetic interactions in human phenotypesThe American Journal of Human Genetics, 2021
- A Synchronization-Free Algorithm for Parallel Sparse Triangular Solves2016
- Efficient Bayesian mixed-model analysis increases association power in large cohortsNature Genetics, 2015
- Sparsifying Synchronization for High-Performance Shared-Memory Sparse Triangular Solver2014
- A quasi-Newton acceleration for high-dimensional optimization algorithmsStatistics and Computing, 2009