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

This paper introduces GRG v2, a highly optimized graph-based genotype format, and grapp, a corresponding Python library, which together enable orders-of-magnitude faster and more memory-efficient whole-genome analyses, such as PCA and GWAS, on biobank-scale datasets compared to traditional methods.

The Gist

Imagine you have a massive library containing the genetic blueprints (DNA) of half a million people. That's the UK Biobank. In the past, trying to read, compare, or analyze all these books was like trying to find a specific sentence in a library where every book was printed on a separate, heavy sheet of paper, stacked in a chaotic pile. You'd have to lift the whole pile just to check one page. This is what traditional genetic data formats are like: they are slow, take up huge amounts of computer memory, and are expensive to process.

This paper introduces two new tools that turn this chaotic library into a smart, interconnected map.

The Problem: The "Flat" Library

Traditionally, genetic data is stored in a "tabular" format (like a giant spreadsheet).

• The Analogy: Imagine a spreadsheet where every row is a person and every column is a tiny piece of DNA (a variant). For 500,000 people and 700 million DNA pieces, this spreadsheet is so huge it doesn't fit in your computer's memory.
• The Result: To do simple math (like finding patterns or ancestry), computers have to load tiny chunks of this spreadsheet over and over again. It's like trying to solve a puzzle by looking at one piece at a time, putting it down, picking up another, and repeating. It takes days or even weeks.

The Solution: The "Genotype Representation Graph" (GRG)

The authors created a new way to store this data called a Genotype Representation Graph (GRG).

• The Analogy: Instead of a flat spreadsheet, imagine a family tree or a flowchart.
  • In a family tree, you don't write down "Grandma has blue eyes" for every single grandchild. You write it once at Grandma's node, and the line connects down to all her descendants.
  • The GRG does this for DNA. Since humans share a lot of ancestry, most people have the same DNA in the same places. The GRG groups these people together. If 10,000 people share a specific DNA mutation, the graph stores that mutation once and draws a line to all 10,000 people.
  • The Benefit: Instead of a massive, flat spreadsheet, you get a compact, hierarchical map. It's like compressing a 100GB video file into a 1GB file without losing any quality.

The Two Big Upgrades

The paper presents two major improvements that make this map practical for real-world use:

1. GRG v2: The "Super-Builder"

The first version of this map was good, but building it was slow and the files were still a bit heavy.

• The Upgrade: The authors rewrote the construction algorithm.
• The Analogy: Think of the old method as building a house brick-by-brick, then painting it, then realizing you need to move a wall, and starting over. The new GRG v2 is like a 3D printer that builds the whole house structure and the paint job simultaneously, perfectly optimized.
• The Result:
  • Speed: It builds the map 10 to 20 times faster.
  • Size: The resulting files are 25 times smaller than the old standard formats.
  • Cost: It costs less than £90 (about $120) to build the map for the entire UK Biobank. That's cheaper than a single night at a hotel!

2. grapp: The "Smart Navigator"

Having a map is great, but you need a tool to drive it. Enter grapp, a software tool (a Python library).

• The Analogy: If the GRG is the map, grapp is the GPS navigation system that knows how to drive on it.
• The Magic: Most genetic tools try to flatten the map back into a spreadsheet to do math. grapp is special because it drives directly on the map. It can perform complex calculations (like finding ancestry or disease links) by just tracing the lines on the graph, without ever needing to load the whole spreadsheet into memory.

What Can We Do Now? (The "Wow" Factor)

Because of these tools, scientists can now do things that were previously impossible or took forever:

1. The "Super-Fast" Ancestry Check (PCA)

• Old Way: To find the top 10 ancestry patterns in 500,000 people, a computer might take 39 hours and crash your RAM.
• New Way: With grapp, it takes 14 minutes on a single computer core and uses a fraction of the memory.
• The Scale: They ran this on 137 million DNA variants (the whole genome) in just a few hours. Before, scientists had to throw away 99% of the data to make the math work. Now, they can use everything.

