Sparse Linear Algebra Accelerates Genotype Representation Graph Computation at Biobank Scale
- 1Cornell University
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 Mikado, 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, Mikado 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.8x 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.
Related
- Biobank-scale self-supervised genotype pretraining yields transferable representations for human genetics
- A Lymphomimetic Synthetic Immune Niche, Consisting of CCL21 and ICAM1, Accelerates the Expansion of Potent CAR T-cells
- Bcl-x Inactivation in Macrophages Accelerates Progression of Advanced Atherosclerotic Lesions in Apoe −/− Mice
- CORONAVIRUS INFECTION ACCELERATES EXPERIMENTAL OSTEOPOROSIS THROUGH THE ACTIVATION OF OSTEOCLASTS
- Hydrodynamic flow in the gut hinders the fixation of beneficial mutants but accelerates their invasion
BibTeX
@misc{li2026sparse,
title = {{Sparse Linear Algebra Accelerates Genotype Representation Graph Computation at Biobank Scale}},
author = {Y. Li and Q. Sun and D. DeHaas and M. X. Zhao and A. A. Boyko and S. A. Musharoff and X. Wei and G. Guidi},
howpublished = {bioRxiv},
year = {2026},
month = sep,
doi = {10.64898/2026.09.10.750583},
url = {https://www.biorxiv.org/content/10.64898/2026.09.10.750583v1},
note = {CC BY},
}
RIS
TY - UNPB
TI - Sparse Linear Algebra Accelerates Genotype Representation Graph Computation at Biobank Scale
AU - Y. Li
AU - Q. Sun
AU - D. DeHaas
AU - M. X. Zhao
AU - A. A. Boyko
AU - S. A. Musharoff
AU - X. Wei
AU - G. Guidi
PY - 2026
DA - 2026/09/10
PB - bioRxiv
DO - 10.64898/2026.09.10.750583
UR - https://www.biorxiv.org/content/10.64898/2026.09.10.750583v1
AB - 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 Mikado, 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, Mikado 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.8x 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.
ER -