Certified Optimality Gaps for Polyploid Read Phasing

Organisms such as potato carry four copies of each chromosome. Reading these genomes means sorting millions of short, error-prone sequencing reads into the copy each came from. This task is called haplotype phasing, and its standard objective, Minimum Error Correction (MEC), counts how few read bases must be "corrected" so that every read agrees with one of the reconstructed copies. Exact solvers stop scaling beyond the diploid case. So polyploid phasing is done today by genetic algorithms, graph auto-encoders and transformers, and none of them can say how far its answer is from the best possible one. We propose to compute a certified lower bound on the MEC objective for polyploid instances. That bound turns every heuristic's output into a measured optimality gap, and on small enough instances it closes into a proof of optimality.

The method comes from scheduling. In identical parallel machine scheduling with sequence-dependent state (the cost of the next job depends on the state the previous ones left the machine in), compact integer programs have weak continuous relaxations and suffer from machine-swapping symmetry. Kowalczyk et al. fixed both problems with column generation, in which each candidate column is one whole machine's schedule and the subproblem is solved over a decision diagram, a layered graph that compactly encodes all feasible sequences. Read phasing has the same structure. The $k$ chromosome copies are identical, interchangeable "machines". Reads are "jobs" processed in genomic order, and the cost of placing a read on a copy depends on the allele state that copy has accumulated so far. We carry the reformulation over, and we add a relaxed decision diagram so that the bound stays valid even when the subproblem cannot be solved exactly.

Core Claim

A set-partitioning reformulation of polyploid weighted MEC has these properties. Each column is one haplotype together with the reads it explains. Genotype dosage, meaning how many of the $k$ copies carry the alternative allele at each site, enters as linear side constraints. Candidate haplotypes are scored by a width-limited relaxed decision diagram built over variant sites. We claim this formulation yields lower bounds tight enough to certify heuristic phasings of tetraploid potato data to within a few percent of optimal at realistic coverage. A compact integer program with symmetry breaking cannot do this. A secondary, empirical claim follows from the first: once gaps are measurable, we can test whether lower MEC actually tracks correct phasing in polyploids, or whether current tools are already near-optimal on an objective that has stopped being informative.

Formulation

Let $R$ be the reads and $J$ the heterozygous sites. A column $c$ is a haplotype string $h_c \in \{0,1\}^J$ plus a read set $S_c$. Its cost $w_c = \sum_{r \in S_c} d(r, h_c)$ is the quality-weighted mismatch between those reads and the haplotype. With $g_j$ the dosage reported by the genotype caller at site $j$, the master problem is

$$\min \sum_c w_c \lambda_c \;\text{ s.t. }\; \sum_{c \ni r} \lambda_c = 1 \;\forall r,\quad \sum_c \lambda_c = k,\quad \sum_c h_c[j]\,\lambda_c = g_j \;\forall j,\quad \lambda \ge 0 .$$

Here $\lambda_c$ is the (relaxed) weight on column $c$. Columns carry no machine labels, so the $k!$ copy-permutation symmetry disappears, as it does for identical machines in Kowalczyk et al. Let $\pi_r$, $\sigma$ and $\mu_j$ be the dual prices of the three constraint families. For a fixed haplotype $h$, a read should enter the column exactly when $d(r,h) < \pi_r$. The pricing problem therefore reduces to choosing $h$ to minimize $\sum_r \min(0, d(r,h) - \pi_r) - \sum_j \mu_j h[j] - \sigma$.

We solve pricing over a decision diagram whose layers are the variant sites. A node records the partial mismatch count of each read still being scanned, capped at $\pi_r$. Merging nodes by taking the component-wise minimum of these counts gives a relaxed diagram whose optimum underestimates the true minimum reduced cost $\bar{c}_{\min}$. Because the column weights sum to $k$, the standard Lagrangian argument gives

$$z^\star \;\ge\; z_{\text{RMP}} + k\,\bar{c}_{\min},$$

where $z^\star$ is the optimal weighted MEC and $z_{\text{RMP}}$ is the value of the current restricted master problem. The bound stays valid at any diagram width. Width only controls how tight it is. This is the scalability lever: we never need exact pricing to produce a certificate.

Research Program

The work proceeds in three parts. First, we build the branch-and-price solver. Columns are seeded from heuristic outputs (GenHap, H-PoP, GAEseq, XHap). A fast restricted diagram finds negative-reduced-cost columns, a relaxed diagram supplies certified bounds, and branching is on read pairs (same copy versus different copy), which preserves the pricing structure.

Second, we add an exact fallback for genomic windows where the relaxed diagram leaves a large gap. That fallback is pricing done by a unified logic-and-arithmetic solver. Following the lazy-nogood design of Drescher and Walsh, the solver generates read-consistency conflicts only when partial assignments violate them, instead of grounding every read-site combination. This is where hard biological side information enters. Mendelian trio constraints, which Chen et al. show remove most phase ambiguity, and known anchor sites are hard to express in neural phasers but are natural declarative rules.

Third, we run a measurement study. For every heuristic on every benchmark we report the certified gap and relate it to correct phasing rate against ground truth.

Each prior line plays a distinct role. Kowalczyk et al. supply the method. Two papers motivate the gap. Graça et al. found that LP-based branch-and-bound fails on haplotype inference because the relaxation smears across 0-1 choices. Rosa et al. showed in scheduling that strengthening the formulation shrinks the relaxation gap from over 37% to under 6%. Graça et al.'s result could be read as ruling out LP-based exact methods for genomics altogether. We read it more narrowly, as a verdict on compact formulations, and our first decisive experiment tests exactly that. The declarative haplotyping systems, SHIPs and Haplo-ASP, address only population parsimony on clean genotype matrices. Neither handles reads, quality weights or polyploidy. They constrain our design by showing that full Boolean grounding caps instance size, which is why grounding is confined to the fallback windows. The neural phasers, GAEseq, its convolutional variant and XHap, optimize surrogate losses and give no guarantee. We do not compete with them on speed. We measure them.

