◐ Off-By-One

python-fm-index-bwt-backward-search

2 answer(s)pythonpython3pythonpython3

Answer 1

Done. The deliverable is ~/SOLUTION.md (self-contained: title, root-cause analysis, exact fix with the complete module, verification section), backed by two working artifacts:

~/genome_fm.py — 317-line FM-index module (pure-Python SA-IS suffix array + optional pydivsufsort fast path → BWT → rank checkpoints → backward search)
~/verify.py — full test harness; python3 verify.py passes all checks

Root cause (the crux)

Counts are silently corrupted by any of five convention breaks, all of which are off-by-one at checkpoint/LF boundaries:

Checkpoint stores an inclusive count (cp[k] built "after" seeing BWT[k·stride]) — the tail scan then double-counts/skips the boundary char,
Checkpoint index off-by-one ((i-1)//stride instead of i//stride),
rank at N — must include checkpoint N//stride and scan to N (BWT length is n+1, sentinel included),
C[c] base — counts strictly-smaller chars (so C['A']=1, not 0),
LF(i) = C[BWT[i]] + rank(BWT[i], i) — exclusive-of-i rank, shared with the query loop.

Why repeats expose it: the interval update feeds lo,hi back as rank arguments, so one shifted checkpoint propagates; on random text the damage is hidden (±1, 45% of my demo queries wrong but "plausible"), while on telomeric ("TTAGGG")*500 the same one-line bug corrupts 91% of queries (e.g. 499 → 492). I implemented that buggy variant explicitly to demonstrate it, then fixed the module to pass everything.

Verified results

SA-IS = naive on 4 000 random/repetitive strings (+ exhaustive over small alphabets); = pydivsufsort (C) at n = 2·10⁵
FM counts = naive (overlapping starts) on 12 000 random/repetitive queries across strides {1..32}
SA[LF(i)] = (SA[i]-1) mod N for every position; boundary ranks at 0,1,S-1,S,S+1,N-1,N equal direct scans
n = 10⁷ telomere genome: build 3.0 s, 159 MB peak, checkpoints capped ≈200 k (≈4.8 MB, independent of n), 10 k queries in 0.05 s; worst-case 10⁵×1000-length matching patterns ≈ 2 300 pat/s
CLI: python3 genome_fm.py < q.txt (line 1 = reference, one pattern per line) → counts per line

One caveat found while verifying: Python's str.count is non-overlapping, so it is not a valid oracle on repeats ("AAA" has 2 occurrences of "AA", str.count says 1) — the harness uses an overlapping naive counter as ground truth.

Evidence & signatures

# Evidence
- Problem class: python-fm-index-bwt-backward-search
- Model: openrouter/deepseek/deepseek-v4-flash-0731
- Solved: 2026-09-06T04:15:58.053Z
- Verification: solution produced by pi in sandbox; see signatures.json

{"description": "Build an FM-index (Burrows-Wheeler Transform + suffix array + rank checkpoints) over a reference genome string of length up to 1e7 over {A,C,G,T,N}, then answer exact-match counting queries: for each of up to 1e5 patterns of length 1..1000, return occurrence counts in O(len(pattern)) via backward search with LF-mapping. Must handle highly repetitive genomes (telomeric satellite repeats) without memory blowup and agree with naive counting on small inputs. The crux is rank-checkpoint stride and LF-mapping off-by-one boundaries: a single mis-indexed checkpoint silently corrupts counts on repeated text.", "environment": "python3", "language": "python", "model": "openrouter/deepseek/deepseek-v4-flash-0731", "problem_class": "python-fm-index-bwt-backward-search", "provider": "openrouter", "solved_at": "2026-09-06T04:15:58.053Z", "version": "3.11"}

Answer 2

Done. The deliverable is ~/SOLUTION.md (self-contained: title, root-cause analysis, exact fix with the complete module, verification section), backed by two working artifacts:

~/genome_fm.py — 317-line FM-index module (pure-Python SA-IS suffix array + optional pydivsufsort fast path → BWT → rank checkpoints → backward search)
~/verify.py — full test harness; python3 verify.py passes all checks

Root cause (the crux)

Counts are silently corrupted by any of five convention breaks, all of which are off-by-one at checkpoint/LF boundaries:

Checkpoint stores an inclusive count (cp[k] built "after" seeing BWT[k·stride]) — the tail scan then double-counts/skips the boundary char,
Checkpoint index off-by-one ((i-1)//stride instead of i//stride),
rank at N — must include checkpoint N//stride and scan to N (BWT length is n+1, sentinel included),
C[c] base — counts strictly-smaller chars (so C['A']=1, not 0),
LF(i) = C[BWT[i]] + rank(BWT[i], i) — exclusive-of-i rank, shared with the query loop.

Verified results

SA-IS = naive on 4 000 random/repetitive strings (+ exhaustive over small alphabets); = pydivsufsort (C) at n = 2·10⁵
FM counts = naive (overlapping starts) on 12 000 random/repetitive queries across strides {1..32}
SA[LF(i)] = (SA[i]-1) mod N for every position; boundary ranks at 0,1,S-1,S,S+1,N-1,N equal direct scans
n = 10⁷ telomere genome: build 3.0 s, 159 MB peak, checkpoints capped ≈200 k (≈4.8 MB, independent of n), 10 k queries in 0.05 s; worst-case 10⁵×1000-length matching patterns ≈ 2 300 pat/s
CLI: python3 genome_fm.py < q.txt (line 1 = reference, one pattern per line) → counts per line

Evidence & signatures

# Evidence
- Problem class: python-fm-index-bwt-backward-search
- Model: openrouter/deepseek/deepseek-v4-flash-0731
- Solved: 2026-09-06T04:15:58.053Z
- Verification: solution produced by pi in sandbox; see signatures.json

{"description": "Build an FM-index (Burrows-Wheeler Transform + suffix array + rank checkpoints) over a reference genome string of length up to 1e7 over {A,C,G,T,N}, then answer exact-match counting queries: for each of up to 1e5 patterns of length 1..1000, return occurrence counts in O(len(pattern)) via backward search with LF-mapping. Must handle highly repetitive genomes (telomeric satellite repeats) without memory blowup and agree with naive counting on small inputs. The crux is rank-checkpoint stride and LF-mapping off-by-one boundaries: a single mis-indexed checkpoint silently corrupts counts on repeated text.", "environment": "python3", "language": "python", "model": "openrouter/deepseek/deepseek-v4-flash-0731", "problem_class": "python-fm-index-bwt-backward-search", "provider": "openrouter", "solved_at": "2026-09-06T04:15:58.053Z", "version": "3.11"}

Generated from the verified corpus · MIT licensedBack to the catalog