PaperlayerView exact revision on arXiv

Source-linked AI summary

Cheaper by the Batch: Shared Traversal for Genotype Graph Editing

Aaron Li, Yifan Li, Drew DeHaas, Giulia Guidi

arXiv:2608.26488v1cs.DSq-bio.PE

TL;DR

GRG updates are difficult because mutation carrier sets are encoded through graph reachability, making changes structural rather than local. The paper batches remapping into one shared reverse-topological traversal with compact bit-parallel state and adaptive carrier-set representations. It achieves up to 10.5× faster end-to-end polarization than independent remapping while preserving exact carrier-set semantics.

  • Problem

    GRG carrier sets are encoded by reachable leaves, so post-construction mutation updates require structural remapping rather than independent local edits.

  • Method

    The method performs one shared reverse-topological candidate-discovery traversal for a batch, using bit-parallel mutation state and adaptive sparse/dense carrier-set representations.

  • Results

    10.5× end-to-end polarization speedup was achieved on the largest dataset while preserving exact carrier-set semantics and keeping peak memory within 1.29× of batch 1.

  • Takeaways & Limitations

    Batching eliminates repeated traversal work while providing a memory-scalable complement to split-based parallelism for GRG editing.

Abstract

from arXiv · show

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.

I. INTRODUCTION

GRG carrier-set updates require structural graph editing because carriers are encoded by reachability rather than an editable genotype-matrix column. The paper introduces shared batched remapping with compact state and evaluates it on allele polarization.

  • GRGs encode carrier sets through reachable leaves, so changing mutation carriers requires restructuring the graph rather than a local column rewrite.
  • Mutation remapping attaches updated mutations to reusable graph structure while adding new structure only when necessary.
  • A shared traversal processes a batch of edits together, propagating mutation-specific state to identify reusable structures and amortize traversal work.
  • An adaptive sparse/dense carrier-set representation keeps shared-traversal state efficient across different carrier-set densities.
  • The method uses a compact bit-parallel representation to reduce per-mutation state overhead during shared traversal.
  • 10.5× speedup was achieved in end-to-end allele polarization while preserving carrier-set semantics.

II. BACKGROUND

A GRG is a shared, leaf-labeled DAG whose topology losslessly represents phased genetic variation and implicitly encodes mutation carriers. Mutation mapping searches this topology for compatible reusable subgraphs before adding structure.

  • A GRG is a leaf-labeled directed acyclic graph that losslessly represents phased genetic variation across haplotypes.
  • Internal nodes represent groups of haplotypes sharing descendant structure, and multiple parents can reuse the same subgraph.
  • A mutation’s carrier set is represented by the reachable leaves of its assigned node.
  • Multiple mutations may share a node when their carrier sets match, while partially overlapping sets can reuse portions of the descendant graph.
  • MAPMUTATIONS discovers compatible nodes and then places each mutation using existing graph structure where possible.
  • Candidate discovery traverses upward from carrier samples, retaining nodes whose descendants contain no non-carriers and pruning incompatible branches.

1) Candidate Discovery:

Mutation application prioritizes reusable compatible subgraphs while preserving exact target carrier sets. Allele polarization supplies a bulk remapping workload by complementing carriers when the alternate allele is ancestral.

  • 1) Candidate Discovery:: An exact candidate match receives the mutation directly; otherwise, disjoint compatible candidates are greedily selected by decreasing descendant-set size.
  • 1) Candidate Discovery:: A new mutation node covers selected candidates and any remaining carriers, guaranteeing that its reachable set equals the target carrier set.
  • 1) Candidate Discovery:: Post-construction updates add or replace mutations whose desired carrier sets must be represented by exact graph reachability.
  • 1) Candidate Discovery:: Allele polarization determines ancestral and derived alleles, supporting downstream analyses of population history.
  • 1) Candidate Discovery:: When the ancestral allele differs from the current reference, polarization updates the recorded mutation and its carrier set.
  • 1) Candidate Discovery:: For biallelic sites, reorientation complements the alternate-carrier set within observed haplotypes and remaps the mutation to that set.

III. METHODS

Batched remapping generalizes single-mutation editing to many updates by replacing repeated traversals with shared candidate discovery. The shared pass propagates compatibility state and prunes nodes that cannot serve any mutation.

  • The batched problem maps k updates so each mutation reaches exactly its requested carrier set while reusing existing structure.
  • Independent remapping launches separate traversals over the same graph, motivating a shared read-only discovery pass followed by serial mutation application.
  • Shared candidate discovery visits each active node once instead of once per mutation and starts from the union of carrier sets.
  • The traversal uses a shared reverse-topological pass because compatibility is inherited from a node’s children.
  • Compatibility states are propagated independently for each mutation, with child-state intersections determining candidate eligibility and pruning.

