nx_align_chain.nx

nx_align_chain.nx -- co-linear seed-chain dynamic programming. license_tier: INDEPENDENT_REDERIVE genealogy_id: international-research-sources/li-2018-minimap2-section-2.2 G1.3 of NISHI_GENOMICS_SUBSTRATE_ROADMAP.md. Bridges the seed pairs from nx_align_match (G1.2) to the alignment extension input of Smith-Waterman (G1.0). A "chain" is a sequence of seeds (q_i, r_i) that are strictly co-linear under the forward-strand model: both q-positions and r-positions strictly increase along the chain. Co-linearity is what makes a chain a coherent alignment hypothesis -- it forbids the seeds from belonging to two different alignments or to different strands of an inversion. Algorithm (O(n^2) reference DP): - Precondition: caller has pre-sorted seeds by r_pos ascending (and within-tie by q_pos ascending). Ties in r_pos are rare for typical w >= 5 minimizers but possible; the strictly-less check on r still works because the inner DP scans j < i. - chain_len[i] = 1 + max(chain_len[j]) over j < i with q[j] < q[i] AND r[j] < r[i] = 1 otherwise - parent[i] = the j that achieved the max (or -1 if no extension) - The best chain ends at argmax_i chain_len[i] (leftmost-tie wins) - Backtrack from argmax through parent[] to recover the chain - Output indices are in q-increasing (== r-increasing) order Why strict-less on both axes: - Equality in q would mean the same query position contributes two seeds -- a repeated minimizer landing on the same query base, which would not extend a single alignment chain. - Equality in r similarly maps two seeds to the same reference base, which is geometrically incoherent for a single chain. What this G1.3 does NOT do (deferred): - Gap-cost-aware scoring (minimap2 alpha + beta) -- G1.3b - Striped / sparse-dp acceleration to O(n log n) -- G1.5 - Strand-aware chaining (forward vs reverse-complement) -- G1.3c - Anchor-band pruning + secondary-chain reporting -- G1.4