Skip to content

Phase 2 — Port RedundantAlns + paired anchor iteration #4

Description

@k1sauce

Part of #1. Depends on #3 (GroupWalk ordering must be in place).

Scope

BT2's `RedundantAlns` (`vendor/bowtie2/aligner_result.cpp:980`) tracks per-cell `(refid, fw, refoff, read_row)` occupancy and rejects new alignments that overlap previously-seen ones. For ungapped same-position alignments this is equivalent to our (ref_id, ref_off, strand) dedup, but for gapped alignments it differentiates much more finely.

Additionally, BT2's `extendSeedsPaired` (`aligner_sw_driver.cpp:1582-2585`) has an outer iteration structure over anchors that interleaves with mate-find in a specific way. Our `align_pair_jointly` is a simplified approximation.

Deliverables

  • `RedundantAlns` struct in `crates/rusttie-align/src/redundant.rs` mirroring `aligner_result.h:1657`. Per-cell occupancy hashset, `overlap(&AlnRes) -> bool` + `add(&AlnRes)` methods.
  • Integrate into `paired_descent.rs`: before mate-rescue, check `overlap`; before adding to per-mate lists, check `overlap`.
  • Port BT2's exact anchor-iteration structure (mate alternation, didAnchor tracking, the do-while inner loop at `aligner_sw_driver.cpp:2326`).
  • Pool-diff diagnostic on Phase 0 sample reads: our pool now matches BT2's pool on those reads.

Exit criterion

  • chr22 MAPQ at `--joint-descent --seed-hit-cap 1000 -D 1000` jumps to 97%+.
  • If it stays at 94%, something else is structural — we re-plan before Phase 3.

Risks

  • `RedundantAlns` is per-mate, but in joint-descent we generate pairs. Need to figure out how the per-mate dedup interacts with pair-pool composition (does an excluded mate alignment mean its (mate, partner) pair is also excluded? Yes per BT2 source, but verify).
  • BT2's `extendSeedsPaired` interacts with the alignment cache (`AlignmentCacheIface`). We may or may not need to model that.

Files referenced

  • `vendor/bowtie2/aligner_result.h:1657` (RedundantAlns class)
  • `vendor/bowtie2/aligner_result.cpp:980-1032` (overlap impl)
  • `vendor/bowtie2/aligner_sw_driver.cpp:1582-2585` (extendSeedsPaired)
  • `crates/rusttie-align/src/paired_descent.rs` (our impl to refactor)

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