Biology subjects

DeHaas, D.

Publications and source records attributed to DeHaas, D..

5 recordsLinked to original sources

bioRxiv2026

Sparse Linear Algebra Accelerates Genotype Representation Graph Computation at Biobank Scale

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 the current approach does not exploit modern accelerator architectures. This work introduces Mikado, a new methodology for expressing GRG-based computation using sparse linear algebra primitives. Under a reverse topological ordering of the graph nodes, the GRG adjacency matrix is strictly block-lower-triangular, and the genotype matrix-vector product becomes a sparse triangular solve that can be further decomposed into a pipelined sequence of blocked sparse matrix-vector multiplies. By decoupling computation from graph representation, our approach exposes fine-grained parallelism and enables hardware-optimized sparse primitives on GPUs. Mikado achieves an order-of-magnitude speedup and cost savings for PCA and BOLT-LMM compared with the original GRG traversal approach, including on All of Us cohorts. It provides a scalable, hardware-portable, researcher-friendly tool for population genetics at biobank scale.

genomics↗

bioRxiv2026

General, orders-of-magnitude faster whole-genome analysis with genotype representation graphs

Whole-genome sequencing (WGS) of biobank-scale cohorts have generated datasets that traditional tabular genotype formats cannot efficiently store or analyze. Genotype Representation Graphs (GRGs) offer a compelling alternative: a biologically-motivated, hierarchical, graph-based representation that compactly and losslessly encodes the genotypes, and that supports computation directly on the graph rather than on a materialized genotype matrix. Here we introduce two advances that together make GRG a practical foundation for biobank-scale population and statistical genetics. First, we present GRG v2, a substantially improved format and construction algorithm that reduces construction time by 10-20x, halves the disk and RAM footprint of the resulting files, and improves load time by more than 20x. Applied to the recently phased UK Biobank WGS dataset (490,541 individuals, 706,556,181 variants), GRG v2 produces files 25 times smaller than .vcf.gz and more than 8 times smaller than PLINK2s PGEN format, while costing less than 90 GBP to construct. Second, we introduce grapp, a Python library and command-line tool that exploits the computational advantages of GRG for both routine analyses and new method development. grapp provides standard pipelines for variant and sample filtering, genome-wide association studies (GWAS) with covariates, principal component analysis (PCA), and data export, all implemented as graph-based operations. Moreover, it provides linear operators that integrate with the numpy and scipy sparse linear algebra ecosystem, enabling implicit matrix multiplication against the standardized genotype matrix, the linkage disequilibrium matrix, and the genetic relatedness matrix all via an underlying GRG. Using these operators, scipy-based PCA can be implemented in four lines of Python and runs 51-492x faster than existing methods while using less RAM. PCA on 89,988,512 variants in the UK Biobank runs in two to four hours. This scalability allows us to introduce a leave-one-chromosome-out (LOCO) approach to GWAS covariate construction that avoids LD artifacts without requiring LD pruning. Together, GRG v2 and grapp enable a level of scalability and methodological flexibility that is not achievable with traditional genotype formats.

genetics↗

bioRxiv2025

Inference of complex demographic history using composite likelihood based on whole-genome genealogies

Accurate parametric inference on complex demographic models is a continuing challenge in population genetics. Ancestral recombination graphs (ARGs) provide richer information than simple population genetic summary statistics and can potentially improve the power and accuracy of such inference. We present mrpast, a tool for inferring complex demographic history from ARGs. mrpast uses a composite likelihood formulation based on the pairwise sample coalescence time, observable in an ARG, and the coalescence probabilities from a continuous-time Markov process. We have evaluated mrpasts accuracy on a variety of models, including stepping-stone models with asymmetric migrations, changes in effective population sizes, out-of-Africa, and American admixture. We demonstrated mrpasts accuracy using simulated ARGs and inferred ARGs, and its high versatility in jointly inferring all parameters in complex models, including time of demographic events (e.g., population split, admixture), effective population size (e.g., constant, exponential growth), and gene flow (e.g., admixture proportion, migration rate). Extending the three-population out-of-Africa model with asymmetric migrations, we observed significantly more migrations from East Asians to Europeans than from Europeans to East Asians. Notably, mrpast can reliably recover all parameters in an American admixture model, when treating non-admixed Native Americans as an unsampled ("ghost") population. Applying this model to Mexican, Puerto Rican, and Colombian populations, we found that the reconstructed histories of Native and admixed Americans align closely with both historical records and genetic evidence. Lastly, mrpast provides a comprehensive pipeline to facilitate easier, more appropriate, and robust demographic inference, in which users can easily simulate, infer, and manipulate ARGs, and illustrate and test a demographic model.

genetics↗

bioRxiv2025

IGD: A simple, efficient genotype data format

MotivationWhile there are a variety of file formats for storing reference-sequence-aligned genotype data, many are complex or inefficient. Programming language support for such formats is often limited. A file format that is simple to understand and implement - yet fast and small - is helpful for research on highly scalable bioinformatics. ResultsWe present the Indexable Genotype Data (IGD) file format, a simple uncompressed binary format that can be more than 100 times faster and 3.5 times smaller than vcf.gz on Biobank-scale whole-genome sequence data. The implementation for reading and writing IGD in Python is under 350 lines of code, which reflects the simplicity of the format. AvailabilityA C++ library reading and writing IGD, and tooling to convert .vcf.gz files, can be found at https://github.com/aprilweilab/picovcf. A Python library is at https://github.com/aprilweilab/pyigd

bioinformatics↗

bioRxiv2024

Genotype Representation Graphs: Enabling Efficient Analysis of Biobank-Scale Data

Computational analysis of a large number of genomes requires a data structure that can represent the dataset compactly while also enabling efficient operations on variants and samples. Current practice is to store large-scale genetic polymorphism data using tabular data structures and file formats, where rows and columns represent samples and genetic variants. However, encoding genetic data in such formats has become unsustainable. For example, the UK Biobank polymorphism data of 200,000 phased whole genomes has exceeded 350 terabytes (TB) in Variant Call Format (VCF), cumbersome and inefficient to work with. To mitigate the computational burden, we introduce the Genotype Representation Graph (GRG), an extremely compact data structure to losslessly present phased whole-genome polymorphisms. A GRG is a fully connected hierarchical graph that exploits variant-sharing across samples, leveraging ideas inspired by Ancestral Recombination Graphs. Capturing variant-sharing in a multitree structure compresses biobank-scale human data to the point where it can fit in a typical servers RAM (5-26 gigabytes (GB) per chromosome), and enables graph-traversal algorithms to trivially reuse computed values, both of which can significantly reduce computation time. We have developed a command-line tool and a library usable via both C++ and Python for constructing and processing GRG files which scales to a million whole genomes. It takes 160GB disk space to encode the information in 200,000 UK Biobank phased whole genomes as a GRG, more than 13 times smaller than the size of compressed VCF. We show that summaries of genetic variants such as allele frequency and association effect can be computed on GRG via graph traversal that runs significantly faster than all tested alternatives, including vcf.gz, PLINK BED, tree sequence, XSI, and Savvy. Furthermore, GRG is particularly suitable for doing repeated calculations and interactive data analysis. We anticipate that GRG-based algorithms will improve the scalability of various types of computation and generally lower the cost of analyzing large genomic datasets.

genetics↗