AI Insight
This paper presents a new algorithm for efficiently updating genotype representation graphs (GRGs), which are data structures used to encode genetic variation across large populations. The researchers developed a batched approach that processes multiple mutations simultaneously in a single graph traversal, rather than handling each mutation independently. Testing on real genetic data shows the method is up to 10.5 times faster than existing approaches while maintaining complete accuracy in tracking which individuals carry each genetic variant.
Why it matters
This computational improvement could significantly accelerate population genetics research by making it faster to analyze and update large-scale genetic datasets containing hundreds of thousands of samples. The efficiency gains are particularly relevant for common operations like allele polarization, enabling researchers to work with increasingly large genomic databases more practically.
Understand the Science
⚠️ Preprint – Noch nicht peer-reviewed
Dieser Artikel wurde noch nicht von unabhängigen Experten begutachtet. Die Ergebnisse sind vorläufig und sollten mit Vorsicht interpretiert werden.
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$times$ faster than independent remapping while preserving exact carrier-set semantics.
Source: Cheaper by the Batch: Shared Traversal for Genotype Graph Editing