Baselines

The naive reference point is the MEC value of a simple position-ordered greedy phasing, together with the trivial lower bound of zero. Any certified bound must beat zero by a margin that matters, and any heuristic should beat greedy.

The strongest existing heuristic competitors on polyploid data are GAEseq and XHap. GAEseq is reported to achieve lower MEC and higher correct phasing rate than HapCompass and H-PoP on potato chromosome 5 at 15x, 25x and 35x coverage. However, no reported numeric MEC or correct-phasing value was found on Lacuna for either GAEseq or XHap on potato. We will therefore rerun both from their released code, including XHap's repository, on identical read sets with authors' default settings and a tuning budget matched across methods. For viral quasispecies the strongest reported number is from GAEseq on the HIV-1 5-virus-mix: it perfectly reconstructed all five strains in 8 of 13 genes, against 5 or 6 for PredictHaplo and TenSQR. On the diploid side, GenHap reports a haplotype error rate below 2.5% on simulated GemSIM reads, and about ten minutes on NA12878 PacBio data at coverage up to 565x.

Our method does not aim to "beat" these on accuracy. Success means two things. The certified gap for the best heuristic should fall below 5% on at least the 15x and 25x tetraploid potato instances. When our solver is allowed to improve the heuristic's solution, any MEC reduction should be accompanied by an honestly reported change in correct phasing rate, whether up or down.

The strongest exact competitor is a compact integer program for polyploid weighted MEC, with lexicographic symmetry breaking across copies in the style of SHIPs. It runs in a commercial MILP solver under the same wall-clock and memory limits, and we compare root bounds and final gaps. A second exact competitor is a direct MaxSAT/ASP encoding of weighted MEC with dosage cardinality constraints, extending the Haplo-ASP encoding.

Three ablations isolate the key ingredients. Removing the dosage constraints measures how much of the bound comes from caller information rather than the reformulation. Sweeping diagram width traces the bound-versus-time curve. Disabling the relaxed diagram and relying only on heuristic pricing shows that certification depends on the relaxation and not merely on column generation.

Why not just…?

Why not just give a compact integer program with symmetry breaking to a commercial solver? This is the obvious first move, and the evidence against it is indirect but consistent. On 1,183 haplotype-inference instances, Graça et al. report that CPLEX aborted on 249 while MiniSat+ aborted on 18, and they attribute the failures to relaxation smearing. In scheduling, Kowalczyk et al. report that their decision-diagram formulation has a strictly stronger relaxation than the time-indexed one and was fastest on about 65% of the 4-machine instances. Our root-bound comparison on identical potato windows settles the question directly. If the symmetry-broken compact formulation reaches gaps within a factor of two of ours, the reformulation is not worth its complexity, and we will say so.

Why not just extend Haplo-ASP or a MaxSAT encoding to reads? For diploid, low-coverage windows this may genuinely be competitive. Haplo-ASP solved 332 of 334 parsimony instances, and Eiter et al. showed in makespan scheduling that ASP with difference logic beats commercial solvers within industrial timeouts. The weakness is that a pure logic solver proves bounds through search, not through a relaxation. A timeout therefore usually leaves no useful bound, and full grounding is the known ceiling. We treat this encoding as a real threat. We run it as a baseline on every window, and we keep it as the exact pricing fallback rather than discarding it.

Why not just trust the heuristics, since they already reach low error? GenHap's sub-2.5% haplotype error is measured against simulated truth, which real polyploid samples lack. The potato comparisons are relative between tools, with no way of knowing whether all of them sit far from optimal. A certificate is the only way to find out. If our gaps show the heuristics are already near-optimal, that is itself a useful negative result: it would mean progress in polyploid phasing must come from better objectives and more data, not better search. The information-theoretic analysis of coverage requirements points in that direction.

Why not just use an exact column-wise dynamic program, as in HapCol, or Viterbi decoding as in the mate-pair coding view? For diploids these approaches are strong, and we do not claim to beat them there. Their state space grows exponentially with coverage, and with ploidy, and that is the regime we target. NA12878 chromosome 22 serves only as a sanity check that our bound matches known diploid optima.

Proposed Experiments

The primary benchmark is potato chromosome 5. We use the semi-experimental simulated sets at 15x, 25x and 35x, where ground truth allows correct phasing rate to be computed, and the real reads at NCBI accession SRR6173308, used by GAEseq and XHap, where only MEC and certified gaps can be reported. We split chromosomes into windows of increasing length to trace where certification breaks down.

The HIV-1 5-virus-mix tests a variable number of copies. There the constraint that the column weights sum to $k$ is replaced by a per-column penalty, and we report strain-reconstruction counts against GAEseq's 8 of 13. GIAB NA12878 chromosome 22 and GemSIM simulations provide the diploid check.

Four checks decide the outcome. First, root-bound gap of our formulation versus the symmetry-broken compact program on matched windows. Second, the fraction of windows certified within 1% and 5% for the best heuristic. Third, the correlation between certified MEC improvement and correct phasing rate on simulated potato, which tests whether exact MEC is worth pursuing at all. Fourth, the width ablation, showing that the bound degrades gracefully rather than collapsing as coverage rises.