hspZ: GPU-accelerated HSPs backend
hspZ v0.0.4

B. Spaced-seed index

Map full valid windows into stable 12-of-19 reference buckets and an oracle-ordered query seed stream.

A spaced shape validates its full width, then packs only the care positions. `T` marks a care position that also permits a transition variant.

base       0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
12of19    T T T 0 T 0 0 T T 0  0  T  0  T  0  T  T  T  T
packed     [ twelve ordered 2-bit bases = one k-mer index ]

bucket k   pos_table[index[k-1] .. index[k]]
            low reference positions  →  high reference positions
B.1 — Resolve the seed shapeStep 1 of 5
React Flow

WHAT GOES IN: `12of19`, `14of22`, or a custom 1/0/T pattern. WHAT HAPPENS: The parser records the pattern width, care positions, and positions that allow transitions. WHAT COMES OUT: One validated Shape with 4–15 packed care bases. INVARIANT: Custom care positions follow KegAlign semantics and therefore admit transitions.

Readable journey

Step 1

B.1 — Resolve the seed shape

what goes in
`12of19`, `14of22`, or a custom 1/0/T pattern.
what happens
The parser records the pattern width, care positions, and positions that allow transitions.
what comes out
One validated Shape with 4–15 packed care bases.
invariant
Custom care positions follow KegAlign semantics and therefore admit transitions.
  1. CLI seed spec → Shape parser: name or 1/0/T pattern
  2. Shape parser → Shape parser: resolve care positions
  3. Shape parser → Shape: width + care bits + transitions
Step 2

B.2 — Validate complete seed windows

what goes in
One Shape and a candidate reference or query start.
what happens
Every base across the full pattern width is checked before care positions are packed two bits at a time.
what comes out
A packed k-mer index or the invalid-k-mer sentinel.
invariant
An invalid or lowercase base anywhere in the window rejects it, even at a don't-care position.
  1. Full seed window → Validator: all width bases
  2. Validator → Care-bit packer: valid uppercase ACGT window
  3. Care-bit packer → K-mer index: ordered 2-bit care bases
Step 3

B.3 — Count reference k-mers

what goes in
A packed reference bin, Shape, step, and CPU worker count.
what happens
Workers rescan disjoint position ranges and count each valid k-mer into private tables.
what comes out
Per-worker counts for every possible packed k-mer.
invariant
Reference position zero and the strided starts match KegAlign's offset rule exactly.
  1. Reference bin → CPU workers: contiguous step-index ranges
  2. CPU workers → CPU workers: validate + pack each window
  3. CPU workers → Private counts: counts without atomics
Step 4

B.4 — Scan and scatter a stable index

what goes in
Per-worker k-mer counts and the same reference ranges.
what happens
Two-level prefixes assign disjoint bucket cursors; workers rescan and scatter genomic positions.
what comes out
Cumulative `index_table` boundaries and bucketed `pos_table` positions.
invariant
Positions remain ascending inside every bucket, byte-identical to the serial builder and to the arrays `hspZ index` stores for `run --index`.
  1. Private counts → Two-level scan: counts by worker and k-mer
  2. Two-level scan → CPU workers: disjoint bucket cursors
  3. CPU workers → SeedTable: rescan + stable scatter
  4. SeedTable → SeedTable: cumulative index + positions
Step 5

B.5 — Emit query seeds in oracle order

what goes in
One query interval, Shape, and transition setting.
what happens
Each valid position emits its exact k-mer first, then one permitted transition variant per care position.
what comes out
A stable stream of packed `(k-mer, query-position)` seed offsets.
invariant
CPU and device seeders preserve query-position order and variant order exactly.
  1. Query interval → seed_kmers: encoded windows
  2. seed_kmers → Prefix scan: slots per query position
  3. Prefix scan → scatter_seeds: stable output ranges
  4. scatter_seeds → Seed offsets: exact then transitions