Introduction

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.

Separate the Two Haplotypes

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">Each row is a sequencing <b>read</b> over five SNP positions.
    <code>0</code> / <code>1</code> are the two variants; <code>.</code> means the read
    didn't cover that SNP. Click a read to flip it between <b>Copy A</b> and <b>Copy B</b>.
    A perfect split has a Minimum Error Correction (MEC) score of 0.</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">Split the reads, then check the score.</div>
<div class="btns">
  <button id="check" type="button">Check score</button>
  <button id="phase" type="button">Phase automatically</button>
  <button id="reset" type="button" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Haplotype assembly (Minimum Error Correction). Reads cover SNP positions with
// values 0/1 (-1 = not covered). We 2-color the reads into copy A / copy B; each
// copy's consensus is the per-column majority. MEC = total letters disagreeing with
// their consensus. Checking a split is a quick scan; finding the minimum-MEC split
// is NP-hard (Lippert, Schwartz, Lancia & Istrail, 2002), so brute force tries 2^reads.
const M = 5; // SNP positions
// Ground truth haplotypes: A = 0 1 0 1 0, B = 1 0 1 0 1. Reads sampled from them,
// with ONE deliberate error so the optimal MEC is small but nonzero is avoidable here.
const READS = [
  [ 0,  1, -1, -1, -1], // r0 from A
  [-1,  1,  0,  1, -1], // r1 from A
  [-1, -1,  0,  1,  0], // r2 from A
  [ 1,  0, -1, -1, -1], // r3 from B
  [-1,  0,  1,  0, -1], // r4 from B
  [-1, -1,  1,  0,  1], // r5 from B
];
// assign[i] = 0 (copy A) or 1 (copy B). Start everything in A.
let assign = READS.map(() => 0);

function consensus(group){
  const cons = [];
  for(let j=0;j<M;j++){
    let z=0,o=0;
    for(const i of group){ if(READS[i][j]===0) z++; else if(READS[i][j]===1) o++; }
    cons.push(z===0&&o===0 ? -1 : (o>z?1:0)); // majority; tie -> 0
  }
  return cons;
}
// MEC for a given assignment: sum of disagreements with each group's consensus.
function mec(asg){
  const gA=[],gB=[];
  asg.forEach((g,i)=> (g===0?gA:gB).push(i));
  const cA=consensus(gA), cB=consensus(gB);
  let cost=0;
  for(let i=0;i<READS.length;i++){
    const c = asg[i]===0?cA:cB;
    for(let j=0;j<M;j++){ if(READS[i][j]!==-1 && c[j]!==-1 && READS[i][j]!==c[j]) cost++; }
  }
  return {cost,cA,cB};
}

const sym = v => v===-1?'.':String(v);
function render(){
  const colA=document.getElementById('colA'), colB=document.getElementById('colB');
  colA.querySelectorAll('.read').forEach(e=>e.remove());
  colB.querySelectorAll('.read').forEach(e=>e.remove());
  const {cA,cB}=mec(assign);
  READS.forEach((read,i)=>{
    const row=document.createElement('div'); row.className='read';
    const lab=document.createElement('span'); lab.className='lab'; lab.textContent='r'+i; row.appendChild(lab);
    const cons = assign[i]===0?cA:cB;
    read.forEach((v,j)=>{
      const c=document.createElement('span');
      c.className='cellv '+(v===-1?'vx':(v===0?'v0':'v1'));
      if(v!==-1 && cons[j]!==-1 && v!==cons[j]) c.classList.add('err');
      c.textContent=sym(v); row.appendChild(c);
    });
    row.addEventListener('click',()=>{ assign[i]=assign[i]===0?1:0; render(); setStatus('Split the reads, then check the score.',''); });
    (assign[i]===0?colA:colB).appendChild(row);
  });
  document.getElementById('consA').textContent = cA.map(sym).join(' ');
  document.getElementById('consB').textContent = cB.map(sym).join(' ');
}
function setStatus(t,cls){ const s=document.getElementById('status'); s.textContent=t; s.className='status '+cls; }

function check(){
  const {cost}=mec(assign);
  if(cost===0) setStatus('MEC = 0 — a perfect split! Both copies are consistent.','ok');
  else setStatus(fmt('MEC = %cost% mismatch%v% (highlighted). Try moving a read.', { cost: cost, v: cost===1?'':'es' }),'bad');
}
function phase(){
  let best=null, bestCost=Infinity, steps=0;
  const n=READS.length;
  // Fix r0 in copy A to remove the trivial A/B symmetry; try 2^(n-1) splits.
  for(let mask=0; mask<(1<<(n-1)); mask++){ steps++;
    const asg=[0]; for(let i=1;i<n;i++) asg.push((mask>>(i-1))&1);
    const {cost}=mec(asg);
    if(cost<bestCost){ bestCost=cost; best=asg.slice(); }
  }
  assign=best; render();
  setStatus(fmt('Optimal split found: MEC = %bestCost%, after checking %steps% of %v% splits.', { bestCost: bestCost, steps: steps, v: 1<<(n-1) }), bestCost===0?'ok':'bad');
  console.log('Best assignment:', best.join(''), '| MEC', bestCost, '| splits checked', steps);
}
document.getElementById('check').addEventListener('click',check);
document.getElementById('phase').addEventListener('click',phase);
document.getElementById('reset').addEventListener('click',()=>{ assign=READS.map(()=>0); render(); setStatus('Split the reads, then check the score.',''); });
render();
Result
Console

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.

The Real Complexity

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 — 2n2^{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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/haplotype-phasing/Content licensed under CC BY-NC 4.0.