B. Bit-Parallel Mutation State

Batched discovery packs mutation-specific compatibility states into bit masks and propagates them through a shared reverse-topological traversal. This reduces redundant state processing, while deferred application can trade compactness for batching efficiency.

  • B. Bit-Parallel Mutation State: Bit-parallel masks represent which mutations remain compatible at each node, allowing one operation to evaluate many mutations simultaneously.Leaf masks encode carried mutations; internal masks are bitwise ANDs of child masks.
  • B. Bit-Parallel Mutation State: Batches larger than the machine word width remain supported, using q = ⌈k/w⌉ words and O(q) state processing per node.Each word covers a consecutive group of at most w mutations.
  • B. Bit-Parallel Mutation State: Deferred application may produce a less compact GRG than sequential mapping because mutations in one batch cannot reuse structure introduced by another.The paper quantifies this compactness trade-off separately.
  • B. Bit-Parallel Mutation State: Reverse-topological candidate discovery initializes leaf states, propagates active mutation state through nodes, and records compatible nodes before activating parents.Traversal stops above nodes where no mutation remains active.

C. Adaptive Carrier-Set Representation

The method adapts carrier-set storage to density while batching shared traversal and separating discovery from application. Sparse vectors favor rare variants, whereas dense bitsets become useful for larger shared carrier regions.

  • C. Adaptive Carrier-Set Representation: Descendant sets accumulate cheaply because distinct children have disjoint descendants, allowing sparse concatenation or dense bitwise OR without overlap resolution.This relies on the GRG multitree’s lack of diamond patterns.
  • C. Adaptive Carrier-Set Representation: Carrier sets switch from sparse sample-ID vectors to dense N-bit bitsets as density increases, covering rare-to-common variants.The representation is chosen separately for each set.
  • C. Adaptive Carrier-Set Representation: τ = 1/32 = 0.03125 is the experimental density threshold where 32-bit sparse identifiers and dense bitsets have equal storage cost.A d-sample sparse vector costs 32d bits, versus N bits for a dense bitset.
  • C. Adaptive Carrier-Set Representation: Larger batches traverse larger carrier unions and encounter dense descendant sets more often, increasing the value of dense bitsets.The sparse/dense choice is complementary to batching and parallels sparse-linear-algebra accumulator selection.
  • C. Adaptive Carrier-Set Representation: Discovery reads a fixed snapshot and precedes sequential application, so shared traversal requires no topology synchronization within a batch.Mutations do not observe structure created by other mutations during discovery.

E. Split-Based Parallelism

Splitting provides outer parallelism by processing genomic sub-GRGs independently, while batching consolidates repeated traversals within each sub-GRG. Batching improves memory scalability because it avoids replicating graph state across workers and preserves exact candidate discovery on a shared snapshot.

  • E. Split-Based Parallelism: Splitting partitions the GRG by genomic position, processes sub-GRGs independently, and merges them afterward; batching operates inside each concurrently processed partition.The two strategies form nested levels of parallelism.
  • E. Split-Based Parallelism: Adding split-based workers increases peak memory because each worker retains its own sub-GRG, local state, and modifications for later merging.This replication is the principal memory cost of adding workers.
  • E. Split-Based Parallelism: Batched discovery returns the same candidate list as independent discovery on the same snapshot, preserving the subsequent mapping semantics.The equivalence follows by induction over reverse-topological processing.
  • E. Split-Based Parallelism: Batching is advantageous when independent traversals overlap sufficiently: the overlap factor ρ(k) must exceed q = ⌈k/w⌉.Independent mapping revisits nodes per mutation, whereas batching processes each distinct node with q word operations.
  • E. Split-Based Parallelism: Temporary mutation state scales as O(qAB) words for AB active nodes, giving batching a nearly fixed per-worker footprint compared with replicated split state.Batching increases per-worker work without proportionally increasing graph-state memory.

H. Generating Polarization Updates

The evaluation generates controlled allele-polarization updates on simulated and All of Us GRGs, then measures end-to-end time, memory, and traversal behavior across batch sizes. The setup isolates remapping work while spanning increasing dataset sizes and a real chromosome-scale dataset.

  • H. Generating Polarization Updates: Simulated experiments use OutOfAfrica_2T12 GRGs with 5,000–100,000 diploid individuals, or 10k–200k phased haplotypes.Experiments run on the NCSA Delta CPU partition.
  • H. Generating Polarization Updates: A modified reference flips the ancestral allele at 10% of selected biallelic sites, creating a controlled polarization workload with known expected complements.Sites are selected from mutations in each generated GRG.
  • H. Generating Polarization Updates: The real-data experiment polarizes chromosome 21 from the All of Us cohort against the Ensembl ancestral reference genome.It uses a chromosome-specific GRG.
  • H. Generating Polarization Updates: Polarization is tested with batch sizes 1, 16, 64, 256, and 1024, spanning one-word and multi-word bit-state regimes.With 64-bit words, batch size 1024 requires q = 16 words per node.
  • H. Generating Polarization Updates: The evaluation records wall-clock time, peak memory, split and partition times, traversal components, node visits, and dense-membership threshold behavior.These measurements separate shared traversal, candidate discovery, application, polarization work, and I/O.

