Certified Phase: Identifiability Certificates for Polyploid Haplotype Blocks

Every haplotype phasing tool returns an answer, but none can say which parts of that answer the sequencing data actually forces. Haplotype phasing means sorting a genome's alleles back onto the chromosome copy each came from. A diploid has two copies; a tetraploid potato has four, and those copies are often nearly identical over long stretches. Downstream users need to know which phased stretches they can trust. Today they get a heuristic phase plus, at best, a probability from a model whose assumptions may not hold.

We propose to use a geometric tool from the matrix-factorization literature, partial identifiability, to fill this gap. Partial identifiability gives conditions under which one component of a low-rank decomposition is provably the only one consistent with the data, even when the full decomposition is not unique. The plan is to write read-based phasing as a constrained factorization of the read-by-SNP matrix. We then certify, window by window and chained along the chromosome, which haplotype segments are uniquely determined. Segments that are not certified are flagged, either as unlinked or as collapsed copies that the data cannot tell apart. The proposal succeeds if errors concentrate almost entirely outside certified regions, so that certificates beat cheaper confidence signals at choosing which regions to trust.

Core Claim

Read-based phasing can be written as approximating the fragment matrix $R$ (reads × heterozygous SNPs, entries in $\{0,1\}$ or missing) by $UV$. Here $U$ is a reads × $K$ matrix whose rows lie on the probability simplex (which of the $K$ copies a read came from), and $V$ is a $K$ × SNPs matrix with entries bounded in $[0,1]$ (the haplotypes). This is exactly the bounded simplex-structured factorization of Bounded Simplex-Structured Matrix Factorization. That paper places basis entries in a box and weights on the simplex, proves identifiability under milder conditions than plain nonnegative factorization, and tests on MovieLens and MNIST. The Data-Based Uniqueness theorem of Partial Identifiability for Nonnegative Matrix Factorization states when a single factor column is unique. It requires two things:

  • a "selective window", meaning rows where only that component is active;
  • a full-rank submatrix over the other factor's zero region.

The same paper also gives a sequential identifiability argument, in which components are certified one after another in an inductive chain.

Our claim is that these conditions map naturally onto phasing:

  • Reads are selective rows by construction. In the noise-free model each read comes from exactly one copy.
  • The rank condition fails exactly when homologues coincide on a window. This is the "incoherence failure" that breaks the guarantees of Sparse Tensor Decomposition for Haplotype Assembly of Diploids and Polyploids.
  • Sequential identifiability mirrors extending phase along a chromosome. A certificate on one window plus enough shared reads propagates to the next window.

The new object is a per-segment certificate, with an explicit noise margin, that separates three kinds of region: certified-phased, unlinked, and collapsed. No current phaser produces such an object.

The closest existing work produces phases, not certificates:

All three give global, assumption-dependent guarantees about an algorithm. We give local, data-dependent guarantees about the output, and those guarantees remain informative exactly where incoherence fails.

Research Program

Phase 1: the factorization. We build a bounded simplex-structured phaser for $K \ge 2$ with missing entries. We fit only observed entries using the inertial block-coordinate method from the bounded simplex paper, initialized from SDhaP or AltHap outputs. The phaser is a means, not the contribution. We only need it to be competitive so that certificates are computed on a reasonable solution.

Phase 2: a noisy, incomplete-data certificate. This is the main technical work. Gillis and Rajkó's theorem assumes exact, complete matrices; the research file lists extending it to noisy and incomplete data as open. We handle missing data by working in windows of consecutive SNPs. In such a window, long reads (PacBio, Fosmid) yield an almost fully observed submatrix. We then restrict to reads spanning the window.

For noise, we replace "full rank" with a quantitative margin. Let $\sigma_{\min}(Z_k)$ be the smallest singular value of the zero-region submatrix $Z_k$ for copy $k$ on the window. Let $\varepsilon$ be the expected perturbation of that submatrix implied by the estimated per-base error rate and the window's coverage. Copy $k$ is certified on the window if

$$\sigma_{\min}(Z_k) > c\,\varepsilon .$$

