Haplotype Phasing

You inherited your genome twice — one copy of every chromosome from your mother, one from your father. At most positions the two copies read the same letter, but at millions of spots called SNPs (single-nucleotide polymorphisms) they differ. The exact run of variants sitting together on a single chromosome copy is called a haplotype.

Here is the catch. A modern sequencer reads short fragments of DNA, and for each SNP it usually just tells you "this person is A and G here" — without saying which copy carries the A and which carries the G. The two haplotypes arrive scrambled together. Recovering them is the problem of haplotype phasing.

It sounds like bookkeeping, but it is not. The moment you have to decide, for many SNPs at once, how to split them into two consistent strands, you have walked straight into one of the hardest classes of problems in all of computer science.

Below are short reads from a sequencer. Each read covers a few SNP positions and shows the letters it saw (0 and 1 stand for the two possible variants; . means the read didn't cover that SNP). Your job: split the reads into two groups — one per chromosome copy — so that reads in the same group agree wherever they overlap.

<p class="hint">{{hint}}</p>
<div class="cols">
  <div class="col" id="colA"><div class="colhead">{{copy_a}}</div></div>
  <div class="col" id="colB"><div class="colhead">{{copy_b}}</div></div>
</div>
<div class="cons">
  <div>{{consensus_a}} <span id="consA" class="mono">–</span></div>
  <div>{{consensus_b}} <span id="consB" class="mono">–</span></div>
</div>
<div class="status" id="status">{{status_initial}}</div>
<div class="btns">
  <button id="check" type="button">{{btn_check}}</button>
  <button id="phase" type="button">{{btn_phase}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.hint code { background: #eef2f6; padding: 0 .25rem; border-radius: 4px; }
.cols { display: grid; grid-template-columns: 1fr 1fr; gap: .7rem; }
.col { background: #f1f4f8; border: 1px solid #d6dee7; border-radius: 10px; padding: .5rem; min-height: 60px; }
.colhead { font-weight: 700; color: #1d3557; font-size: .85rem; margin-bottom: .4rem; }
.read { display: flex; gap: 4px; align-items: center; background: #fff; border: 1px solid #cdd9e3;
        border-radius: 8px; padding: .3rem .45rem; margin-bottom: .35rem; cursor: pointer; transition: all .1s; }
.read:hover { border-color: #1d3557; }
.read .lab { font-size: .72rem; color: #667; width: 26px; }
.cellv { width: 22px; height: 24px; display: flex; align-items: center; justify-content: center;
         font: 700 14px ui-monospace, monospace; border-radius: 5px; }
.v0 { background: #dbeafe; color: #1e3a8a; }
.v1 { background: #fde2c8; color: #9a3412; }
.vx { background: #f3f4f6; color: #aaa; }
.cellv.err { outline: 2px solid #e63946; }
.cons { font-size: .85rem; color: #333; margin: .5rem 0; display: flex; gap: 1.4rem; flex-wrap: wrap; }
.mono { font-family: ui-monospace, monospace; font-weight: 700; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Click a read to flip it between the two copies. Checking an assignment is easy: count how many letters disagree with their group's consensus — that's the Minimum Error Correction (MEC) score, and 0 means a perfect split. Finding the best assignment is the hard part: press Phase automatically and the computer tries every way to two-color the reads. With a handful of reads that's fine; add more and the possibilities double each time.

How hard is phasing, really? Not reading the letters — sorting them onto the right copy.

• Checking a candidate phasing is trivial: build each group's consensus and count the disagreements (the MEC score).
• Brute force tries every way to assign reads to the two copies — $2^{n}$ assignments for n reads, hopeless once there are more than a few dozen.
• It's NP-hard. When the reads contain sequencing errors, finding the split with the fewest corrections — the Minimum Error Correction problem — was shown to be NP-hard (Lippert, Schwartz, Lancia and Istrail, 2002), and even APX-hard to approximate (Cilibrasi, van Iersel, Kelk and Tromp, 2007). The population version — phasing many people with the fewest distinct haplotypes (Haplotype Inference by Parsimony) — is NP-hard as well (Gusfield, 2003).
• So deciding the most parsimonious phasing is as hard as the whole NP family — the same wall behind P vs NP.

That is the punchline: with clean, perfectly overlapping reads phasing is easy, but real data has errors and gaps, and the instant those force a trade-off, you are facing genuine intractability. Practical tools fall back on heuristics and statistical models rather than guaranteed-optimal answers.

Knowing which variants travel together — not just that they exist — changes what medicine can do:

• Personalized medicine: two harmful variants on the same gene copy can leave the other copy healthy; on different copies they may knock out both. Same letters, opposite consequences — only phasing tells them apart.
• Pharmacogenomics: predicting how you metabolize a drug often depends on the exact haplotype of genes like CYP2D6, not the isolated variants.
• Transplant matching: HLA typing for organ and marrow donors is fundamentally a haplotype question.
• Disease mapping and imputation: phased reference panels let researchers fill in untyped variants and trace which haplotypes carry risk.

Underneath, phasing is a constraint-satisfaction / optimization problem, the same shape as SAT and graph partitioning — split the data into consistent groups while breaking as few rules as possible.

Haplotype phasing hides a quiet surprise: the data your sequencer hands you is two life stories printed on top of each other, and separating them cleanly — once errors and gaps enter — is NP-hard, proven by Lippert and colleagues in 2002 and APX-hard to even approximate.

So when genomics labs phase a genome, they are not running a tidy lookup; they are taming an intractable problem with heuristics, statistics and ever-longer reads. Behind a deeply human question — which half of me came from whom, and does it matter for my health? — sits P vs NP, patiently reminding us that some sorting just doesn't come cheap.