Certified Optimality Gaps for Polyploid Haplotype Phasing

Polyploid genomes such as tetraploid potato and hexaploid wheat carry three or more copies of each chromosome. Haplotype phasing is the task of reconstructing each copy's sequence from short, noisy sequencing reads. The standard objective is Minimum Error Correction (MEC): split the reads into $k$ groups, one per chromosome copy, and flip as few observed letters as possible so that every group agrees on one sequence. The best current polyploid tools are neural networks and relaxation methods that optimize smooth stand-ins for this objective. On the field's main tetraploid benchmark, the reported MEC dropped from 96.2 to 29.9 when NeurHap was introduced. Nobody knows whether 29.9 is close to the true optimum or far from it. No method reports a lower bound, so the field cannot tell whether the remaining errors come from weak optimization or from noise in the data.

We propose to compute certified lower bounds on polyploid MEC for the standard benchmarks. The tool for doing this is a small, solver-independent "phasing intermediate representation": a compact description of the optimization problem, borrowed in spirit from how quantum compilers lower high-level programs. It passes through exactness-preserving compression steps before reaching exact discrete solvers. The core observation is that deep-coverage read data is massively redundant. After the reads are cut into short windows of variant sites and identical allele patterns are merged, each window's problem size depends on the number of distinct read patterns, not on coverage. That size is small enough for exact weighted MaxSAT or pseudo-Boolean solvers to finish. Because the window optima sum to a valid lower bound on the global optimum, every existing method's MEC score can then be reported with a measured gap to optimality.

Core Claim

The weighted MEC objective, for a set of reads $R$, multiplicities $w_r$, and haplotypes $h_1,\dots,h_k$ over SNP sites, is

$$\mathrm{MEC}(R) = \min_{h_1,\dots,h_k}\ \sum_{r\in R} w_r \min_{j\le k} d(r, h_j),$$

where $d$ counts mismatches between read $r$ and haplotype $h_j$ at the sites $r$ covers.

Partition the SNP sites into disjoint windows $W_1,\dots,W_m$, and let $R|_{W_i}$ be the reads restricted to window $W_i$. Take any global solution and restrict it to a window. The result is feasible for that window, and its window costs add up exactly to the global cost. Therefore

$$\sum_{i=1}^{m} \mathrm{MEC}(R|_{W_i}) \ \le\ \mathrm{MEC}(R).$$

Solving each window exactly therefore certifies a lower bound on the whole chromosome. Stitching the window solutions together yields an upper bound.

Two exact reductions make the windows solvable. First, reads with identical allele strings over the same window can always share a haplotype, because a fixed haplotype set sends each read to its nearest copy. Such reads therefore collapse into one weighted read with no loss. Second, the $k!$ ways of relabeling the chromosome copies give the same solution. These can be removed with the lexicographic ordering that made SHIPs fast, as described in Efficient Haplotype Inference with Boolean Satisfiability.

The claim has two parts. The bound will be tight enough to be informative, meaning the gap between the stitched upper bound and the lower bound is small relative to reported MEC values. The certified numbers will then show which current methods are optimization-limited and which are data-limited.

Why This Intersection, and What Each Direction Contributes

Each of the three directions plays a different role in this proposal.

The genomics-scalability line supplies the solvers. SHIPs recast parsimony haplotyping as a sequence of satisfiability problems and solved 228 of 229 benchmark instances, against 190 for the earlier exact tool. Generic ILP vs Specialized 0-1 ILP for Haplotype Inference showed that specialized pseudo-Boolean solvers beat general integer programming on such problems. These works constrain the design as well as enabling it. They target parsimony on genotype data, and exact solvers are known to break down on noisy, deep fragment matrices. That failure is why we solve only compressed windows and never the whole chromosome.

