Debian Codegraph @

bwa-apache2/ksw.c

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