nx_align.nx

nx_align.nx -- Smith-Waterman local alignment, linear-gap. license_tier: INDEPENDENT_REDERIVE genealogy_id: international-research-sources/smith-waterman-1981 G1.0 of NISHI_GENOMICS_SUBSTRATE_ROADMAP.md. Reference-impl Smith-Waterman with linear gap penalty. This is the EXTENSION half of BWA-MEM-class seed-and-extend; future modules: nx_align_minimizer.nx (G1.1) -- minimizer-based seeding nx_align_chain.nx (G1.2) -- compatible-seed chaining nx_align_affine.nx (G1.0b) -- affine gap (Gotoh 1982) nx_align_bwa_mem.nx (G1.3) -- full BWA-MEM-class pipeline Recurrence (Smith & Waterman 1981): H[0][j] = H[i][0] = 0 H[i][j] = max( 0, H[i-1][j-1] + s(a[i-1], b[j-1]), // diagonal H[i-1][j] + gap, // up (gap in b) H[i][j-1] + gap ) // left (gap in a) max_score = max over all H[i][j] Why local + linear-gap for G1.0: - Local (the 0-floor) is what read aligners need: a read may match only part of the reference, with mismatch / clipping at the ends. Global alignment (Needleman-Wunsch) forces end-to-end match which is wrong for read alignment. - Linear gap is one parameter; affine gap (Gotoh 1982) is three parameters and three DP matrices. Affine is more realistic (a single 5bp indel is usually one event, not 5 events) but adds complexity. G1.0b layers affine on top of this. Tie-breaking: On equal scores, the FIRST max found wins (strict > update). Means: when multiple equally-good local alignments exist, the one closest to the top-left of the DP table is reported. Deterministic across hosts; matches the audit discipline. API: nx_max3(a, b, c) -> i64