B. Polarization Performance

Batching substantially accelerates polarization by reducing repeated traversal, with larger datasets benefiting more, while adaptive membership further improves traversal and keeps memory near baseline. Nontraversal phases increasingly limit end-to-end gains, and the largest batches can reduce output-graph compactness.

  • Polarization runtime: 10.5× end-to-end speedup is achieved at 200k haplotypes, up from 2.5× at 10k haplotypes.At batch size 1024, traversal speedup reaches 79.5× at 200k haplotypes, but candidate discovery, application, polarization-specific work, and I/O increasingly limit end-to-end speed.
  • Polarization runtime: 9.6× end-to-end speedup is achieved on the All of Us dataset at batch size 1024.Nontraversal phases account for most of the remaining runtime, matching the limiting pattern observed on simulated data.
  • Traversal reuse: 916.8× overlap occurs at batch size 1024 on the 200k-haplotype dataset, indicating extensive repeated node processing under independent mapping.The overlap factor rises from 1.0× at batch 1 to 15.8×, 62.4×, 232.4×, and 916.8× as batch size grows.
  • Memory usage: 1.286× baseline peak memory is the maximum reported for batch size 1024, rising from 129.05 GiB to roughly 166 GiB on 200k haplotypes.This memory increase accompanies the 10.5× end-to-end speedup on the 200k dataset.
  • Adaptive carrier-set membership: 1.72×–2.44× traversal speedup is obtained from dense membership at batch size 1024 across datasets.Dense membership helps little at small batch sizes, while the runtime-optimal τ varies; fixed τ = 0.01 stays within 20% of the tuned optimum for 22 of 25 configurations and is 9.5% slower on average.
  • Output graph compactness: 78.24% edge-count and 27.15% serialized-size increases occur at batch size 1024 on the 200k dataset.The node count is effectively unchanged across batch sizes, and smaller datasets show equal or lower overhead.

V. RELATED WORK

GRGs exploit genealogical hierarchy to share subgraph structure across samples, while related multi-search and sparse-linear-algebra techniques inform batched traversal and adaptive carrier-set representation.

  • GRGs and sparse representations: GRGs share subgraph structure across samples by placing mutations on shared genealogical structure.This extends sparse storage by representing hierarchical commonality rather than treating sharing as flat.
  • Multi-search traversal: Multi-source BFS jointly executes searches by combining frontiers and attaching compact per-search state to shared vertices.These methods target concurrent searches with different levels and level-aligned frontiers.
  • Multi-search traversal: Unlike concurrent BFS, batched GRG discovery processes a compatible node once for the batch and uses a reverse topological pass without level alignment.The searches begin from carrier sets and move upward through an acyclic graph.
  • Adaptive representation: Adaptive carrier-set representation parallels sparse-versus-dense accumulator selection in Gustavson-style sparse matrix computation.Sparse storage suits low occupancy, whereas dense storage becomes preferable as occupancy rises.

VI. CONCLUSION

The paper presents batched mutation mapping for GRGs, combining shared traversal, bit-parallel state, and adaptive carrier-set membership. On allele polarization, batching substantially improves performance while keeping memory close to the batch-1 baseline, although other pipeline stages become the remaining bottleneck.

  • Conclusion: The algorithm replaces independent reverse-topological traversals with one shared traversal using compact mutation-specific state and adaptive sparse/dense memberships.It also integrates with the existing split-based parallel pipeline.
  • Conclusion: The method consolidates irregular pointer-chasing passes with data-dependent frontiers, eliminating repeated work without concurrent graph modification.This benefit depends on substantial overlap between independent traversals.
  • Conclusion: 79.5× lower shared traversal time and 10.5× lower end-to-end polarization time were achieved on 200k haplotypes and 4.7M mutations.Peak memory remained within 1.29× of the batch-1 baseline.
  • Conclusion: Candidate processing, application, polarization-specific work, and I/O dominate end-to-end performance after shared traversal is accelerated.These stages motivate future work beyond the traversal optimization.
Loading 2608.26488v1…