nx_align_backtrace.nx

nx_align_backtrace.nx -- Smith-Waterman backtrace with CIGAR output. license_tier: INDEPENDENT_REDERIVE genealogy_id: international-research-sources/smith-waterman-1981 + sam-spec-v1.4.6 G1.0c of NISHI_GENOMICS_SUBSTRATE_ROADMAP.md. Walks the SW DP table backward from the max-score cell to recover the operation string of the optimal local alignment. Output uses SAM/BAM CIGAR codes (NX_CIGAR_M / _I / _D from nx_const). Why a separate primitive rather than extending smith_waterman_linear: The existing G1.0 SW returns score + end-coordinates and discards the DP table internally. Backtrace needs the full table. Rather than complicate the G1.0 API with optional-output flags, this primitive owns its own table allocation + DP fill + backtrace. Some DP-code duplication is the price for clean API separation. (G1.5 perf path will share a sw_dp helper used by both.) Tie-break for predecessor selection: When multiple predecessors produce the current cell's value (rare but possible), the order checked is: diagonal -> up -> left. This favours matches/mismatches over gaps, matching the minimap2 + BWA-MEM convention. Deterministic across hosts. Stop condition: Backtrace stops when H[i][j] == 0 -- the local-alignment 0-floor marks the start of the optimal region. Out-coordinates record where the alignment STARTED (i_start, j_start), so the alignment spans a[i_start .. i_max) vs b[j_start .. j_max) using ops as the operation stream from left to right. What G1.0c does NOT do (deferred): - Affine-gap backtrace (needs separate E/F predecessor matrices) -- G1.0d - Run-length compression of ops (e.g., "MMMM" -> "4M") -- G1.4c - CIGAR string serialisation as ASCII -- nx_sam_writer (G6) - Soft-clipping of unaligned query ends -- G1.4c - Explicit = / X distinction (we use M for both) -- G1.4c API: smith_waterman_linear_backtrace(