nx_align_backtrace_test.nx source
↩ module page · 209 lines · 8799 B
1// nx_align_backtrace_test.nx -- KAT for SW backtrace + CIGAR ops.
2//
3// All vectors hand-traced from the DP table. Tie-break: diag > up > left.
4// Local-alignment 0-floor stop.
5//
6// expect_exit: 0
7//
8// license_tier: ORIGINAL
9
10import "nx_syscalls.nx"
11import "nx_const.nx"
12import "nx_align_backtrace.nx"
13
14func main() -> i64 {
15 let a: *u8 = sys_mmap(32)
16 let b: *u8 = sys_mmap(32)
17 let ops: *u8 = sys_mmap(64)
18 let meta: *i64 = sys_mmap(64) as *i64
19
20 // ============================================================
21 // Section A -- identical "ACGT" vs "ACGT" m=+2 mis=-1 gap=-2.
22 // Expected: 4 ops all M, score 8, max (4,4), start (0,0).
23 // ============================================================
24
25 a[0]=0x41; a[1]=0x43; a[2]=0x47; a[3]=0x54
26 b[0]=0x41; b[1]=0x43; b[2]=0x47; b[3]=0x54
27 let n1: i64 = smith_waterman_linear_backtrace(a, 4, b, 4, 2, -1, -2,
28 ops, 64, meta)
29 if n1 != 4 { return 1 }
30 if meta[0] != 8 { return 2 } // score
31 if meta[1] != 4 { return 3 } // max_i
32 if meta[2] != 4 { return 4 } // max_j
33 if meta[3] != 0 { return 5 } // start_i
34 if meta[4] != 0 { return 6 } // start_j
35 var i: i64 = 0
36 while i < 4 {
37 if (ops[i] & 0xff) != NX_CIGAR_M { return 10 + i }
38 i = i + 1
39 }
40
41 // ============================================================
42 // Section B -- one substitution "ACAT" vs "ACGT".
43 // Expected: 4 ops all M (M does not distinguish match from mismatch),
44 // score 5, max (4,4), start (0,0).
45 // ============================================================
46
47 a[0]=0x41; a[1]=0x43; a[2]=0x41; a[3]=0x54
48 b[0]=0x41; b[1]=0x43; b[2]=0x47; b[3]=0x54
49 let n2: i64 = smith_waterman_linear_backtrace(a, 4, b, 4, 2, -1, -2,
50 ops, 64, meta)
51 if n2 != 4 { return 20 }
52 if meta[0] != 5 { return 21 }
53 if meta[1] != 4 { return 22 }
54 if meta[2] != 4 { return 23 }
55 if meta[3] != 0 { return 24 }
56 if meta[4] != 0 { return 25 }
57 var i2: i64 = 0
58 while i2 < 4 {
59 if (ops[i2] & 0xff) != NX_CIGAR_M { return 30 + i2 }
60 i2 = i2 + 1
61 }
62
63 // ============================================================
64 // Section C -- gap path: "AGCT" vs "ACT" m=+2 mis=-1 gap=-1.
65 // Hand-traced max=5 at (4,3); backtrace MIMM (in alignment order),
66 // start (0,0). See nx_align_backtrace.nx header for the trace.
67 // ============================================================
68
69 a[0]=0x41; a[1]=0x47; a[2]=0x43; a[3]=0x54 // AGCT
70 b[0]=0x41; b[1]=0x43; b[2]=0x54 // ACT
71 let n3: i64 = smith_waterman_linear_backtrace(a, 4, b, 3, 2, -1, -1,
72 ops, 64, meta)
73 if n3 != 4 { return 40 }
74 if meta[0] != 5 { return 41 }
75 if meta[1] != 4 { return 42 }
76 if meta[2] != 3 { return 43 }
77 if meta[3] != 0 { return 44 }
78 if meta[4] != 0 { return 45 }
79
80 // Ops in alignment order: M I M M
81 if (ops[0] & 0xff) != NX_CIGAR_M { return 50 }
82 if (ops[1] & 0xff) != NX_CIGAR_I { return 51 }
83 if (ops[2] & 0xff) != NX_CIGAR_M { return 52 }
84 if (ops[3] & 0xff) != NX_CIGAR_M { return 53 }
85
86 // ============================================================
87 // Section D -- symmetric gap-in-b: "ACT" vs "AGCT" m=+2 mis=-1 gap=-1.
88 // Same alignment mirrored: MDMM, max (3,4) score 5.
89 // ============================================================
90
91 a[0]=0x41; a[1]=0x43; a[2]=0x54 // ACT
92 b[0]=0x41; b[1]=0x47; b[2]=0x43; b[3]=0x54 // AGCT
93 let n4: i64 = smith_waterman_linear_backtrace(a, 3, b, 4, 2, -1, -1,
94 ops, 64, meta)
95 if n4 != 4 { return 60 }
96 if meta[0] != 5 { return 61 }
97 if meta[1] != 3 { return 62 }
98 if meta[2] != 4 { return 63 }
99 if meta[3] != 0 { return 64 }
100 if meta[4] != 0 { return 65 }
101 if (ops[0] & 0xff) != NX_CIGAR_M { return 70 }
102 if (ops[1] & 0xff) != NX_CIGAR_D { return 71 }
103 if (ops[2] & 0xff) != NX_CIGAR_M { return 72 }
104 if (ops[3] & 0xff) != NX_CIGAR_M { return 73 }
105
106 // ============================================================
107 // Section E -- embedded match: "ACGT" vs "TTACGTGG" m=+2 mis=-1 gap=-2.
108 // Best local: ACGT at b[2..6). Expected MMMM score 8, max (4,6),
109 // start (0,2).
110 // ============================================================
111
112 a[0]=0x41; a[1]=0x43; a[2]=0x47; a[3]=0x54
113 b[0]=0x54; b[1]=0x54; b[2]=0x41; b[3]=0x43; b[4]=0x47; b[5]=0x54; b[6]=0x47; b[7]=0x47
114 let n5: i64 = smith_waterman_linear_backtrace(a, 4, b, 8, 2, -1, -2,
115 ops, 64, meta)
116 if n5 != 4 { return 80 }
117 if meta[0] != 8 { return 81 }
118 if meta[1] != 4 { return 82 }
119 if meta[2] != 6 { return 83 }
120 if meta[3] != 0 { return 84 }
121 if meta[4] != 2 { return 85 } // alignment starts at b[2]
122 if (ops[0] & 0xff) != NX_CIGAR_M { return 86 }
123 if (ops[3] & 0xff) != NX_CIGAR_M { return 87 }
124
125 // ============================================================
126 // Section F1 -- AFFINE backtrace: identical strings.
127 // "ACGT"/"ACGT" m=+2 mis=-1 open=-2 extend=-1.
128 // Expected: 4 ops MMMM, score 8 (no gaps), end (4,4), start (0,0).
129 // ============================================================
130
131 a[0]=0x41; a[1]=0x43; a[2]=0x47; a[3]=0x54
132 b[0]=0x41; b[1]=0x43; b[2]=0x47; b[3]=0x54
133 let af_fields: *i64 = sys_mmap(64) as *i64
134 af_fields[0] = 2 // match
135 af_fields[1] = -1 // mismatch
136 af_fields[2] = -2 // gap_open
137 af_fields[3] = -1 // gap_extend
138
139 let af_ops: *u8 = sys_mmap(64)
140 let af_meta: *i64 = sys_mmap(64) as *i64
141 let an1: i64 = smith_waterman_affine_backtrace(a, 4, b, 4, af_fields,
142 af_ops, 64, af_meta)
143 if an1 != 4 { return 200 }
144 if af_meta[0] != 8 { return 201 }
145 if af_meta[1] != 4 { return 202 }
146 if af_meta[2] != 4 { return 203 }
147 if af_meta[3] != 0 { return 204 }
148 if af_meta[4] != 0 { return 205 }
149 var ai: i64 = 0
150 while ai < 4 {
151 if (af_ops[ai] & 0xff) != NX_CIGAR_M { return 210 + ai }
152 ai = ai + 1
153 }
154
155 // ============================================================
156 // Section F2 -- AFFINE 2bp gap: use the known-passing fixture
157 // from smith_waterman_affine's own KAT (Section E):
158 // "AAAAAGGGGG" (10) vs "AAAAATTGGGGG" (12).
159 // Best alignment: AAAAA--GGGGG / AAAAATTGGGGG = 10M + 2D.
160 // Score (affine open=-2 extend=-1): 10*2 - (2 + 2*1) = 16.
161 // No-gap alternative max: 5*2 = 10 (just AAAAA or GGGGG).
162 // Gap path 16 > 10 strictly -- SW must pick it.
163 //
164 // Ops: M M M M M D D M M M M M = 12; end (10,12); start (0,0).
165 // ============================================================
166
167 a[0]=0x41; a[1]=0x41; a[2]=0x41; a[3]=0x41; a[4]=0x41
168 a[5]=0x47; a[6]=0x47; a[7]=0x47; a[8]=0x47; a[9]=0x47
169 b[0]=0x41; b[1]=0x41; b[2]=0x41; b[3]=0x41; b[4]=0x41
170 b[5]=0x54; b[6]=0x54
171 b[7]=0x47; b[8]=0x47; b[9]=0x47; b[10]=0x47; b[11]=0x47
172
173 let an2: i64 = smith_waterman_affine_backtrace(a, 10, b, 12, af_fields,
174 af_ops, 64, af_meta)
175 if an2 != 12 { return an2 + 220 }
176 if af_meta[0] != 16 { return af_meta[0] + 240 }
177 if af_meta[1] != 10 { return 250 }
178 if af_meta[2] != 12 { return 251 }
179 if af_meta[3] != 0 { return 252 }
180 if af_meta[4] != 0 { return 253 }
181 // Ops: MMMMMDDMMMMM
182 if (af_ops[0] & 0xff) != NX_CIGAR_M { return 260 }
183 if (af_ops[4] & 0xff) != NX_CIGAR_M { return 261 }
184 if (af_ops[5] & 0xff) != NX_CIGAR_D { return 262 }
185 if (af_ops[6] & 0xff) != NX_CIGAR_D { return 263 }
186 if (af_ops[7] & 0xff) != NX_CIGAR_M { return 264 }
187 if (af_ops[11] & 0xff) != NX_CIGAR_M { return 265 }
188
189 // ============================================================
190 // Section F -- empty inputs return 0 ops + 0 score.
191 // ============================================================
192
193 let n6: i64 = smith_waterman_linear_backtrace(a, 0, b, 5, 2, -1, -2,
194 ops, 64, meta)
195 if n6 != 0 { return 90 }
196 if meta[0] != 0 { return 91 }
197
198 // ============================================================
199 // Section G -- capacity overflow returns -1.
200 // ============================================================
201
202 a[0]=0x41; a[1]=0x43; a[2]=0x47; a[3]=0x54
203 b[0]=0x41; b[1]=0x43; b[2]=0x47; b[3]=0x54
204 let n7: i64 = smith_waterman_linear_backtrace(a, 4, b, 4, 2, -1, -2,
205 ops, 2, meta)
206 if n7 != -1 { return 95 }
207
208 return 0
209}