Debian Codegraph @

bwa-apache2/ksw.c

raw ◀ ▶
2 Debian patches touch this file
1 /* The MIT License
2
3 Copyright (c) 2011 by Attractive Chaos <[email protected]>
4
5 Permission is hereby granted, free of charge, to any person obtaining
6 a copy of this software and associated documentation files (the
7 "Software"), to deal in the Software without restriction, including
8 without limitation the rights to use, copy, modify, merge, publish,
9 distribute, sublicense, and/or sell copies of the Software, and to
10 permit persons to whom the Software is furnished to do so, subject to
11 the following conditions:
12
13 The above copyright notice and this permission notice shall be
14 included in all copies or substantial portions of the Software.
15
16 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
17 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
18 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
19 NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
20 BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
21 ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
22 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
23 SOFTWARE.
24 */
25
26 #include <stdlib.h>
27 #include <stdint.h>
28 #include <assert.h>
29 #if defined __SSE2__
•30 #define SIMDE_ENABLE_NATIVE_ALIASES
31 #include <simde/x86/sse2.h>
32 #elif defined __ARM_NEON
33 #include "neon_sse.h"
34 #else
35 #include "scalar_sse.h"
36 #endif
37 #include "ksw.h"
38
39 #ifdef USE_MALLOC_WRAPPERS
40 # include "malloc_wrap.h"
41 #endif
42
43 #ifdef __GNUC__
44 #define LIKELY(x) __builtin_expect((x),1)
45 #define UNLIKELY(x) __builtin_expect((x),0)
46 #else
47 #define LIKELY(x) (x)
48 #define UNLIKELY(x) (x)
49 #endif
50
51 const kswr_t g_defr = { 0, -1, -1, -1, -1, -1, -1 };
52
53 struct _kswq_t {
54 int qlen, slen;
55 uint8_t shift, mdiff, max, size;
56 __m128i *qp, *H0, *H1, *E, *Hmax;
57 };
58
59 /**
60 * Initialize the query data structure
61 *
62 * @param size Number of bytes used to store a score; valid valures are 1 or 2
63 * @param qlen Length of the query sequence
64 * @param query Query sequence
65 * @param m Size of the alphabet
66 * @param mat Scoring matrix in a one-dimension array
67 *
68 * @return Query data structure
69 */
70 kswq_t *ksw_qinit(int size, int qlen, const uint8_t *query, int m, const int8_t *mat)
71 {
72 kswq_t *q;
73 int slen, a, tmp, p;
74
75 size = size > 1? 2 : 1;
76 p = 8 * (3 - size); // # values per __m128i
77 slen = (qlen + p - 1) / p; // segmented length
78 q = (kswq_t*)malloc(sizeof(kswq_t) + 256 + 16 * slen * (m + 4)); // a single block of memory
79 q->qp = (__m128i*)(((size_t)q + sizeof(kswq_t) + 15) >> 4 << 4); // align memory
80 q->H0 = q->qp + slen * m;
81 q->H1 = q->H0 + slen;
82 q->E = q->H1 + slen;
83 q->Hmax = q->E + slen;
84 q->slen = slen; q->qlen = qlen; q->size = size;
85 // compute shift
86 tmp = m * m;
87 for (a = 0, q->shift = 127, q->mdiff = 0; a < tmp; ++a) { // find the minimum and maximum score
88 if (mat[a] < (int8_t)q->shift) q->shift = mat[a];
89 if (mat[a] > (int8_t)q->mdiff) q->mdiff = mat[a];
90 }
91 q->max = q->mdiff;
92 q->shift = 256 - q->shift; // NB: q->shift is uint8_t
93 q->mdiff += q->shift; // this is the difference between the min and max scores
94 // An example: p=8, qlen=19, slen=3 and segmentation:
95 // {{0,3,6,9,12,15,18,-1},{1,4,7,10,13,16,-1,-1},{2,5,8,11,14,17,-1,-1}}
96 if (size == 1) {
97 int8_t *t = (int8_t*)q->qp;
98 for (a = 0; a < m; ++a) {
99 int i, k, nlen = slen * p;
100 const int8_t *ma = mat + a * m;
101 for (i = 0; i < slen; ++i)
102 for (k = i; k < nlen; k += slen) // p iterations
103 *t++ = (k >= qlen? 0 : ma[query[k]]) + q->shift;
104 }
105 } else {
106 int16_t *t = (int16_t*)q->qp;
107 for (a = 0; a < m; ++a) {
108 int i, k, nlen = slen * p;
109 const int8_t *ma = mat + a * m;
110 for (i = 0; i < slen; ++i)
111 for (k = i; k < nlen; k += slen) // p iterations
112 *t++ = (k >= qlen? 0 : ma[query[k]]);
113 }
114 }
115 return q;
116 }
117
118 #if defined __ARM_NEON
119 // This macro implicitly uses each function's `zero` local variable
120 #define _mm_slli_si128(a, n) (vextq_u8(zero, (a), 16 - (n)))
121 #endif
122
123 kswr_t ksw_u8(kswq_t *q, int tlen, const uint8_t *target, int _o_del, int _e_del, int _o_ins, int _e_ins, int xtra) // the first gap costs -(_o+_e)
124 {
125 int slen, i, m_b, n_b, te = -1, gmax = 0, minsc, endsc;
126 uint64_t *b;
127 __m128i zero, oe_del, e_del, oe_ins, e_ins, shift, *H0, *H1, *E, *Hmax;
128 kswr_t r;
129
130 #if defined __SSE2__
131 #define __max_16(ret, xx) do { \
132 (xx) = _mm_max_epu8((xx), _mm_srli_si128((xx), 8)); \
133 (xx) = _mm_max_epu8((xx), _mm_srli_si128((xx), 4)); \
134 (xx) = _mm_max_epu8((xx), _mm_srli_si128((xx), 2)); \
135 (xx) = _mm_max_epu8((xx), _mm_srli_si128((xx), 1)); \
136 (ret) = _mm_extract_epi16((xx), 0) & 0x00ff; \
137 } while (0)
138
139 // Given entries with arbitrary values, return whether they are all 0x00
140 #define allzero_16(xx) (_mm_movemask_epi8(_mm_cmpeq_epi8((xx), zero)) == 0xffff)
141
142 #elif defined __ARM_NEON
143 #define __max_16(ret, xx) (ret) = vmaxvq_u8((xx))
144 #define allzero_16(xx) (vmaxvq_u8((xx)) == 0)
145
146 #else
147 #define __max_16(ret, xx) (ret) = m128i_max_u8((xx))
148 #define allzero_16(xx) (m128i_allzero((xx)))
149 #endif
150
151 // initialization
152 r = g_defr;
153 minsc = (xtra&KSW_XSUBO)? xtra&0xffff : 0x10000;
154 endsc = (xtra&KSW_XSTOP)? xtra&0xffff : 0x10000;
155 m_b = n_b = 0; b = 0;
156 zero = _mm_set1_epi32(0);
157 oe_del = _mm_set1_epi8(_o_del + _e_del);
158 e_del = _mm_set1_epi8(_e_del);
159 oe_ins = _mm_set1_epi8(_o_ins + _e_ins);
160 e_ins = _mm_set1_epi8(_e_ins);
161 shift = _mm_set1_epi8(q->shift);
162 H0 = q->H0; H1 = q->H1; E = q->E; Hmax = q->Hmax;
163 slen = q->slen;
164 for (i = 0; i < slen; ++i) {
165 _mm_store_si128(E + i, zero);
166 _mm_store_si128(H0 + i, zero);
167 _mm_store_si128(Hmax + i, zero);
168 }
169 // the core loop
170 for (i = 0; i < tlen; ++i) {
171 int j, k, imax;
172 __m128i e, h, t, f = zero, max = zero, *S = q->qp + target[i] * slen; // s is the 1st score vector
173 h = _mm_load_si128(H0 + slen - 1); // h={2,5,8,11,14,17,-1,-1} in the above example
174 h = _mm_slli_si128(h, 1); // h=H(i-1,-1); << instead of >> because x64 is little-endian
175 for (j = 0; LIKELY(j < slen); ++j) {
176 /* SW cells are computed in the following order:
177 * H(i,j) = max{H(i-1,j-1)+S(i,j), E(i,j), F(i,j)}
178 * E(i+1,j) = max{H(i,j)-q, E(i,j)-r}
179 * F(i,j+1) = max{H(i,j)-q, F(i,j)-r}
180 */
181 // compute H'(i,j); note that at the beginning, h=H'(i-1,j-1)
182 h = _mm_adds_epu8(h, _mm_load_si128(S + j));
183 h = _mm_subs_epu8(h, shift); // h=H'(i-1,j-1)+S(i,j)
184 e = _mm_load_si128(E + j); // e=E'(i,j)
185 h = _mm_max_epu8(h, e);
186 h = _mm_max_epu8(h, f); // h=H'(i,j)
187 max = _mm_max_epu8(max, h); // set max
188 _mm_store_si128(H1 + j, h); // save to H'(i,j)
189 // now compute E'(i+1,j)
190 e = _mm_subs_epu8(e, e_del); // e=E'(i,j) - e_del
191 t = _mm_subs_epu8(h, oe_del); // h=H'(i,j) - o_del - e_del
192 e = _mm_max_epu8(e, t); // e=E'(i+1,j)
193 _mm_store_si128(E + j, e); // save to E'(i+1,j)
194 // now compute F'(i,j+1)
195 f = _mm_subs_epu8(f, e_ins);
196 t = _mm_subs_epu8(h, oe_ins); // h=H'(i,j) - o_ins - e_ins
197 f = _mm_max_epu8(f, t);
198 // get H'(i-1,j) and prepare for the next j
199 h = _mm_load_si128(H0 + j); // h=H'(i-1,j)
200 }
201 // NB: we do not need to set E(i,j) as we disallow adjecent insertion and then deletion
202 for (k = 0; LIKELY(k < 16); ++k) { // this block mimics SWPS3; NB: H(i,j) updated in the lazy-F loop cannot exceed max
203 f = _mm_slli_si128(f, 1);
204 for (j = 0; LIKELY(j < slen); ++j) {
205 h = _mm_load_si128(H1 + j);
206 h = _mm_max_epu8(h, f); // h=H'(i,j)
207 _mm_store_si128(H1 + j, h);
208 h = _mm_subs_epu8(h, oe_ins);
209 f = _mm_subs_epu8(f, e_ins);
210 if (UNLIKELY(allzero_16(_mm_subs_epu8(f, h)))) goto end_loop16;
211 }
212 }
213 end_loop16:
214 //int k;for (k=0;k<16;++k)printf("%d ", ((uint8_t*)&max)[k]);printf("\n");
215 __max_16(imax, max); // imax is the maximum number in max
216 if (imax >= minsc) { // write the b array; this condition adds branching unfornately
217 if (n_b == 0 || (int32_t)b[n_b-1] + 1 != i) { // then append
218 if (n_b == m_b) {
219 m_b = m_b? m_b<<1 : 8;
220 b = (uint64_t*)realloc(b, 8 * m_b);
221 }
222 b[n_b++] = (uint64_t)imax<<32 | i;
223 } else if ((int)(b[n_b-1]>>32) < imax) b[n_b-1] = (uint64_t)imax<<32 | i; // modify the last
224 }
225 if (imax > gmax) {
226 gmax = imax; te = i; // te is the end position on the target
227 for (j = 0; LIKELY(j < slen); ++j) // keep the H1 vector
228 _mm_store_si128(Hmax + j, _mm_load_si128(H1 + j));
229 if (gmax + q->shift >= 255 || gmax >= endsc) break;
230 }
231 S = H1; H1 = H0; H0 = S; // swap H0 and H1
232 }
233 r.score = gmax + q->shift < 255? gmax : 255;
234 r.te = te;
235 if (r.score != 255) { // get a->qe, the end of query match; find the 2nd best score
236 int max = -1, tmp, low, high, qlen = slen * 16;
237 uint8_t *t = (uint8_t*)Hmax;
238 for (i = 0; i < qlen; ++i, ++t)
239 if ((int)*t > max) max = *t, r.qe = i / 16 + i % 16 * slen;
240 else if ((int)*t == max && (tmp = i / 16 + i % 16 * slen) < r.qe) r.qe = tmp;
241 //printf("%d,%d\n", max, gmax);
242 if (b) {
243 i = (r.score + q->max - 1) / q->max;
244 low = te - i; high = te + i;
245 for (i = 0; i < n_b; ++i) {
246 int e = (int32_t)b[i];
247 if ((e < low || e > high) && (int)(b[i]>>32) > r.score2)
248 r.score2 = b[i]>>32, r.te2 = e;
249 }
250 }
251 }
252 free(b);
253 return r;
254 }
255
256 kswr_t ksw_i16(kswq_t *q, int tlen, const uint8_t *target, int _o_del, int _e_del, int _o_ins, int _e_ins, int xtra) // the first gap costs -(_o+_e)
257 {
258 int slen, i, m_b, n_b, te = -1, gmax = 0, minsc, endsc;
259 uint64_t *b;
260 __m128i zero, oe_del, e_del, oe_ins, e_ins, *H0, *H1, *E, *Hmax;
261 kswr_t r;
262
263 #if defined __SSE2__
264 #define __max_8(ret, xx) do { \
265 (xx) = _mm_max_epi16((xx), _mm_srli_si128((xx), 8)); \
266 (xx) = _mm_max_epi16((xx), _mm_srli_si128((xx), 4)); \
267 (xx) = _mm_max_epi16((xx), _mm_srli_si128((xx), 2)); \
268 (ret) = _mm_extract_epi16((xx), 0); \
269 } while (0)
270
271 // Given entries all either 0x0000 or 0xffff, return whether they are all 0x0000
272 #define allzero_0f_8(xx) (!_mm_movemask_epi8((xx)))
273
274 #elif defined __ARM_NEON
275 #define __max_8(ret, xx) (ret) = vmaxvq_s16(vreinterpretq_s16_u8((xx)))
276 #define allzero_0f_8(xx) (vmaxvq_u16(vreinterpretq_u16_u8((xx))) == 0)
277
278 #else
279 #define __max_8(ret, xx) (ret) = m128i_max_s16((xx))
280 #define allzero_0f_8(xx) (m128i_allzero((xx)))
281 #endif
282
283 // initialization
284 r = g_defr;
285 minsc = (xtra&KSW_XSUBO)? xtra&0xffff : 0x10000;
286 endsc = (xtra&KSW_XSTOP)? xtra&0xffff : 0x10000;
287 m_b = n_b = 0; b = 0;
288 zero = _mm_set1_epi32(0);
289 oe_del = _mm_set1_epi16(_o_del + _e_del);
290 e_del = _mm_set1_epi16(_e_del);
291 oe_ins = _mm_set1_epi16(_o_ins + _e_ins);
292 e_ins = _mm_set1_epi16(_e_ins);
293 H0 = q->H0; H1 = q->H1; E = q->E; Hmax = q->Hmax;
294 slen = q->slen;
295 for (i = 0; i < slen; ++i) {
296 _mm_store_si128(E + i, zero);
297 _mm_store_si128(H0 + i, zero);
298 _mm_store_si128(Hmax + i, zero);
299 }
300 // the core loop
301 for (i = 0; i < tlen; ++i) {
302 int j, k, imax;
303 __m128i e, t, h, f = zero, max = zero, *S = q->qp + target[i] * slen; // s is the 1st score vector
304 h = _mm_load_si128(H0 + slen - 1); // h={2,5,8,11,14,17,-1,-1} in the above example
305 h = _mm_slli_si128(h, 2);
306 for (j = 0; LIKELY(j < slen); ++j) {
307 h = _mm_adds_epi16(h, _mm_load_si128(S++));
308 e = _mm_load_si128(E + j);
309 h = _mm_max_epi16(h, e);
310 h = _mm_max_epi16(h, f);
311 max = _mm_max_epi16(max, h);
312 _mm_store_si128(H1 + j, h);
313 e = _mm_subs_epu16(e, e_del);
314 t = _mm_subs_epu16(h, oe_del);
315 e = _mm_max_epi16(e, t);
316 _mm_store_si128(E + j, e);
317 f = _mm_subs_epu16(f, e_ins);
318 t = _mm_subs_epu16(h, oe_ins);
319 f = _mm_max_epi16(f, t);
320 h = _mm_load_si128(H0 + j);
321 }
322 for (k = 0; LIKELY(k < 16); ++k) {
323 f = _mm_slli_si128(f, 2);
324 for (j = 0; LIKELY(j < slen); ++j) {
325 h = _mm_load_si128(H1 + j);
326 h = _mm_max_epi16(h, f);
327 _mm_store_si128(H1 + j, h);
328 h = _mm_subs_epu16(h, oe_ins);
329 f = _mm_subs_epu16(f, e_ins);
330 if(UNLIKELY(allzero_0f_8(_mm_cmpgt_epi16(f, h)))) goto end_loop8;
331 }
332 }
333 end_loop8:
334 __max_8(imax, max);
335 if (imax >= minsc) {
336 if (n_b == 0 || (int32_t)b[n_b-1] + 1 != i) {
337 if (n_b == m_b) {
338 m_b = m_b? m_b<<1 : 8;
339 b = (uint64_t*)realloc(b, 8 * m_b);
340 }
341 b[n_b++] = (uint64_t)imax<<32 | i;
342 } else if ((int)(b[n_b-1]>>32) < imax) b[n_b-1] = (uint64_t)imax<<32 | i; // modify the last
343 }
344 if (imax > gmax) {
345 gmax = imax; te = i;
346 for (j = 0; LIKELY(j < slen); ++j)
347 _mm_store_si128(Hmax + j, _mm_load_si128(H1 + j));
348 if (gmax >= endsc) break;
349 }
350 S = H1; H1 = H0; H0 = S;
351 }
352 r.score = gmax; r.te = te;
353 {
354 int max = -1, tmp, low, high, qlen = slen * 8;
355 uint16_t *t = (uint16_t*)Hmax;
356 for (i = 0, r.qe = -1; i < qlen; ++i, ++t)
357 if ((int)*t > max) max = *t, r.qe = i / 8 + i % 8 * slen;
358 else if ((int)*t == max && (tmp = i / 8 + i % 8 * slen) < r.qe) r.qe = tmp;
359 if (b) {
360 i = (r.score + q->max - 1) / q->max;
361 low = te - i; high = te + i;
362 for (i = 0; i < n_b; ++i) {
363 int e = (int32_t)b[i];
364 if ((e < low || e > high) && (int)(b[i]>>32) > r.score2)
365 r.score2 = b[i]>>32, r.te2 = e;
366 }
367 }
368 }
369 free(b);
370 return r;
371 }
372
373 static inline void revseq(int l, uint8_t *s)
374 {
375 int i, t;
376 for (i = 0; i < l>>1; ++i)
377 t = s[i], s[i] = s[l - 1 - i], s[l - 1 - i] = t;
378 }
379
380 kswr_t ksw_align2(int qlen, uint8_t *query, int tlen, uint8_t *target, int m, const int8_t *mat, int o_del, int e_del, int o_ins, int e_ins, int xtra, kswq_t **qry)
381 {
382 int size;
383 kswq_t *q;
384 kswr_t r, rr;
385 kswr_t (*func)(kswq_t*, int, const uint8_t*, int, int, int, int, int);
386
387 q = (qry && *qry)? *qry : ksw_qinit((xtra&KSW_XBYTE)? 1 : 2, qlen, query, m, mat);
388 if (qry && *qry == 0) *qry = q;
389 func = q->size == 2? ksw_i16 : ksw_u8;
390 size = q->size;
391 r = func(q, tlen, target, o_del, e_del, o_ins, e_ins, xtra);
392 if (qry == 0) free(q);
393 if ((xtra&KSW_XSTART) == 0 || ((xtra&KSW_XSUBO) && r.score < (xtra&0xffff))) return r;
394 revseq(r.qe + 1, query); revseq(r.te + 1, target); // +1 because qe/te points to the exact end, not the position after the end
395 q = ksw_qinit(size, r.qe + 1, query, m, mat);
396 rr = func(q, tlen, target, o_del, e_del, o_ins, e_ins, KSW_XSTOP | r.score);
397 revseq(r.qe + 1, query); revseq(r.te + 1, target);
398 free(q);
399 if (r.score == rr.score)
400 r.tb = r.te - rr.te, r.qb = r.qe - rr.qe;
401 return r;
402 }
403
404 kswr_t ksw_align(int qlen, uint8_t *query, int tlen, uint8_t *target, int m, const int8_t *mat, int gapo, int gape, int xtra, kswq_t **qry)
405 {
406 return ksw_align2(qlen, query, tlen, target, m, mat, gapo, gape, gapo, gape, xtra, qry);
407 }
408
409 /********************
410 *** SW extension ***
411 ********************/
412
413 typedef struct {
414 int32_t h, e;
415 } eh_t;
416
417 int ksw_extend2(int qlen, const uint8_t *query, int tlen, const uint8_t *target, int m, const int8_t *mat, int o_del, int e_del, int o_ins, int e_ins, int w, int end_bonus, int zdrop, int h0, int *_qle, int *_tle, int *_gtle, int *_gscore, int *_max_off)
418 {
419 eh_t *eh; // score array
420 int8_t *qp; // query profile
421 int i, j, k, oe_del = o_del + e_del, oe_ins = o_ins + e_ins, beg, end, max, max_i, max_j, max_ins, max_del, max_ie, gscore, max_off;
422 assert(h0 > 0);
423 // allocate memory
424 qp = malloc(qlen * m);
•425 eh = calloc(qlen + 2, 8);
426 // generate the query profile
427 for (k = i = 0; k < m; ++k) {
428 const int8_t *p = &mat[k * m];
429 for (j = 0; j < qlen; ++j) qp[i++] = p[query[j]];
430 }
431 // fill the first row
432 eh[0].h = h0; eh[1].h = h0 > oe_ins? h0 - oe_ins : 0;
433 for (j = 2; j <= qlen && eh[j-1].h > e_ins; ++j)
434 eh[j].h = eh[j-1].h - e_ins;
435 // adjust $w if it is too large
436 k = m * m;
437 for (i = 0, max = 0; i < k; ++i) // get the max score
438 max = max > mat[i]? max : mat[i];
439 max_ins = (int)((double)(qlen * max + end_bonus - o_ins) / e_ins + 1.);
440 max_ins = max_ins > 1? max_ins : 1;
441 w = w < max_ins? w : max_ins;
442 max_del = (int)((double)(qlen * max + end_bonus - o_del) / e_del + 1.);
443 max_del = max_del > 1? max_del : 1;
444 w = w < max_del? w : max_del; // TODO: is this necessary?
445 // DP loop
446 max = h0, max_i = max_j = -1; max_ie = -1, gscore = -1;
447 max_off = 0;
448 beg = 0, end = qlen;
449 for (i = 0; LIKELY(i < tlen); ++i) {
450 int t, f = 0, h1, m = 0, mj = -1;
451 int8_t *q = &qp[target[i] * qlen];
452 // apply the band and the constraint (if provided)
453 if (beg < i - w) beg = i - w;
454 if (end > i + w + 1) end = i + w + 1;
455 if (end > qlen) end = qlen;
456 // compute the first column
457 if (beg == 0) {
458 h1 = h0 - (o_del + e_del * (i + 1));
459 if (h1 < 0) h1 = 0;
460 } else h1 = 0;
461 for (j = beg; LIKELY(j < end); ++j) {
462 // At the beginning of the loop: eh[j] = { H(i-1,j-1), E(i,j) }, f = F(i,j) and h1 = H(i,j-1)
463 // Similar to SSE2-SW, cells are computed in the following order:
464 // H(i,j) = max{H(i-1,j-1)+S(i,j), E(i,j), F(i,j)}
465 // E(i+1,j) = max{H(i,j)-gapo, E(i,j)} - gape
466 // F(i,j+1) = max{H(i,j)-gapo, F(i,j)} - gape
467 eh_t *p = &eh[j];
468 int h, M = p->h, e = p->e; // get H(i-1,j-1) and E(i-1,j)
469 p->h = h1; // set H(i,j-1) for the next row
470 M = M? M + q[j] : 0;// separating H and M to disallow a cigar like "100M3I3D20M"
471 h = M > e? M : e; // e and f are guaranteed to be non-negative, so h>=0 even if M<0
472 h = h > f? h : f;
473 h1 = h; // save H(i,j) to h1 for the next column
474 mj = m > h? mj : j; // record the position where max score is achieved
475 m = m > h? m : h; // m is stored at eh[mj+1]
476 t = M - oe_del;
477 t = t > 0? t : 0;
478 e -= e_del;
479 e = e > t? e : t; // computed E(i+1,j)
480 p->e = e; // save E(i+1,j) for the next row
481 t = M - oe_ins;
482 t = t > 0? t : 0;
483 f -= e_ins;
484 f = f > t? f : t; // computed F(i,j+1)
485 }
486 eh[end].h = h1; eh[end].e = 0;
487 if (j == qlen) {
488 max_ie = gscore > h1? max_ie : i;
489 gscore = gscore > h1? gscore : h1;
490 }
491 if (m == 0) break;
492 if (m > max) {
493 max = m, max_i = i, max_j = mj;
494 max_off = max_off > abs(mj - i)? max_off : abs(mj - i);
495 } else if (zdrop > 0) {
496 if (i - max_i > mj - max_j) {
497 if (max - m - ((i - max_i) - (mj - max_j)) * e_del > zdrop) break;
498 } else {
499 if (max - m - ((mj - max_j) - (i - max_i)) * e_ins > zdrop) break;
500 }
501 }
502 // update beg and end for the next round
503 for (j = beg; LIKELY(j < end) && eh[j].h == 0 && eh[j].e == 0; ++j);
504 beg = j;
505 for (j = end; LIKELY(j >= beg) && eh[j].h == 0 && eh[j].e == 0; --j);
506 end = j + 2 < qlen? j + 2 : qlen;
507 //beg = 0; end = qlen; // uncomment this line for debugging
508 }
509 free(eh); free(qp);
510 if (_qle) *_qle = max_j + 1;
511 if (_tle) *_tle = max_i + 1;
512 if (_gtle) *_gtle = max_ie + 1;
513 if (_gscore) *_gscore = gscore;
514 if (_max_off) *_max_off = max_off;
515 return max;
516 }
517
518 int ksw_extend(int qlen, const uint8_t *query, int tlen, const uint8_t *target, int m, const int8_t *mat, int gapo, int gape, int w, int end_bonus, int zdrop, int h0, int *qle, int *tle, int *gtle, int *gscore, int *max_off)
519 {
520 return ksw_extend2(qlen, query, tlen, target, m, mat, gapo, gape, gapo, gape, w, end_bonus, zdrop, h0, qle, tle, gtle, gscore, max_off);
521 }
522
523 /********************
524 * Global alignment *
525 ********************/
526
527 #define MINUS_INF -0x40000000
528
529 static inline uint32_t *push_cigar(int *n_cigar, int *m_cigar, uint32_t *cigar, int op, int len)
530 {
531 if (*n_cigar == 0 || op != (cigar[(*n_cigar) - 1]&0xf)) {
532 if (*n_cigar == *m_cigar) {
533 *m_cigar = *m_cigar? (*m_cigar)<<1 : 4;
534 cigar = realloc(cigar, (*m_cigar) << 2);
535 }
536 cigar[(*n_cigar)++] = len<<4 | op;
537 } else cigar[(*n_cigar)-1] += len<<4;
538 return cigar;
539 }
540
541 int ksw_global2(int qlen, const uint8_t *query, int tlen, const uint8_t *target, int m, const int8_t *mat, int o_del, int e_del, int o_ins, int e_ins, int w, int *n_cigar_, uint32_t **cigar_)
542 {
543 eh_t *eh;
544 int8_t *qp; // query profile
545 int i, j, k, oe_del = o_del + e_del, oe_ins = o_ins + e_ins, score, n_col;
546 uint8_t *z; // backtrack matrix; in each cell: f<<4|e<<2|h; in principle, we can halve the memory, but backtrack will be a little more complex
547 if (n_cigar_) *n_cigar_ = 0;
548 // allocate memory
549 n_col = qlen < 2*w+1? qlen : 2*w+1; // maximum #columns of the backtrack matrix
550 z = n_cigar_ && cigar_? malloc((long)n_col * tlen) : 0;
551 qp = malloc(qlen * m);
552 eh = calloc(qlen + 1, 8);
553 // generate the query profile
554 for (k = i = 0; k < m; ++k) {
555 const int8_t *p = &mat[k * m];
556 for (j = 0; j < qlen; ++j) qp[i++] = p[query[j]];
557 }
558 // fill the first row
559 eh[0].h = 0; eh[0].e = MINUS_INF;
560 for (j = 1; j <= qlen && j <= w; ++j)
561 eh[j].h = -(o_ins + e_ins * j), eh[j].e = MINUS_INF;
562 for (; j <= qlen; ++j) eh[j].h = eh[j].e = MINUS_INF; // everything is -inf outside the band
563 // DP loop
564 for (i = 0; LIKELY(i < tlen); ++i) { // target sequence is in the outer loop
565 int32_t f = MINUS_INF, h1, beg, end, t;
566 int8_t *q = &qp[target[i] * qlen];
567 beg = i > w? i - w : 0;
568 end = i + w + 1 < qlen? i + w + 1 : qlen; // only loop through [beg,end) of the query sequence
569 h1 = beg == 0? -(o_del + e_del * (i + 1)) : MINUS_INF;
570 if (n_cigar_ && cigar_) {
571 uint8_t *zi = &z[(long)i * n_col];
572 for (j = beg; LIKELY(j < end); ++j) {
573 // At the beginning of the loop: eh[j] = { H(i-1,j-1), E(i,j) }, f = F(i,j) and h1 = H(i,j-1)
574 // Cells are computed in the following order:
575 // M(i,j) = H(i-1,j-1) + S(i,j)
576 // H(i,j) = max{M(i,j), E(i,j), F(i,j)}
577 // E(i+1,j) = max{M(i,j)-gapo, E(i,j)} - gape
578 // F(i,j+1) = max{M(i,j)-gapo, F(i,j)} - gape
579 // We have to separate M(i,j); otherwise the direction may not be recorded correctly.
580 // However, a CIGAR like "10M3I3D10M" allowed by local() is disallowed by global().
581 // Such a CIGAR may occur, in theory, if mismatch_penalty > 2*gap_ext_penalty + 2*gap_open_penalty/k.
582 // In practice, this should happen very rarely given a reasonable scoring system.
583 eh_t *p = &eh[j];
584 int32_t h, m = p->h, e = p->e;
585 uint8_t d; // direction
586 p->h = h1;
587 m += q[j];
588 d = m >= e? 0 : 1;
589 h = m >= e? m : e;
590 d = h >= f? d : 2;
591 h = h >= f? h : f;
592 h1 = h;
593 t = m - oe_del;
594 e -= e_del;
595 d |= e > t? 1<<2 : 0;
596 e = e > t? e : t;
597 p->e = e;
598 t = m - oe_ins;
599 f -= e_ins;
600 d |= f > t? 2<<4 : 0; // if we want to halve the memory, use one bit only, instead of two
601 f = f > t? f : t;
602 zi[j - beg] = d; // z[i,j] keeps h for the current cell and e/f for the next cell
603 }
604 } else {
605 for (j = beg; LIKELY(j < end); ++j) {
606 eh_t *p = &eh[j];
607 int32_t h, m = p->h, e = p->e;
608 p->h = h1;
609 m += q[j];
610 h = m >= e? m : e;
611 h = h >= f? h : f;
612 h1 = h;
613 t = m - oe_del;
614 e -= e_del;
615 e = e > t? e : t;
616 p->e = e;
617 t = m - oe_ins;
618 f -= e_ins;
619 f = f > t? f : t;
620 }
621 }
622 eh[end].h = h1; eh[end].e = MINUS_INF;
623 }
624 score = eh[qlen].h;
625 if (n_cigar_ && cigar_) { // backtrack
626 int n_cigar = 0, m_cigar = 0, which = 0;
627 uint32_t *cigar = 0, tmp;
628 i = tlen - 1; k = (i + w + 1 < qlen? i + w + 1 : qlen) - 1; // (i,k) points to the last cell
629 while (i >= 0 && k >= 0) {
630 which = z[(long)i * n_col + (k - (i > w? i - w : 0))] >> (which<<1) & 3;
631 if (which == 0) cigar = push_cigar(&n_cigar, &m_cigar, cigar, 0, 1), --i, --k;
632 else if (which == 1) cigar = push_cigar(&n_cigar, &m_cigar, cigar, 2, 1), --i;
633 else cigar = push_cigar(&n_cigar, &m_cigar, cigar, 1, 1), --k;
634 }
635 if (i >= 0) cigar = push_cigar(&n_cigar, &m_cigar, cigar, 2, i + 1);
636 if (k >= 0) cigar = push_cigar(&n_cigar, &m_cigar, cigar, 1, k + 1);
637 for (i = 0; i < n_cigar>>1; ++i) // reverse CIGAR
638 tmp = cigar[i], cigar[i] = cigar[n_cigar-1-i], cigar[n_cigar-1-i] = tmp;
639 *n_cigar_ = n_cigar, *cigar_ = cigar;
640 }
641 free(eh); free(qp); free(z);
642 return score;
643 }
644
645 int ksw_global(int qlen, const uint8_t *query, int tlen, const uint8_t *target, int m, const int8_t *mat, int gapo, int gape, int w, int *n_cigar_, uint32_t **cigar_)
646 {
647 return ksw_global2(qlen, query, tlen, target, m, mat, gapo, gape, gapo, gape, w, n_cigar_, cigar_);
648 }
649
650 /*******************************************
651 * Main function (not compiled by default) *
652 *******************************************/
653
654 #ifdef _KSW_MAIN
655
656 #include <unistd.h>
657 #include <stdio.h>
658 #include <zlib.h>
659 #include "kseq.h"
660 KSEQ_INIT(gzFile, err_gzread)
661
662 unsigned char seq_nt4_table[256] = {
663 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
664 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
665 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
666 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
667 4, 0, 4, 1, 4, 4, 4, 2, 4, 4, 4, 4, 4, 4, 4, 4,
668 4, 4, 4, 4, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
669 4, 0, 4, 1, 4, 4, 4, 2, 4, 4, 4, 4, 4, 4, 4, 4,
670 4, 4, 4, 4, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
671 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
672 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
673 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
674 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
675 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
676 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
677 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
678 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4
679 };
680
681 int main(int argc, char *argv[])
682 {
683 int c, sa = 1, sb = 3, i, j, k, forward_only = 0, max_rseq = 0;
684 int8_t mat[25];
685 int gapo = 5, gape = 2, minsc = 0, xtra = KSW_XSTART;
686 uint8_t *rseq = 0;
687 gzFile fpt, fpq;
688 kseq_t *kst, *ksq;
689
690 // parse command line
691 while ((c = getopt(argc, argv, "a:b:q:r:ft:1")) >= 0) {
692 switch (c) {
693 case 'a': sa = atoi(optarg); break;
694 case 'b': sb = atoi(optarg); break;
695 case 'q': gapo = atoi(optarg); break;
696 case 'r': gape = atoi(optarg); break;
697 case 't': minsc = atoi(optarg); break;
698 case 'f': forward_only = 1; break;
699 case '1': xtra |= KSW_XBYTE; break;
700 }
701 }
702 if (optind + 2 > argc) {
703 fprintf(stderr, "Usage: ksw [-1] [-f] [-a%d] [-b%d] [-q%d] [-r%d] [-t%d] <target.fa> <query.fa>\n", sa, sb, gapo, gape, minsc);
704 return 1;
705 }
706 if (minsc > 0xffff) minsc = 0xffff;
707 xtra |= KSW_XSUBO | minsc;
708 // initialize scoring matrix
709 for (i = k = 0; i < 4; ++i) {
710 for (j = 0; j < 4; ++j)
711 mat[k++] = i == j? sa : -sb;
712 mat[k++] = 0; // ambiguous base
713 }
714 for (j = 0; j < 5; ++j) mat[k++] = 0;
715 // open file
716 fpt = xzopen(argv[optind], "r"); kst = kseq_init(fpt);
717 fpq = xzopen(argv[optind+1], "r"); ksq = kseq_init(fpq);
718 // all-pair alignment
719 while (kseq_read(ksq) > 0) {
720 kswq_t *q[2] = {0, 0};
721 kswr_t r;
722 for (i = 0; i < (int)ksq->seq.l; ++i) ksq->seq.s[i] = seq_nt4_table[(int)ksq->seq.s[i]];
723 if (!forward_only) { // reverse
724 if ((int)ksq->seq.m > max_rseq) {
725 max_rseq = ksq->seq.m;
726 rseq = (uint8_t*)realloc(rseq, max_rseq);
727 }
728 for (i = 0, j = ksq->seq.l - 1; i < (int)ksq->seq.l; ++i, --j)
729 rseq[j] = ksq->seq.s[i] == 4? 4 : 3 - ksq->seq.s[i];
730 }
731 gzrewind(fpt); kseq_rewind(kst);
732 while (kseq_read(kst) > 0) {
733 for (i = 0; i < (int)kst->seq.l; ++i) kst->seq.s[i] = seq_nt4_table[(int)kst->seq.s[i]];
734 r = ksw_align(ksq->seq.l, (uint8_t*)ksq->seq.s, kst->seq.l, (uint8_t*)kst->seq.s, 5, mat, gapo, gape, xtra, &q[0]);
735 if (r.score >= minsc)
736 err_printf("%s\t%d\t%d\t%s\t%d\t%d\t%d\t%d\t%d\n", kst->name.s, r.tb, r.te+1, ksq->name.s, r.qb, r.qe+1, r.score, r.score2, r.te2);
737 if (rseq) {
738 r = ksw_align(ksq->seq.l, rseq, kst->seq.l, (uint8_t*)kst->seq.s, 5, mat, gapo, gape, xtra, &q[1]);
739 if (r.score >= minsc)
740 err_printf("%s\t%d\t%d\t%s\t%d\t%d\t%d\t%d\t%d\n", kst->name.s, r.tb, r.te+1, ksq->name.s, (int)ksq->seq.l - r.qb, (int)ksq->seq.l - 1 - r.qe, r.score, r.score2, r.te2);
741 }
742 }
743 free(q[0]); free(q[1]);
744 }
745 free(rseq);
746 kseq_destroy(kst); err_gzclose(fpt);
747 kseq_destroy(ksq); err_gzclose(fpq);
748 return 0;
749 }
750 #endif