nx_align_affine.nx

nx_align_affine.nx -- Smith-Waterman local alignment, AFFINE gap. license_tier: INDEPENDENT_REDERIVE genealogy_id: international-research-sources/gotoh-1982 G1.0b of NISHI_GENOMICS_SUBSTRATE_ROADMAP.md. Three-matrix DP (Gotoh 1982) layering an affine gap penalty on top of the linear- gap reference impl in nx_align.nx (G1.0). Why affine: a single 5bp deletion is biologically ONE event, not 5 independent events. Linear-gap penalises it 5*gap; affine penalises it open + 5*extend with extend << open, which matches the empirical indel-length distribution and the model that BWA-MEM / minimap2 / Bowtie2 all use by default. Penalty model: Cost of a length-L gap = gap_open_score + L * gap_extend_score Both scores are NEGATIVE (added to running scores). BWA-MEM defaults: match=+1, mis=-4, gap_open=-6, gap_extend=-1. Test convention here: match=+2, mis=-1, gap_open=-2, gap_extend=-1 so length-1 gap = -3 (= linear gap=-3), length-2 gap = -4 (vs linear -6) -- this differentiation is the whole point. Recurrence (Gotoh 1982): E[i][j] = max( H[i ][j-1] + (gap_open + gap_extend), E[i ][j-1] + gap_extend ) // gap in a F[i][j] = max( H[i-1][j ] + (gap_open + gap_extend), F[i-1][j ] + gap_extend ) // gap in b H[i][j] = max( 0, H[i-1][j-1] + s(a[i-1], b[j-1]), E[i][j], F[i][j] ) Boundary: H[0][*] = H[*][0] = 0; E[*][0] = F[0][*] = NEG_INF max_score = max over all H[i][j] Negative-infinity sentinel: NEG_INF = -1000000000 (i.e., -1e9). All real scores fit in roughly ±(n * match_score) << 1e9, so saturating-add semantics are avoided. Bounded n * m * |max_score_per_cell| << 1e9.