The polyploid line supplies the methods we audit. These are SDhaP's low-rank semidefinite relaxation (SDhaP), AltHap's sparse tensor decomposition (Sparse Tensor Decomposition for Haplotype Assembly of Diploids and Polyploids), and the autoencoders GAEseq (A Graph Auto-Encoder for Haplotype Assembly and Viral Quasispecies Reconstruction) and CAECseq (A Convolutional Auto-Encoder for Haplotype Assembly and Viral Quasispecies Reconstruction). They also include XHap's transformer correlation model (XHap) and NeurHap's graph-network coloring with local refinement (Graph Coloring via Neural Networks for Haplotype Assembly and Viral Quasispecies Reconstruction). All of them optimize relaxations or surrogate losses. NeurHap's own authors note that the neural part needs a combinatorial clean-up step to be competitive. That observation motivates measuring how much optimization slack remains.

The quantum-software line supplies the engineering discipline rather than a claimed speedup. Work such as Formalization of Quantum Intermediate Representations for code safety and the model-driven pipeline MDE4QAI separates a platform-independent problem description from backend-specific lowering passes, each of which can be checked. Semi-symmetry factoring (Reducing QAOA Circuit Depth by Factoring out Semi-Symmetries, Reducing QUBO Density by Factoring Out Semi-Symmetries) is one such pass. It moves interactions that several variables share onto helper variables while keeping the ground state unchanged. We adopt that structure: one weighted, windowed MEC representation, a set of passes we prove preserve the optimum, and several backends.

One of those backends is a QUBO encoding, meaning a quadratic objective over binary variables of the kind annealers and QAOA circuits accept. It exists for honest resource accounting, not as the route to the results. This is the "abstraction gap" lesson applied in reverse. The ideas behind a quantum compiler improve a classical genomics pipeline, and the same representation shows exactly what a quantum backend would cost.

Research Program

We will build the phasing representation as a weighted fragment matrix per window. Each record holds an allele pattern, a multiplicity, and optional per-base quality weights. We will then implement and prove four passes.

The first pass, pattern collapsing, is exact. The second is copy-label symmetry breaking, which is exact up to relabeling. The third is window-boundary selection: it places cuts at sites with low read spanning, which loses little in the bound. The fourth is a backend lowering to weighted MaxSAT or pseudo-Boolean form, following the SHIPs encoding style adapted from parsimony to MEC with per-read assignment variables. A second lowering produces one-hot coloring QUBOs, with optional semi-symmetry factoring.

Window size will be adaptive. We grow a window until the exact solver hits a time cap, so the lower bound tightens as compute allows. Even unfinished solver runs return valid window lower bounds, so the certificate is always sound.

Running the same pipeline over $k=1,2,\dots$ yields certified MEC-versus-ploidy curves. For viral mixtures, where the number of strains is unknown, the shape of this curve gives a principled way to choose $k$. That addresses NeurHap's stated limitation of requiring the ploidy as input.

The analysis has two parts. For every published method, we decompose its MEC into certified optimization slack (its score minus our lower bound) and irreducible error (the lower bound itself). We also study how the compressed window size scales with coverage, ploidy, and heterozygosity.

Baselines

The naive reference point is a feasible but unoptimized solution: random read-to-copy assignment followed by majority-vote haplotypes. This sets the scale of the gap. Alongside it we report the trivial lower bound of zero, so readers can see how much the certificate actually closes.

The strongest existing method is NeurHap with its refinement step. On 5x Sim-Potato it reports an MEC of 29.9, against 96.2 for the next best method, with a runtime of 258 seconds versus 341 for CAECseq and 492 for GAEseq (NeurHap). We will rerun NeurHap, CAECseq, GAEseq, AltHap, SDhaP, and XHap from released code on identical read sets with identical $k$. Each gets the same wall-clock budget as our full pipeline and the same number of random restarts. All solutions are scored with one shared MEC evaluator, so the comparison does not depend on how each paper computed its metric.

