python-pairhmm-indel-realignment-band-boundary-exactness
Done. The verified solution is at ~/solution.md (also in /workspace/).
The task had no starter code or hidden tests—just /workspace/problem.json describing the required PairHMM behavior. I built and verified a complete implementation.
Root causes identified:
1. Underflow — naive probability-space products flush to 0.0 on long homopolymer reads. Fixed by running the entire recursion in log10 space with a stable log10_sum (log-sum-exp); the quality table is exactly log10(e(q)) = -q/10.
2. Band misalignment for unequal lengths — a |i-j| <= b band assumes R==H and excludes the front-loaded (left-aligned) mass that dominates when gap extension is cheap. Fixed with an endpoint-joining interpolated diagonal plus a pad margin; exactness requires band + pad >= |R-H|.
3. Silent clipping — narrow bands return finite but wrong values. Fixed with a banded Viterbi traceback that raises BandClippedError when the best path touches an interior band edge.
4. N bases treated as non-informative (log10 = 0); zero-length reads/haplotypes degenerate to the analytic deletion/insertion chains.
Verification (23/23 assertions pass, 1e-9 tolerance):
- 200 log10-vs-rescaled-linear cross-checks
- 300 wide-band == full-matrix checks (including R != H)
- clipping rejection demonstrated on R=3, H=10
- 3000 bp homopolymer: finite log10 L = -2.635, banded(50) exact
- N wildcard, empty read/hap analytic values
- posteriors satisfy P(M)+P(I)=1 per read position and P(M)+P(D)=1 per hap position (max error 7.8e-15)
- beta_M(0,0) == full likelihood (50 cases)
The markdown embeds the full pairhmm.py and verify_pairhmm.py; I extracted the code back out of the markdown and re-ran it to confirm the document is self-contained and directly usable.
# Evidence - Problem class: python-pairhmm-indel-realignment-band-boundary-exactness - Model: openrouter/deepseek/deepseek-v4.1-flash - Solved: 2026-09-29T22:21:55.829Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Implement the three-state PairHMM forward recursion used for indel realignment (match/insert/delete, read base qualities mapped through a log10 error-probability table) with exact log-space scaling so long homopolymer reads do not underflow to zero. Add the banded-with-padding optimization required when read and haplotype lengths differ (left-alignment in the extra dimension) and show the padded banded result is identical to the full unbanded matrix within a stated tolerance, while correctly rejecting band widths that clip the optimal path. Cover ambiguous bases (N), zero-length reads, reads whose best path exits the band, and report per-position posterior probabilities.", "environment": "python3", "language": "python", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "python-pairhmm-indel-realignment-band-boundary-exactness", "provider": "openrouter", "solved_at": "2026-09-29T22:21:55.829Z", "version": "3.11"}Done. The verified solution is at ~/solution.md (also in /workspace/).
The task had no starter code or hidden tests—just /workspace/problem.json describing the required PairHMM behavior. I built and verified a complete implementation.
Root causes identified:
1. Underflow — naive probability-space products flush to 0.0 on long homopolymer reads. Fixed by running the entire recursion in log10 space with a stable log10_sum (log-sum-exp); the quality table is exactly log10(e(q)) = -q/10.
2. Band misalignment for unequal lengths — a |i-j| <= b band assumes R==H and excludes the front-loaded (left-aligned) mass that dominates when gap extension is cheap. Fixed with an endpoint-joining interpolated diagonal plus a pad margin; exactness requires band + pad >= |R-H|.
3. Silent clipping — narrow bands return finite but wrong values. Fixed with a banded Viterbi traceback that raises BandClippedError when the best path touches an interior band edge.
4. N bases treated as non-informative (log10 = 0); zero-length reads/haplotypes degenerate to the analytic deletion/insertion chains.
Verification (23/23 assertions pass, 1e-9 tolerance):
- 200 log10-vs-rescaled-linear cross-checks
- 300 wide-band == full-matrix checks (including R != H)
- clipping rejection demonstrated on R=3, H=10
- 3000 bp homopolymer: finite log10 L = -2.635, banded(50) exact
- N wildcard, empty read/hap analytic values
- posteriors satisfy P(M)+P(I)=1 per read position and P(M)+P(D)=1 per hap position (max error 7.8e-15)
- beta_M(0,0) == full likelihood (50 cases)
The markdown embeds the full pairhmm.py and verify_pairhmm.py; I extracted the code back out of the markdown and re-ran it to confirm the document is self-contained and directly usable.
# Evidence - Problem class: python-pairhmm-indel-realignment-band-boundary-exactness - Model: openrouter/deepseek/deepseek-v4.1-flash - Solved: 2026-09-29T22:21:55.829Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Implement the three-state PairHMM forward recursion used for indel realignment (match/insert/delete, read base qualities mapped through a log10 error-probability table) with exact log-space scaling so long homopolymer reads do not underflow to zero. Add the banded-with-padding optimization required when read and haplotype lengths differ (left-alignment in the extra dimension) and show the padded banded result is identical to the full unbanded matrix within a stated tolerance, while correctly rejecting band widths that clip the optimal path. Cover ambiguous bases (N), zero-length reads, reads whose best path exits the band, and report per-position posterior probabilities.", "environment": "python3", "language": "python", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "python-pairhmm-indel-realignment-band-boundary-exactness", "provider": "openrouter", "solved_at": "2026-09-29T22:21:55.829Z", "version": "3.11"}