Skip to content

Phase 1 — Port BT2's GroupWalk SA-range traversal #3

Description

@k1sauce

Part of #1. Blocked by #2 (need root cause confirmed first).

Scope

BT2 walks SA-range hits in a specific deterministic order via `GroupWalk` (`vendor/bowtie2/group_walk.h`). The order matters because BT2's `-D` budget can fire mid-traversal, leaving a specific subset of hits explored. Our current `collect_prioritized` in `crates/rusttie-align/src/align.rs:531` uses a simpler sort by SA-range size — different traversal order, different alignments discovered.

If Phase 0 confirms GroupWalk is (part of) the cause, port it.

Deliverables

  • New module `rusttie-index::groupwalk` mirroring the public API of `group_walk.h`.
  • Per-element validation: feed a known SA range, assert output sequence matches BT2's byte-for-byte. Use the instrumented BT2 binary from Phase 0 — Spike: identify exact BT2 pool divergence root cause #2.
  • Replace `collect_prioritized` to use `GroupWalk` (gated behind `RUSTTIE_USE_GROUPWALK=1` initially for A/B safety).
  • Single-end chr22 validation: position / CIGAR / AS agreement stays ≥99.6%.
  • Joint-descent uses `GroupWalk` once gated.

Exit criterion

  • Single-end metrics unchanged on chr22 (regression gate).
  • Pool-diff diagnostic shows our pool composition shifting toward BT2's for the Phase 0 sample reads.

Risks

  • BT2's `GroupWalk` uses a deterministic PRNG seeded from read+position. Reproducing the same PRNG sequence requires matching BT2's RNG implementation (`vendor/bowtie2/random_source.h`).
  • The walk can have side-effects on a shared cache structure (`AlignmentCacheIface`) that we'd need to model or stub.

Files referenced

  • `vendor/bowtie2/group_walk.h`
  • `vendor/bowtie2/random_source.h`
  • `crates/rusttie-align/src/align.rs:531` (current collect_prioritized to replace)

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions