nx_sequence_edit.nx

nx_sequence_edit.nx -- Levenshtein edit distance for byte sequences. license_tier: INDEPENDENT_REDERIVE genealogy_id: international-research-sources/wagner-fischer-1974 G0.2 of NISHI_GENOMICS_SUBSTRATE_ROADMAP.md. Classic Wagner-Fischer dynamic-programming algorithm: d[i][j] = min(d[i-1][j] + 1, // delete a[i-1] d[i][j-1] + 1, // insert b[j-1] d[i-1][j-1] + (a[i-1] != b[j-1])) // substitute / match d[0][0] = 0; d[i][0] = i; d[0][j] = j Works on raw byte sequences -- equality is byte-equal. Caller may pass ASCII bases, packed 2-bit codes one per byte, amino acids, or any other byte alphabet; the algorithm is alphabet-agnostic. Why classic O(mn) DP for the reference impl: - Bit-equal reproducible across hosts (no SIMD-order nondeterminism) - Trivially auditable against the textbook recurrence - Reference behaviour to validate the Myers' bitvector fast path (nx_sequence_edit_bv.nx, G0.5) and Edlib parity bench (G14) Memory: Internal sys_mmap of (n+1) * (m+1) * 8 bytes for the DP table. For n=m=200 -> 320 KB; for n=m=1000 -> 8 MB. Long-read alignment (n,m ~ 10000) will require the rolling two-row optimisation (nx_sequence_edit_lin.nx, G0.5). API: edit_distance(a, n, b, m) -> i64 Returns the Levenshtein distance, or -1 if either length is negative. n + m == 0 returns 0. nx_safety_envelope: (schema: nishi-library/seeds/safety-critical-standards.toml) intended_use: "Edit distance for read-to-reference compare, guide-RNA off-target enumeration, primer validation, sequence-similarity scoring" sil_target: SIL2 asil_target: QM