The constant $c$ comes from a standard singular-value perturbation argument (Weyl's inequality): rank cannot drop under a perturbation smaller than the smallest singular value. The window's certificate is then chained to the next window if enough overlapping reads are selective for the same copy in both windows. This is the sequential identifiability step, and chaining stops where the condition fails.

We aim to prove the margin version for the window model. Where a proof is out of reach, we calibrate $c$ on synthetic data and state it as a calibrated rule rather than a theorem.

Phase 3: diagnostics. Rank deficiency of the joint window factor, as opposed to an individual copy's failure, signals collapsed homologues. We report these regions with an estimated multiplicity of the collapsed copies rather than an arbitrary split. This targets the autopolyploid regime highlighted in the research file's tensions section, where shared sequence makes current factorization guarantees vacuous.

Out of scope. We deliberately do not pursue the polyhedral extension-complexity question for the MEC polytope (whether its slack matrix has polynomial positive-semidefinite rank). An exponential lower bound would likely follow from known correlation-polytope results (Linear vs. Semidefinite Extended Formulations) and would not change what any practitioner does. The slack-matrix literature enters through its identifiability geometry, not its rank theory.

Baselines

Naive reference. The phaser's output is treated as fully trusted wherever reads connect SNPs, the usual connected-component block definition. This gives the "certify everything linked" operating point. Any certificate must reduce switch error within the regions it keeps, relative to this point.

Strongest existing phasers. We run the phasers below on identical inputs and use them both as phase sources and as hosts for certificates:

  • HapAltMin. It reports an MEC rate of 0.034 on NA12878 Fosmid chromosome 1, versus 0.04 for SCGD and 0.058 for ProbHap (Matrix Completion and Performance Guarantees). On its synthetic benchmark at 20% error and 8X coverage, it reports a reconstruction rate of about 0.943 versus 0.899 for SCGD.
  • SDhaP (SDhaP). For polyploid data, no reported numeric result was found on Lacuna for SDhaP or AltHap correct phasing rate on the simulated $K=3,4$ sets.
  • AltHap. As above, no numeric correct-phasing-rate result was found on Lacuna.
  • GAEseq (A Graph Auto-Encoder for Haplotype Assembly). It is the strongest reported method on potato chromosome 5 at 15X, 25X and 35X, but no numeric value was found on Lacuna.

Our bounded simplex phaser must reach MEC within a few percent of the best of these. That condition keeps the certificate comparison honest; it is not a claim to beat them.

Strongest certification competitor. The main competitor is solution-stability scoring: run SDhaP's randomized rounding and AltHap from many random restarts and bootstrap read resamples, then mark a segment trusted if at least 95% of runs agree on its phase. This uses the same total compute budget as our certificate pipeline. No reported result was found on Lacuna for calibrated phase-confidence methods on these benchmarks, so this baseline is constructed by us.

Ablations isolating the key ingredient. We compare certificates computed under several variants:

  • plain nonnegative factorization without the box and simplex constraints;
  • the exact rank test without the noise margin;
  • window certificates without sequential chaining.

What counts as beating the baselines. We report two curves: switch error inside trusted regions as a function of the fraction of heterozygous SNPs trusted, and the same for collapsed-region detection. The certificate wins if its curve dominates the stability baseline at equal coverage of trusted SNPs, or matches it at a fraction of the compute.

Why not just…?

Why not just use the phaser's own posterior or bootstrap agreement as confidence? This is the real threat. Stability across restarts measures optimizer variance, not data non-uniqueness. A region where two homologues coincide can yield the same wrong split in every run, because initialization breaks the tie consistently. A region with a genuinely unique answer can look unstable if the optimizer is poor. The certificate tests the data's geometry directly. The decisive experiment is the collapsed-homologue simulation described below. If bootstrap agreement flags collapsed regions as well as certificates do, the certificate's advantage reduces to compute cost, and we will report it that way.

Why not just threshold bridging-read depth between SNPs? Depth thresholds catch unlinked regions but are blind to collapse: forty reads spanning two identical copies give high depth and zero information about which copy is which. The ablation in which certificates use only the chaining overlap count, without the rank margin, is exactly this baseline. Its gap to the full certificate on polyploid data measures what the geometry adds.

Why not just improve the solver, for example coordinate-descent factorization in place of SDhaP's low-rank relaxation? Coordinate-descent factorization is the method of Algorithms for positive semidefinite factorization, which uses exact closed-form quartic coordinate updates. That paper evaluates only on small polygon and correlation-polytope slack matrices, and its methods are local heuristics. A faster or slightly better solver still returns one answer with no statement about which parts are forced. SDhaP already scales to $10^5$-SNP polyploid blocks in about 20 minutes, so speed is not the bottleneck that trust is.

Proposed Experiments

Synthetic controlled study. We simulate polyploid genomes at $K=2,3,4,6$ in the style of SDhaP's large-block simulations, varying error rate and coverage. We insert regions where two or more homologues are identical, which plants known non-identifiable segments. The decisive check is the recall and precision of certificates at flagging planted collapsed and unlinked segments, against bootstrap agreement and depth thresholds. If certificates do not beat bootstrap agreement here, the proposal's core claim fails.

Semi-experimental and real data. These test whether the effect survives realistic noise:

  • potato chromosome 5 at 15X, 25X and 35X, plus the real tetraploid potato reads (accession SRR6173308) used by XHap;
  • NA12878 Fosmid chromosome 1, where HapAltMin's 0.034 MEC rate anchors phaser quality;
  • GemSIM PacBio chromosome 22, where GenHap reports haplotype error under 2.5%.

On each, we plot switch error against trusted fraction. The expected pattern is that uncertified regions hold most switch errors while covering a minority of heterozygous SNPs.

Limitations. Real-data ground truth is scarce, so the human evaluation relies on Genome in a Bottle (GIAB) truth for NA12878. For potato we rely on the semi-experimental reference. We treat agreement with GAEseq and XHap there only as a sanity check, not as truth.