2. The "Leave-One-Out" Trick (LOCO)

• The Problem: When looking for genes linked to a disease (like BMI), scientists usually use ancestry patterns as a "control" to avoid false alarms. But sometimes, the control itself gets confused by local DNA patterns, leading to fake results.
• The Old Fix: Scientists would manually chop up the data to remove confusing parts (LD pruning), which is messy and requires guessing the right settings.
• The New Fix: Because the new tools are so fast, they can run the ancestry check 22 times (once for each chromosome), leaving out the specific chromosome they are studying each time. This is called LOCO (Leave-One-Chromosome-Out).
• The Result: It's like checking your map while ignoring the street you are currently driving on to ensure you aren't getting confused by local traffic. It's more accurate, requires no guessing, and is now affordable because the computer is fast enough to do it 22 times in a row.

The Big Picture

This paper is about removing the bottleneck.

For years, geneticists had to choose between accuracy (using all the data) and feasibility (using a tiny, filtered subset of data) because their computers were too slow.

With GRG v2 and grapp, the computer speed is no longer the limit. We can now analyze the entire genetic history of half a million people, in full detail, in a single afternoon, for the price of a cup of coffee. It opens the door to asking bigger, more complex questions about human health and evolution that we simply couldn't ask before.

Technical Summary

1. Problem Statement

The advent of biobank-scale Whole-Genome Sequencing (WGS) has created datasets of unprecedented size (e.g., the UK Biobank WGS dataset contains ~490,000 individuals and >700 million variants). Traditional tabular genotype formats (such as .vcf.gz, BED, and BGEN) and associated tools struggle with these scales due to:

• Storage Inefficiency: Tabular formats are large and do not compress well for massive cohorts.
• Computational Bottlenecks: Basic operations like filtering or calculating allele frequencies can take hours to days. Complex statistical genetics methods (e.g., Principal Component Analysis (PCA) or Genome-Wide Association Studies (GWAS)) often require loading the entire genotype matrix into RAM, which is infeasible for WGS data.
• Methodological Limitations: To fit data into memory, researchers are forced to aggressively filter variants (e.g., LD pruning, minor allele frequency thresholds), which discards valuable genetic information and introduces statistical biases.
• Lack of Integration: Existing graph-based representations (like Ancestral Recombination Graphs or ARGs) are efficient for simulation but difficult to export to standard formats or use for routine analysis without converting back to inefficient tabular forms.

2. Methodology

The authors introduce a two-pronged solution: an improved data structure (GRG v2) and a software ecosystem (grapp) that leverages this structure for computation.

A. Genotype Representation Graph (GRG) v2

GRG is a directed acyclic graph (multi-tree) that losslessly encodes genotypes by exploiting shared ancestry.

• Structure: Samples are leaves, and variants (mutations) are mapped to internal nodes. All samples reachable from a variant node carry that variant.
• Algorithmic Improvements (v2 vs. v1):
  • Lossless Construction: Unlike v1, which used a lossy intermediate step (BuildShape) followed by a slow MapMutations step, v2 maintains node-to-mutation mapping during the recursive "Build" process.
  • Optimized Haplotype Representation: Uses a more compact representation of haplotypes during the neighbor-joining process (using Hamming distance), reducing RAM footprint.
  • New "Reduce" Step: A post-construction step that identifies nodes with shared children and creates new parent nodes to reduce the total edge count, further compressing the graph.
  • Edge Encoding: Uses Compressed Sparse Row (CSR) format with integer encoding (libvbyte) on edge differences to minimize disk and RAM usage.
• Performance: Construction is 10–20× faster, and resulting files are 2–40× smaller than .vcf.gz and >8× smaller than PLINK2's PGEN format.

B. The grapp Library

grapp is a Python library and CLI tool designed to perform statistical genetics directly on the GRG without materializing the genotype matrix.

