Fast genome-analysis tools for biobanks get their speed from a shortcut. For each person, they compare that person's DNA only against the few other people whose DNA matches it over long stretches, instead of against everyone. People from well-represented ancestries have many such close matches, so the shortcut costs them little. People from under-represented ancestries have few, so the same shortcut quietly gives them a worse answer. This proposal treats the number of comparison partners each person gets as a compute budget to be allocated. The allocation rule would be tuned so that the extra error any ancestry group suffers stays below an explicit tolerance, at the lowest total compute. Because each candidate rule costs hours of CPU time to evaluate, the trade-off between compute and per-group error would be explored with a scalarization that can reach every part of the trade-off curve, not only its outer convex boundary.
The concrete setting is haplotype phasing, the task of splitting a person's genotypes into the two copies inherited from mother and father. SHAPEIT4 does this with a hidden Markov model whose candidate "conditioning states" (other haplotypes the model may copy from) are chosen with the positional Burrows–Wheeler transform (PBWT). The PBWT keeps haplotypes sorted so that long exact matches sit next to each other, which lets the conditioning set shrink as the cohort grows. The result is a switch error rate of 0.117% on about 400,000 UK Biobank samples, against 0.178% for Eagle2. That is a cohort-wide average. The research file contains no ancestry-stratified error, and the mechanism gives a clear reason to expect the average hides a gap.
Core Claim
Ancestry disparity in PBWT-based phasing is mainly a resource-allocation problem rather than a modeling problem. A per-sample, per-window rule for how many PBWT neighbours to condition on can be written as a small function of signals the PBWT already computes, such as the length profile of the longest local matches. Tuning that rule's few parameters under explicit constraints on each group's excess switch error should close most of the gap at much lower compute than raising the conditioning budget for everyone.
Ancestry labels are used only to tune and audit the rule, never at run time. This matters because admixed chromosomes do not fit discrete groups. It also means the deployed tool needs no sensitive attribute.
Relation to Prior Work
The genomics papers motivate the gap. SHAPEIT4 shows that the efficiency of PBWT conditioning depends on shared ancestry. SparsePainter restricts its ancestry-painting model to the top $Q\approx 20$ PBWT matches regardless of where those matches come from, and studies 7 continental backgrounds in UK Biobank without reporting per-ancestry accuracy. TPBWT masks error-prone sites to repair fragmented matches. All three choose neighbours by heuristics that never look at the groups. This work changes how much each sample gets, not how matches are found.
The fairness papers supply the method. Balancing Act (CEAG) bounds each group's excess accuracy drop under network pruning. It updates Lagrange multipliers on the real, non-differentiable error rates. It also reports that gaps closed on training data reopen at test time. That finding constrains this design: it forces the audit to happen on held-out individuals. The stochastic-approximation benchmark finds that augmented-Lagrangian methods give the best accuracy–fairness compromise on Folktables, while switching subgradient methods satisfy constraints but hurt the main objective. Both papers optimize neural network weights. Here the decision variables are a handful of allocation parameters inside a discrete search structure, which removes the mini-batch variance problem those papers fight.
The scalarization papers supply the exploration tool and a falsifiable worry. Optimal Scalarizations for Sublinear Hypervolume Regret proves that hypervolume scalarization with random directions reaches $O(T^{-1/k})$ hypervolume regret over $T$ evaluations and $k$ objectives, and matches a lower bound. Shu et al. explain why weighted sums cannot reach concave parts of a trade-off front. Our front is made of discrete allocation rules evaluated by expensive runs, so non-convexity is plausible, but it is an empirical question. We will measure it rather than assume it.
MIFPO computes exact fairness–performance fronts but only for a binary sensitive attribute and binary labels, and it does not apply to string-matching structures.
Research Program
For sample $i$ and genomic window $w$, let $K_{iw}=g_\theta(\ell_{iw})$ be the number of conditioning states. Here $\ell_{iw}$ is the vector of lengths of the longest PBWT matches at that window. $g_\theta$ is a monotone rule with three or four parameters $\theta$: a target total shared length to accumulate, a floor, a cap, and a growth rate. Let $C(\theta)$ be the total CPU cost, $\mathrm{SER}_g(\theta)$ the switch error rate in ancestry group $g$, and $\mathrm{SER}(\theta)$ the cohort rate. The tuning problem is
$$\min_\theta \; C(\theta) \quad \text{subject to} \quad \mathrm{SER}_g(\theta)-\mathrm{SER}(\theta)\le \epsilon \;\; \text{for every group } g,$$
with $\epsilon$ a tolerance the user sets, for example 0.02 percentage points.
Exploration. We will map the front over the objectives $(C, \mathrm{SER}_1,\dots,\mathrm{SER}_G)$, with $G$ up to 7, using hypervolume scalarization over a Gaussian-process surrogate. Each query is one phasing run on a calibration subset. We will then select the cheapest feasible point.
Refinement. Starting from that point, we will run dual ascent on per-group multipliers driven by the measured error rates, following CEAG's use of real error rates for the dual update.
Implementation. Allocation is implemented inside SHAPEIT4's state-selection step. A second instantiation varies $Q$ in SparsePainter to test whether the finding transfers to ancestry painting.
Truth data. Phasing truth comes from parent–offspring duos and trios identified with RAFFI. This is the standard source of phasing truth in large cohorts.
Held-out split. Calibration and test individuals are separated so that no pair shares more than a set amount of identity-by-descent, measured with RaPID. This directly targets the train/test fairness gap that CEAG observed, since relatedness between calibration and test samples would otherwise inflate apparent constraint satisfaction.
Baselines
The naive reference point is unmodified SHAPEIT4 with default conditioning. Its reported cohort switch error rate on UK Biobank is 0.117% (Delaneau et al.). No reported ancestry-stratified switch error rate was found on Lacuna for SHAPEIT4, Eagle2, or SparsePainter, so the first deliverable is to produce those numbers on our split. Eagle2 (reported 0.178%) is run alongside as a second unmodified tool.
The strongest competitor is SHAPEIT4 with a uniformly larger conditioning budget, scaled until total CPU equals our method's cost. This is what a practitioner would actually do, and it is the comparison that separates "allocation" from "more compute."
We also run a linear-scalarization sweep that minimizes $C+\sum_g w_g \mathrm{SER}_g$ over $\theta$. It uses the same surrogate, the same number of phasing runs, and the same parameter ranges, so the only difference from our method is the scalarization.
The key ablation is a hand-set adaptive rule: give more states wherever the top match is short, with thresholds chosen once by eye. It isolates whether constrained tuning adds anything beyond the obvious heuristic. A second ablation feeds ancestry labels into $g_\theta$, testing whether label-free allocation gives anything up.
All variants use the same calibration and test individuals, the same hardware, and the same budget of tuning runs. Beating the baselines means one of two outcomes on held-out unrelated individuals. Either the method meets the $\epsilon$ constraint for all groups at lower CPU than matched-compute uniform scaling, or it achieves a smaller worst-group excess error at equal CPU. In both cases the cohort switch error rate must stay within 0.005 percentage points of default.
Why not just…?
Why not just raise the conditioning budget for everyone? It may close the gap, but it spends most of the extra compute on majority-ancestry samples that already have long matches. The matched-compute baseline settles this directly. If uniform scaling meets the constraint at equal cost, the allocation idea is unnecessary and we will say so.
Why not just use the obvious heuristic of more states where matches are short? This is the real threat. Our rule belongs to the same family, so if the hand-set version already meets the constraint, the contribution shrinks to the stratified audit. The question is whether thresholds chosen without group-level feedback land in the right place across 7 groups with very different linkage patterns. SparsePainter's finding of population-specific linkage at immune loci suggests one threshold may not fit all groups, but only the ablation can decide.
Why not just weight each group's error in a sum? Weighted sums only reach the convex hull of the achievable trade-offs (Shu et al.). With discrete, expensive evaluations, the cheapest feasible rule may lie inside the hull. We will report the fraction of front points that no weight vector can reach. If that fraction is zero, the front is effectively convex and the weighted sum suffices; that would be a reportable finding, not a failure.
Why not just phase each ancestry against its own reference panel? Splitting the cohort removes cross-ancestry sharing and shrinks the very sample sizes that make PBWT conditioning efficient (SHAPEIT4). It also has no answer for admixed chromosomes, as in the Mexican cohort analysed with TPBWT. We include stratified phasing as a further reference to quantify this cost.
Decisive Checks
Three results decide the project.
The first is whether the gap exists at all. Before any tuning, per-group excess switch error must be clearly nonzero and must track short local match length. If it does not, the premise fails.
The second is whether the constraint transfers. Constraints met on calibration individuals must still hold on the relatedness-separated test set. Failure would repeat the CEAG generalization gap in genomics and motivate tighter calibration margins.
The third is whether label-free allocation reaches the feasible region more cheaply than both matched-compute uniform scaling and the hand-set heuristic, and whether this holds again when the same rule is applied to $Q$ in SparsePainter's painting accuracy.
References
- Accurate, scalable and integrative haplotype estimation
- Sparse haplotype-based fine-scale local ancestry inference at scale reveals recent selection on immune responses
- Fast and Robust Identity-by-Descent Inference with the Templated Positional Burrows–Wheeler Transform
- Balancing Act: Constraining Disparate Impact in Sparse Models
- Benchmarking Stochastic Approximation Algorithms for Fairness-Constrained Training of Deep Neural Networks
- Optimal Scalarizations for Sublinear Hypervolume Regret
- Learning Pareto Set for Multi-Objective Continuous Robot Control
- Efficient Fairness-Performance Pareto Front Computation
- RAFFI: Accurate and fast familial relationship inference in large scale biobank studies using RaPID
- RaPID: ultra-fast, powerful, and accurate detection of segments identical by descent (IBD) in biobank-scale cohorts