Our stitched upper bound "beats" NeurHap if it is lower at matched runtime. That would be a welcome outcome but is not the main claim. The main claim succeeds if, for most benchmark settings, the certified gap between our lower and upper bounds is under about 10% of NeurHap's reported MEC. At that point the bound is informative enough to rank methods by distance from optimality.

Three ablations isolate the key ingredients. The first removes pattern collapsing, which should make most windows unsolvable at high coverage. The second removes symmetry breaking, which should inflate solve time roughly with $k!$. The third replaces exact window solving with NeurHap-refine on the same windows, which tests whether exactness itself matters.

For the QUBO backend, the reference is the published semi-symmetry result for generic graph coloring: a 33.5% depth reduction on large instances using up to 29 helper qubits, and coupling reductions of up to 49%. We measure whether phasing graphs, after collapsing, retain that much factorable structure.

Why not just…?

Why not just run a MaxSAT or integer-programming solver on the whole chromosome? Our ablation directly tests the evidence from the SHIPs and pseudo-Boolean literature that exact solvers break down on noisy, deep matrices. Whole-chromosome runs will also be reported as incomplete-solver lower bounds. If such runs give bounds as tight as windowed ones, our windowing step is unnecessary, and we would report that.

Why not just deduplicate reads and keep using NeurHap? Deduplication is our first pass, and NeurHap can use it too. We will run NeurHap on collapsed inputs as a baseline. Deduplication alone produces no certificate, though. Faster heuristics leave open whether 29.9 is good, and that question is the one this proposal answers.

Why not just run NeurHap-refine or GenHap-style genetic search longer with more restarts? This is a real threat to any claim that our upper bound is better. It is no threat to the lower bound, which no amount of heuristic search can provide. Giving the heuristics growing budgets and tracking their convergence toward our certified bound will show whether their slack is a matter of budget or a structural trap. GenHap is limited to diploids, so this comparison uses NeurHap and AltHap.

Why not just use a fast de Bruijn graph phaser? KSNP phases a 50x human ONT dataset in about 38 minutes, but its bubble-resolution rules are diploid-specific. We include it on the diploid NA12878 data as a sanity check that our upper bounds are competitive where it applies.

Why involve quantum compilation at all? The certified-bound results do not depend on quantum hardware. The QUBO backend answers a narrower question: how many qubits and couplings a compressed phasing window actually needs, with and without semi-symmetry factoring. That gives the field an evidence-based answer instead of speculation.

Proposed Experiments

The primary benchmark is Sim-Potato (tetraploid, chromosome 5) at 5x, 15x, 25x, and 35x coverage. For each setting we report the certified lower bound, the stitched upper bound, and each baseline's rerun MEC, correct phasing rate, and runtime.

We add AltHap and SDhaP-style simulations at $k=3,4,6$ that vary heterozygosity. Low heterozygosity is where AltHap's incoherence assumption breaks and SDhaP's $K^2$ coverage rule bites. We predict the certified gap will show those methods' failures there are optimization failures, not data limits.

The HIV-1 five-strain mixture, where CAECseq reports perfect reconstruction in 9 of 13 genes and GAEseq in 8, tests MEC-versus-$k$ curves for strain counting. The HCV 10-strain and ZIKV 15-strain mixtures test the high-$k$ regime; no reported result was found on Lacuna for those datasets' numeric MEC, so we establish baselines ourselves. Real potato reads (SRR6173308) are run with lower bounds only, since there is no ground truth.

The decisive check is this. If, on Sim-Potato at 15x and above, our lower bound sits within a few percent of NeurHap's MEC, current methods are near-optimal and the field should shift effort to the error model and coverage. If a large gap remains, phasing still has substantial optimization headroom. Either result is new and useful.

The secondary check is the empirical scaling of collapsed window size with coverage. Our prediction is that it is roughly flat once coverage exceeds a few times $k$, because the number of distinct patterns is bounded by $k$ times the error-pattern diversity. The results will also report qubit and coupling counts per window for the QUBO lowering.