• Linear Algebra Operators: It implements scipy.sparse.linalg.LinearOperator interfaces. This allows standard numpy and scipy operations (like matrix multiplication $AX$ or $X^T X$) to be performed implicitly on the graph.
  • Matrix Multiplication: Instead of $O(KNM)$ complexity for a $K \times N$ matrix $A$ and $N \times M$ genotype matrix $X$, GRG-based multiplication is $O(K|\mathcal{G}|)$, where $|\mathcal{G}|$ is the number of edges in the graph (significantly smaller than $NM$).
  • Supports: Haploid/Diploid matrices, standardized matrices, and handling of missing data (via implicit imputation).
• Workflow Integration: Provides pipelines for filtering, PCA, and GWAS with covariates.

3. Key Contributions

1. GRG v2 Format: A highly optimized, lossless graph format that drastically reduces storage and construction costs for biobank-scale data.
2. Implicit Matrix Multiplication: The ability to perform linear algebra operations on the graph structure directly, bypassing the need to load the full genotype matrix into RAM.
3. LOCO PCA for GWAS: A novel application of fast GRG-based PCA to implement a "Leave-One-Chromosome-Out" (LOCO) approach for GWAS covariate construction. This avoids Linkage Disequilibrium (LD) artifacts without the need for parameter-heavy LD pruning.
4. Ecosystem Integration: grapp bridges the gap between graph-based data structures and the standard Python scientific computing stack (NumPy/SciPy), enabling interactive exploration and custom method development.

4. Key Results

• Construction Efficiency:
  • Constructing a GRG for the full UK Biobank WGS (490k individuals, 706M variants) costs <£90 in cloud computing.
  • The resulting file is 25× smaller than .vcf.gz and 8× smaller than PGEN.
  • Construction time is reduced by 10–20× compared to v1.
• PCA Performance:
  • On the UK Biobank (137M variants), GRG-based PCA (k=10) runs in 2.3 hours using ~122GB RAM.
  • Compared to PLINK2 (approx) and FlashPCA2, GRG is 51–492× faster and uses significantly less RAM (e.g., 3.3GB vs. 117GB for a 500k sample subset).
  • GRG PCA can utilize the full unfiltered variant set, whereas other methods require aggressive filtering.
• GWAS and Covariates:
  • LOCO Approach: Using LOCO PCA (running PCA on all chromosomes except the one being tested) effectively removes local LD signals from covariates.
  • Comparison: GWAS p-values using LOCO-GRG covariates closely match those from LD-pruned methods but differ significantly from naive "ALL" chromosome PCA, which showed biased p-values due to LD artifacts.
  • Speed: GRG-based GWAS is faster than single-threaded PLINK and scales better than multi-threaded PLINK as sample size increases.

5. Significance

• Scalability: GRG v2 and grapp make it feasible to analyze biobank-scale WGS data (hundreds of millions of variants) on standard hardware or affordable cloud instances, removing the "RAM wall" that currently limits genetic analysis.
• Methodological Flexibility: By decoupling analysis from the constraints of matrix size, researchers can now use full variant sets rather than filtered subsets. This allows for the adoption of statistically superior methods (like LOCO) that were previously computationally prohibitive.
• Future-Proofing: The framework supports the development of new iterative methods (e.g., Bayesian variable selection, polygenic scoring) that rely on repeated matrix-vector products. It also serves as a potential stepping stone toward full-scale Ancestral Recombination Graph (ARG) inference for biobanks.
• Adoption: By integrating with the standard Python scientific ecosystem, grapp lowers the barrier to entry for using advanced graph-based representations, moving beyond niche research tools to practical, routine analysis pipelines.

In summary, this work demonstrates that transitioning from tabular to graph-based genotype representations, combined with implicit linear algebra operators, can deliver orders-of-magnitude improvements in speed, memory efficiency, and cost, fundamentally changing how population and statistical genetics are performed on massive datasets.