Cheaper by the Batch: Shared Traversal for Genotype Graph Editing
Abstract
Updating a graph by inserting or replacing nodes while preserving semantics and reusing existing structure is a recurring computational problem. In population genetics, this problem arises in the genotype representation graph (GRG), a directed acyclic graph that losslessly encodes phased genetic variation across hundreds of thousands of samples by sharing subgraph structure for individual mutations. In a GRG, each mutation's carrier set is implicitly encoded as the set of leaf nodes reachable from the node it is assigned to. Updating a mutation is therefore a structural editing problem, and current approaches remap mutations individually. This paper introduces a batched mutation-remapping algorithm that replaces independent reuse-aware traversals with a single shared reverse-topological pass, identifying reuse candidates for an entire batch at once. The pass propagates compact bit-parallel per-mutation state and uses an adaptive sparse/dense carrier set representation spanning rare-to-common variant densities. Batching is the memory-scalable complement to split-based parallelism, which instead replicates graph and traversal state per worker. Our remapping is evaluated on a controlled update workload and on end-to-end allele polarization, a bulk carrier set update that is common in population genetic analysis. Our approach is up to 10.5× faster than independent remapping while preserving exact carrier-set semantics.
Related
- Prediction of Systemic Lupus Erythematosus from Genotype and1 Gene-Expression Data: Batch Correction and Leakage Free2 Evaluation
- Batch Effect Correction to Enhance Utility of a Publicly Available ALS Proteomics Dataset
- Bioreactor cultures of brain endothelial cells produce extracellular vesicles with comparable characteristics as that of batch cultures
- A Unified Framework for Batch Correction and Imputation in Modern Mass Spectrometry Proteomics
- Slide-level batch structure limits histology-guided supervision of transcriptomic foundation models
BibTeX
@misc{li2026cheaper,
title = {{Cheaper by the Batch: Shared Traversal for Genotype Graph Editing}},
author = {Aaron Li and Yifan Li and Drew DeHaas and Giulia Guidi},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2608.26488},
eprint = {2608.26488},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.26488},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Cheaper by the Batch: Shared Traversal for Genotype Graph Editing
AU - Aaron Li
AU - Yifan Li
AU - Drew DeHaas
AU - Giulia Guidi
PY - 2026
DA - 2026/09/27
PB - arXiv
DO - 10.48550/arxiv.2608.26488
UR - https://arxiv.org/abs/2608.26488
AB - Updating a graph by inserting or replacing nodes while preserving semantics and reusing existing structure is a recurring computational problem. In population genetics, this problem arises in the genotype representation graph (GRG), a directed acyclic graph that losslessly encodes phased genetic variation across hundreds of thousands of samples by sharing subgraph structure for individual mutations. In a GRG, each mutation's carrier set is implicitly encoded as the set of leaf nodes reachable from the node it is assigned to. Updating a mutation is therefore a structural editing problem, and current approaches remap mutations individually. This paper introduces a batched mutation-remapping algorithm that replaces independent reuse-aware traversals with a single shared reverse-topological pass, identifying reuse candidates for an entire batch at once. The pass propagates compact bit-parallel per-mutation state and uses an adaptive sparse/dense carrier set representation spanning rare-to-common variant densities. Batching is the memory-scalable complement to split-based parallelism, which instead replicates graph and traversal state per worker. Our remapping is evaluated on a controlled update workload and on end-to-end allele polarization, a bulk carrier set update that is common in population genetic analysis. Our approach is up to 10.5× faster than independent remapping while preserving exact carrier-set semantics.
ER -