Debian Codegraph @

bwa-apache2/bwamem.c

raw
1 /* The MIT License
2
3 Copyright (c) 2018- Dana-Farber Cancer Institute
4 2009-2018 Broad Institute, Inc.
5 2008-2009 Genome Research Ltd. (GRL)
6
7 Permission is hereby granted, free of charge, to any person obtaining
8 a copy of this software and associated documentation files (the
9 "Software"), to deal in the Software without restriction, including
10 without limitation the rights to use, copy, modify, merge, publish,
11 distribute, sublicense, and/or sell copies of the Software, and to
12 permit persons to whom the Software is furnished to do so, subject to
13 the following conditions:
14
15 The above copyright notice and this permission notice shall be
16 included in all copies or substantial portions of the Software.
17
18 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
19 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
20 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
21 NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
22 BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
23 ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
24 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
25 SOFTWARE.
26 */
27 #include <stdlib.h>
28 #include <string.h>
29 #include <stdio.h>
30 #include <assert.h>
31 #include <limits.h>
32 #include <math.h>
33 #ifdef HAVE_PTHREAD
34 #include <pthread.h>
35 #endif
36
37 #include "kstring.h"
38 #include "bwamem.h"
39 #include "bntseq.h"
40 #include "ksw.h"
41 #include "kvec.h"
42 #include "ksort.h"
43 #include "utils.h"
44
45 #ifdef USE_MALLOC_WRAPPERS
46 # include "malloc_wrap.h"
47 #endif
48
49 /* Theory on probability and scoring *ungapped* alignment
50 *
51 * s'(a,b) = log[P(b|a)/P(b)] = log[4P(b|a)], assuming uniform base distribution
52 * s'(a,a) = log(4), s'(a,b) = log(4e/3), where e is the error rate
53 *
54 * Scale s'(a,b) to s(a,a) s.t. s(a,a)=x. Then s(a,b) = x*s'(a,b)/log(4), or conversely: s'(a,b)=s(a,b)*log(4)/x
55 *
56 * If the matching score is x and mismatch penalty is -y, we can compute error rate e:
57 * e = .75 * exp[-log(4) * y/x]
58 *
59 * log P(seq) = \sum_i log P(b_i|a_i) = \sum_i {s'(a,b) - log(4)}
60 * = \sum_i { s(a,b)*log(4)/x - log(4) } = log(4) * (S/x - l)
61 *
62 * where S=\sum_i s(a,b) is the alignment score. Converting to the phred scale:
63 * Q(seq) = -10/log(10) * log P(seq) = 10*log(4)/log(10) * (l - S/x) = 6.02 * (l - S/x)
64 *
65 *
66 * Gap open (zero gap): q' = log[P(gap-open)], r' = log[P(gap-ext)] (see Durbin et al. (1998) Section 4.1)
67 * Then q = x*log[P(gap-open)]/log(4), r = x*log[P(gap-ext)]/log(4)
68 *
69 * When there are gaps, l should be the length of alignment matches (i.e. the M operator in CIGAR)
70 */
71
72 static const bntseq_t *global_bns = 0; // for debugging only
73
74 mem_opt_t *mem_opt_init()
75 {
76 mem_opt_t *o;
77 o = calloc(1, sizeof(mem_opt_t));
78 o->flag = 0;
79 o->a = 1; o->b = 4;
80 o->o_del = o->o_ins = 6;
81 o->e_del = o->e_ins = 1;
82 o->w = 100;
83 o->T = 30;
84 o->zdrop = 100;
85 o->pen_unpaired = 17;
86 o->pen_clip5 = o->pen_clip3 = 5;
87
88 o->max_mem_intv = 20;
89
90 o->min_seed_len = 19;
91 o->split_width = 10;
92 o->max_occ = 500;
93 o->max_chain_gap = 10000;
94 o->max_ins = 10000;
95 o->mask_level = 0.50;
96 o->drop_ratio = 0.50;
97 o->XA_drop_ratio = 0.80;
98 o->split_factor = 1.5;
99 o->chunk_size = 10000000;
100 o->n_threads = 1;
101 o->max_XA_hits = 5;
102 o->max_XA_hits_alt = 200;
103 o->max_matesw = 50;
104 o->mask_level_redun = 0.95;
105 o->min_chain_weight = 0;
106 o->max_chain_extend = 1<<30;
107 o->mapQ_coef_len = 50; o->mapQ_coef_fac = log(o->mapQ_coef_len);
108 bwa_fill_scmat(o->a, o->b, o->mat);
109 return o;
110 }
111
112 /***************************
113 * Collection SA invervals *
114 ***************************/
115
116 #define intv_lt(a, b) ((a).info < (b).info)
117 KSORT_INIT(mem_intv, bwtintv_t, intv_lt)
118
119 typedef struct {
120 bwtintv_v mem, mem1, *tmpv[2];
121 } smem_aux_t;
122
123 static smem_aux_t *smem_aux_init()
124 {
125 smem_aux_t *a;
126 a = calloc(1, sizeof(smem_aux_t));
127 a->tmpv[0] = calloc(1, sizeof(bwtintv_v));
128 a->tmpv[1] = calloc(1, sizeof(bwtintv_v));
129 return a;
130 }
131
132 static void smem_aux_destroy(smem_aux_t *a)
133 {
134 free(a->tmpv[0]->a); free(a->tmpv[0]);
135 free(a->tmpv[1]->a); free(a->tmpv[1]);
136 free(a->mem.a); free(a->mem1.a);
137 free(a);
138 }
139
140 static void mem_collect_intv(const mem_opt_t *opt, const bwt_t *bwt, int len, const uint8_t *seq, smem_aux_t *a)
141 {
142 int i, k, x = 0, old_n;
143 int start_width = 1;
144 int split_len = (int)(opt->min_seed_len * opt->split_factor + .499);
145 a->mem.n = 0;
146 // first pass: find all SMEMs
147 while (x < len) {
148 if (seq[x] < 4) {
149 x = bwt_smem1(bwt, len, seq, x, start_width, &a->mem1, a->tmpv);
150 for (i = 0; i < a->mem1.n; ++i) {
151 bwtintv_t *p = &a->mem1.a[i];
152 int slen = (uint32_t)p->info - (p->info>>32); // seed length
153 if (slen >= opt->min_seed_len)
154 kv_push(bwtintv_t, a->mem, *p);
155 }
156 } else ++x;
157 }
158 // second pass: find MEMs inside a long SMEM
159 old_n = a->mem.n;
160 for (k = 0; k < old_n; ++k) {
161 bwtintv_t *p = &a->mem.a[k];
162 int start = p->info>>32, end = (int32_t)p->info;
163 if (end - start < split_len || p->x[2] > opt->split_width) continue;
164 bwt_smem1(bwt, len, seq, (start + end)>>1, p->x[2]+1, &a->mem1, a->tmpv);
165 for (i = 0; i < a->mem1.n; ++i)
166 if ((uint32_t)a->mem1.a[i].info - (a->mem1.a[i].info>>32) >= opt->min_seed_len)
167 kv_push(bwtintv_t, a->mem, a->mem1.a[i]);
168 }
169 // third pass: LAST-like
170 if (opt->max_mem_intv > 0) {
171 x = 0;
172 while (x < len) {
173 if (seq[x] < 4) {
174 if (1) {
175 bwtintv_t m;
176 x = bwt_seed_strategy1(bwt, len, seq, x, opt->min_seed_len, opt->max_mem_intv, &m);
177 if (m.x[2] > 0) kv_push(bwtintv_t, a->mem, m);
178 } else { // for now, we never come to this block which is slower
179 x = bwt_smem1a(bwt, len, seq, x, start_width, opt->max_mem_intv, &a->mem1, a->tmpv);
180 for (i = 0; i < a->mem1.n; ++i)
181 kv_push(bwtintv_t, a->mem, a->mem1.a[i]);
182 }
183 } else ++x;
184 }
185 }
186 // sort
187 ks_introsort(mem_intv, a->mem.n, a->mem.a);
188 }
189
190 /************
191 * Chaining *
192 ************/
193
194 typedef struct {
195 int64_t rbeg;
196 int32_t qbeg, len;
197 int score;
198 } mem_seed_t; // unaligned memory
199
200 typedef struct {
201 int n, m, first, rid;
202 uint32_t w:29, kept:2, is_alt:1;
203 float frac_rep;
204 int64_t pos;
205 mem_seed_t *seeds;
206 } mem_chain_t;
207
208 typedef struct { size_t n, m; mem_chain_t *a; } mem_chain_v;
209
210 #include "kbtree.h"
211
212 #define chain_cmp(a, b) (((b).pos < (a).pos) - ((a).pos < (b).pos))
213 KBTREE_INIT(chn, mem_chain_t, chain_cmp)
214
215 // return 1 if the seed is merged into the chain
216 static int test_and_merge(const mem_opt_t *opt, int64_t l_pac, mem_chain_t *c, const mem_seed_t *p, int seed_rid)
217 {
218 int64_t qend, rend, x, y;
219 const mem_seed_t *last = &c->seeds[c->n-1];
220 qend = last->qbeg + last->len;
221 rend = last->rbeg + last->len;
222 if (seed_rid != c->rid) return 0; // different chr; request a new chain
223 if (p->qbeg >= c->seeds[0].qbeg && p->qbeg + p->len <= qend && p->rbeg >= c->seeds[0].rbeg && p->rbeg + p->len <= rend)
224 return 1; // contained seed; do nothing
225 if ((last->rbeg < l_pac || c->seeds[0].rbeg < l_pac) && p->rbeg >= l_pac) return 0; // don't chain if on different strand
226 x = p->qbeg - last->qbeg; // always non-negtive
227 y = p->rbeg - last->rbeg;
228 if (y >= 0 && x - y <= opt->w && y - x <= opt->w && x - last->len < opt->max_chain_gap && y - last->len < opt->max_chain_gap) { // grow the chain
229 if (c->n == c->m) {
230 c->m <<= 1;
231 c->seeds = realloc(c->seeds, c->m * sizeof(mem_seed_t));
232 }
233 c->seeds[c->n++] = *p;
234 return 1;
235 }
236 return 0; // request to add a new chain
237 }
238
239 int mem_chain_weight(const mem_chain_t *c)
240 {
241 int64_t end;
242 int j, w = 0, tmp;
243 for (j = 0, end = 0; j < c->n; ++j) {
244 const mem_seed_t *s = &c->seeds[j];
245 if (s->qbeg >= end) w += s->len;
246 else if (s->qbeg + s->len > end) w += s->qbeg + s->len - end;
247 end = end > s->qbeg + s->len? end : s->qbeg + s->len;
248 }
249 tmp = w; w = 0;
250 for (j = 0, end = 0; j < c->n; ++j) {
251 const mem_seed_t *s = &c->seeds[j];
252 if (s->rbeg >= end) w += s->len;
253 else if (s->rbeg + s->len > end) w += s->rbeg + s->len - end;
254 end = end > s->rbeg + s->len? end : s->rbeg + s->len;
255 }
256 w = w < tmp? w : tmp;
257 return w < 1<<30? w : (1<<30)-1;
258 }
259
260 void mem_print_chain(const bntseq_t *bns, mem_chain_v *chn)
261 {
262 int i, j;
263 for (i = 0; i < chn->n; ++i) {
264 mem_chain_t *p = &chn->a[i];
265 err_printf("* Found CHAIN(%d): n=%d; weight=%d", i, p->n, mem_chain_weight(p));
266 for (j = 0; j < p->n; ++j) {
267 bwtint_t pos;
268 int is_rev;
269 pos = bns_depos(bns, p->seeds[j].rbeg, &is_rev);
270 if (is_rev) pos -= p->seeds[j].len - 1;
271 err_printf("\t%d;%d;%d,%ld(%s:%c%ld)", p->seeds[j].score, p->seeds[j].len, p->seeds[j].qbeg, (long)p->seeds[j].rbeg, bns->anns[p->rid].name, "+-"[is_rev], (long)(pos - bns->anns[p->rid].offset) + 1);
272 }
273 err_putchar('\n');
274 }
275 }
276
277 mem_chain_v mem_chain(const mem_opt_t *opt, const bwt_t *bwt, const bntseq_t *bns, int len, const uint8_t *seq, void *buf)
278 {
279 int i, b, e, l_rep;
280 int64_t l_pac = bns->l_pac;
281 mem_chain_v chain;
282 kbtree_t(chn) *tree;
283 smem_aux_t *aux;
284
285 kv_init(chain);
286 if (len < opt->min_seed_len) return chain; // if the query is shorter than the seed length, no match
287 tree = kb_init(chn, KB_DEFAULT_SIZE);
288
289 aux = buf? (smem_aux_t*)buf : smem_aux_init();
290 mem_collect_intv(opt, bwt, len, seq, aux);
291 for (i = 0, b = e = l_rep = 0; i < aux->mem.n; ++i) { // compute frac_rep
292 bwtintv_t *p = &aux->mem.a[i];
293 int sb = (p->info>>32), se = (uint32_t)p->info;
294 if (p->x[2] <= opt->max_occ) continue;
295 if (sb > e) l_rep += e - b, b = sb, e = se;
296 else e = e > se? e : se;
297 }
298 l_rep += e - b;
299 for (i = 0; i < aux->mem.n; ++i) {
300 bwtintv_t *p = &aux->mem.a[i];
301 int step, count, slen = (uint32_t)p->info - (p->info>>32); // seed length
302 int64_t k;
303 // if (slen < opt->min_seed_len) continue; // ignore if too short or too repetitive
304 step = p->x[2] > opt->max_occ? p->x[2] / opt->max_occ : 1;
305 for (k = count = 0; k < p->x[2] && count < opt->max_occ; k += step, ++count) {
306 mem_chain_t tmp, *lower, *upper;
307 mem_seed_t s;
308 int rid, to_add = 0;
309 s.rbeg = tmp.pos = bwt_sa(bwt, p->x[0] + k); // this is the base coordinate in the forward-reverse reference
310 s.qbeg = p->info>>32;
311 s.score= s.len = slen;
312 rid = bns_intv2rid(bns, s.rbeg, s.rbeg + s.len);
313 if (rid < 0) continue; // bridging multiple reference sequences or the forward-reverse boundary; TODO: split the seed; don't discard it!!!
314 if (kb_size(tree)) {
315 kb_intervalp(chn, tree, &tmp, &lower, &upper); // find the closest chain
316 if (!lower || !test_and_merge(opt, l_pac, lower, &s, rid)) to_add = 1;
317 } else to_add = 1;
318 if (to_add) { // add the seed as a new chain
319 tmp.n = 1; tmp.m = 4;
320 tmp.seeds = calloc(tmp.m, sizeof(mem_seed_t));
321 tmp.seeds[0] = s;
322 tmp.rid = rid;
323 tmp.is_alt = !!bns->anns[rid].is_alt;
324 kb_putp(chn, tree, &tmp);
325 }
326 }
327 }
328 if (buf == 0) smem_aux_destroy(aux);
329
330 kv_resize(mem_chain_t, chain, kb_size(tree));
331
332 #define traverse_func(p_) (chain.a[chain.n++] = *(p_))
333 __kb_traverse(mem_chain_t, tree, traverse_func);
334 #undef traverse_func
335
336 for (i = 0; i < chain.n; ++i) chain.a[i].frac_rep = (float)l_rep / len;
337 if (bwa_verbose >= 4) printf("* fraction of repetitive seeds: %.3f\n", (float)l_rep / len);
338
339 kb_destroy(chn, tree);
340 return chain;
341 }
342
343 /********************
344 * Filtering chains *
345 ********************/
346
347 #define chn_beg(ch) ((ch).seeds->qbeg)
348 #define chn_end(ch) ((ch).seeds[(ch).n-1].qbeg + (ch).seeds[(ch).n-1].len)
349
350 #define flt_lt(a, b) ((a).w > (b).w)
351 KSORT_INIT(mem_flt, mem_chain_t, flt_lt)
352
353 int mem_chain_flt(const mem_opt_t *opt, int n_chn, mem_chain_t *a)
354 {
355 int i, k;
356 kvec_t(int) chains = {0,0,0}; // this keeps int indices of the non-overlapping chains
357 if (n_chn == 0) return 0; // no need to filter
358 // compute the weight of each chain and drop chains with small weight
359 for (i = k = 0; i < n_chn; ++i) {
360 mem_chain_t *c = &a[i];
361 c->first = -1; c->kept = 0;
362 c->w = mem_chain_weight(c);
363 if (c->w < opt->min_chain_weight) free(c->seeds);
364 else a[k++] = *c;
365 }
366 n_chn = k;
367 ks_introsort(mem_flt, n_chn, a);
368 // pairwise chain comparisons
369 a[0].kept = 3;
370 kv_push(int, chains, 0);
371 for (i = 1; i < n_chn; ++i) {
372 int large_ovlp = 0;
373 for (k = 0; k < chains.n; ++k) {
374 int j = chains.a[k];
375 int b_max = chn_beg(a[j]) > chn_beg(a[i])? chn_beg(a[j]) : chn_beg(a[i]);
376 int e_min = chn_end(a[j]) < chn_end(a[i])? chn_end(a[j]) : chn_end(a[i]);
377 if (e_min > b_max && (!a[j].is_alt || a[i].is_alt)) { // have overlap; don't consider ovlp where the kept chain is ALT while the current chain is primary
378 int li = chn_end(a[i]) - chn_beg(a[i]);
379 int lj = chn_end(a[j]) - chn_beg(a[j]);
380 int min_l = li < lj? li : lj;
381 if (e_min - b_max >= min_l * opt->mask_level && min_l < opt->max_chain_gap) { // significant overlap
382 large_ovlp = 1;
383 if (a[j].first < 0) a[j].first = i; // keep the first shadowed hit s.t. mapq can be more accurate
384 if (a[i].w < a[j].w * opt->drop_ratio && a[j].w - a[i].w >= opt->min_seed_len<<1)
385 break;
386 }
387 }
388 }
389 if (k == chains.n) {
390 kv_push(int, chains, i);
391 a[i].kept = large_ovlp? 2 : 3;
392 }
393 }
394 for (i = 0; i < chains.n; ++i) {
395 mem_chain_t *c = &a[chains.a[i]];
396 if (c->first >= 0) a[c->first].kept = 1;
397 }
398 free(chains.a);
399 for (i = k = 0; i < n_chn; ++i) { // don't extend more than opt->max_chain_extend .kept=1/2 chains
400 if (a[i].kept == 0 || a[i].kept == 3) continue;
401 if (++k >= opt->max_chain_extend) break;
402 }
403 for (; i < n_chn; ++i)
404 if (a[i].kept < 3) a[i].kept = 0;
405 for (i = k = 0; i < n_chn; ++i) { // free discarded chains
406 mem_chain_t *c = &a[i];
407 if (c->kept == 0) free(c->seeds);
408 else a[k++] = a[i];
409 }
410 return k;
411 }
412
413 /******************************
414 * De-overlap single-end hits *
415 ******************************/
416
417 #define alnreg_slt2(a, b) ((a).re < (b).re)
418 KSORT_INIT(mem_ars2, mem_alnreg_t, alnreg_slt2)
419
420 #define alnreg_slt(a, b) ((a).score > (b).score || ((a).score == (b).score && ((a).rb < (b).rb || ((a).rb == (b).rb && (a).qb < (b).qb))))
421 KSORT_INIT(mem_ars, mem_alnreg_t, alnreg_slt)
422
423 #define alnreg_hlt(a, b) ((a).score > (b).score || ((a).score == (b).score && ((a).is_alt < (b).is_alt || ((a).is_alt == (b).is_alt && (a).hash < (b).hash))))
424 KSORT_INIT(mem_ars_hash, mem_alnreg_t, alnreg_hlt)
425
426 #define alnreg_hlt2(a, b) ((a).is_alt < (b).is_alt || ((a).is_alt == (b).is_alt && ((a).score > (b).score || ((a).score == (b).score && (a).hash < (b).hash))))
427 KSORT_INIT(mem_ars_hash2, mem_alnreg_t, alnreg_hlt2)
428
429 #define PATCH_MAX_R_BW 0.05f
430 #define PATCH_MIN_SC_RATIO 0.90f
431
432 int mem_patch_reg(const mem_opt_t *opt, const bntseq_t *bns, const uint8_t *pac, uint8_t *query, const mem_alnreg_t *a, const mem_alnreg_t *b, int *_w)
433 {
434 int w, score, q_s, r_s;
435 double r;
436 if (bns == 0 || pac == 0 || query == 0) return 0;
437 assert(a->rid == b->rid && a->rb <= b->rb);
438 if (a->rb < bns->l_pac && b->rb >= bns->l_pac) return 0; // on different strands
439 if (a->qb >= b->qb || a->qe >= b->qe || a->re >= b->re) return 0; // not colinear
440 w = (a->re - b->rb) - (a->qe - b->qb); // required bandwidth
441 w = w > 0? w : -w; // l = abs(l)
442 r = (double)(a->re - b->rb) / (b->re - a->rb) - (double)(a->qe - b->qb) / (b->qe - a->qb); // relative bandwidth
443 r = r > 0.? r : -r; // r = fabs(r)
444 if (bwa_verbose >= 4)
445 printf("* potential hit merge between [%d,%d)<=>[%ld,%ld) and [%d,%d)<=>[%ld,%ld), @ %s; w=%d, r=%.4g\n",
446 a->qb, a->qe, (long)a->rb, (long)a->re, b->qb, b->qe, (long)b->rb, (long)b->re, bns->anns[a->rid].name, w, r);
447 if (a->re < b->rb || a->qe < b->qb) { // no overlap on query or on ref
448 if (w > opt->w<<1 || r >= PATCH_MAX_R_BW) return 0; // the bandwidth or the relative bandwidth is too large
449 } else if (w > opt->w<<2 || r >= PATCH_MAX_R_BW*2) return 0; // more permissive if overlapping on both ref and query
450 // global alignment
451 w += a->w + b->w;
452 w = w < opt->w<<2? w : opt->w<<2;
453 if (bwa_verbose >= 4) printf("* test potential hit merge with global alignment; w=%d\n", w);
454 bwa_gen_cigar2(opt->mat, opt->o_del, opt->e_del, opt->o_ins, opt->e_ins, w, bns->l_pac, pac, b->qe - a->qb, query + a->qb, a->rb, b->re, &score, 0, 0);
455 q_s = (int)((double)(b->qe - a->qb) / ((b->qe - b->qb) + (a->qe - a->qb)) * (b->score + a->score) + .499); // predicted score from query
456 r_s = (int)((double)(b->re - a->rb) / ((b->re - b->rb) + (a->re - a->rb)) * (b->score + a->score) + .499); // predicted score from ref
457 if (bwa_verbose >= 4) printf("* score=%d;(%d,%d)\n", score, q_s, r_s);
458 if ((double)score / (q_s > r_s? q_s : r_s) < PATCH_MIN_SC_RATIO) return 0;
459 *_w = w;
460 return score;
461 }
462
463 int mem_sort_dedup_patch(const mem_opt_t *opt, const bntseq_t *bns, const uint8_t *pac, uint8_t *query, int n, mem_alnreg_t *a)
464 {
465 int m, i, j;
466 if (n <= 1) return n;
467 ks_introsort(mem_ars2, n, a); // sort by the END position, not START!
468 for (i = 0; i < n; ++i) a[i].n_comp = 1;
469 for (i = 1; i < n; ++i) {
470 mem_alnreg_t *p = &a[i];
471 if (p->rid != a[i-1].rid || p->rb >= a[i-1].re + opt->max_chain_gap) continue; // then no need to go into the loop below
472 for (j = i - 1; j >= 0 && p->rid == a[j].rid && p->rb < a[j].re + opt->max_chain_gap; --j) {
473 mem_alnreg_t *q = &a[j];
474 int64_t or, oq, mr, mq;
475 int score, w;
476 if (q->qe == q->qb) continue; // a[j] has been excluded
477 or = q->re - p->rb; // overlap length on the reference
478 oq = q->qb < p->qb? q->qe - p->qb : p->qe - q->qb; // overlap length on the query
479 mr = q->re - q->rb < p->re - p->rb? q->re - q->rb : p->re - p->rb; // min ref len in alignment
480 mq = q->qe - q->qb < p->qe - p->qb? q->qe - q->qb : p->qe - p->qb; // min qry len in alignment
481 if (or > opt->mask_level_redun * mr && oq > opt->mask_level_redun * mq) { // one of the hits is redundant
482 if (p->score < q->score) {
483 p->qe = p->qb;
484 break;
485 } else q->qe = q->qb;
486 } else if (q->rb < p->rb && (score = mem_patch_reg(opt, bns, pac, query, q, p, &w)) > 0) { // then merge q into p
487 p->n_comp += q->n_comp + 1;
488 p->seedcov = p->seedcov > q->seedcov? p->seedcov : q->seedcov;
489 p->sub = p->sub > q->sub? p->sub : q->sub;
490 p->csub = p->csub > q->csub? p->csub : q->csub;
491 p->qb = q->qb, p->rb = q->rb;
492 p->truesc = p->score = score;
493 p->w = w;
494 q->qb = q->qe;
495 }
496 }
497 }
498 for (i = 0, m = 0; i < n; ++i) // exclude identical hits
499 if (a[i].qe > a[i].qb) {
500 if (m != i) a[m++] = a[i];
501 else ++m;
502 }
503 n = m;
504 ks_introsort(mem_ars, n, a);
505 for (i = 1; i < n; ++i) { // mark identical hits
506 if (a[i].score == a[i-1].score && a[i].rb == a[i-1].rb && a[i].qb == a[i-1].qb)
507 a[i].qe = a[i].qb;
508 }
509 for (i = 1, m = 1; i < n; ++i) // exclude identical hits
510 if (a[i].qe > a[i].qb) {
511 if (m != i) a[m++] = a[i];
512 else ++m;
513 }
514 return m;
515 }
516
517 typedef kvec_t(int) int_v;
518
519 static void mem_mark_primary_se_core(const mem_opt_t *opt, int n, mem_alnreg_t *a, int_v *z)
520 { // similar to the loop in mem_chain_flt()
521 int i, k, tmp;
522 tmp = opt->a + opt->b;
523 tmp = opt->o_del + opt->e_del > tmp? opt->o_del + opt->e_del : tmp;
524 tmp = opt->o_ins + opt->e_ins > tmp? opt->o_ins + opt->e_ins : tmp;
525 z->n = 0;
526 kv_push(int, *z, 0);
527 for (i = 1; i < n; ++i) {
528 for (k = 0; k < z->n; ++k) {
529 int j = z->a[k];
530 int b_max = a[j].qb > a[i].qb? a[j].qb : a[i].qb;
531 int e_min = a[j].qe < a[i].qe? a[j].qe : a[i].qe;
532 if (e_min > b_max) { // have overlap
533 int min_l = a[i].qe - a[i].qb < a[j].qe - a[j].qb? a[i].qe - a[i].qb : a[j].qe - a[j].qb;
534 if (e_min - b_max >= min_l * opt->mask_level) { // significant overlap
535 if (a[j].sub == 0) a[j].sub = a[i].score;
536 if (a[j].score - a[i].score <= tmp && (a[j].is_alt || !a[i].is_alt))
537 ++a[j].sub_n;
538 break;
539 }
540 }
541 }
542 if (k == z->n) kv_push(int, *z, i);
543 else a[i].secondary = z->a[k];
544 }
545 }
546
547 int mem_mark_primary_se(const mem_opt_t *opt, int n, mem_alnreg_t *a, int64_t id)
548 {
549 int i, n_pri;
550 int_v z = {0,0,0};
551 if (n == 0) return 0;
552 for (i = n_pri = 0; i < n; ++i) {
553 a[i].sub = a[i].alt_sc = 0, a[i].secondary = a[i].secondary_all = -1, a[i].hash = hash_64(id+i);
554 if (!a[i].is_alt) ++n_pri;
555 }
556 ks_introsort(mem_ars_hash, n, a);
557 mem_mark_primary_se_core(opt, n, a, &z);
558 for (i = 0; i < n; ++i) {
559 mem_alnreg_t *p = &a[i];
560 p->secondary_all = i; // keep the rank in the first round
561 if (!p->is_alt && p->secondary >= 0 && a[p->secondary].is_alt)
562 p->alt_sc = a[p->secondary].score;
563 }
564 if (n_pri >= 0 && n_pri < n) {
565 kv_resize(int, z, n);
566 if (n_pri > 0) ks_introsort(mem_ars_hash2, n, a);
567 for (i = 0; i < n; ++i) z.a[a[i].secondary_all] = i;
568 for (i = 0; i < n; ++i) {
569 if (a[i].secondary >= 0) {
570 a[i].secondary_all = z.a[a[i].secondary];
571 if (a[i].is_alt) a[i].secondary = INT_MAX;
572 } else a[i].secondary_all = -1;
573 }
574 if (n_pri > 0) { // mark primary for hits to the primary assembly only
575 for (i = 0; i < n_pri; ++i) a[i].sub = 0, a[i].secondary = -1;
576 mem_mark_primary_se_core(opt, n_pri, a, &z);
577 }
578 } else {
579 for (i = 0; i < n; ++i)
580 a[i].secondary_all = a[i].secondary;
581 }
582 free(z.a);
583 return n_pri;
584 }
585
586 /*********************************
587 * Test if a seed is good enough *
588 *********************************/
589
590 #define MEM_SHORT_EXT 50
591 #define MEM_SHORT_LEN 200
592
593 #define MEM_HSP_COEF 1.1f
594 #define MEM_MINSC_COEF 5.5f
595 #define MEM_SEEDSW_COEF 0.05f
596
597 int mem_seed_sw(const mem_opt_t *opt, const bntseq_t *bns, const uint8_t *pac, int l_query, const uint8_t *query, const mem_seed_t *s)
598 {
599 int qb, qe, rid;
600 int64_t rb, re, mid, l_pac = bns->l_pac;
601 uint8_t *rseq = 0;
602 kswr_t x;
603
604 if (s->len >= MEM_SHORT_LEN) return -1; // the seed is longer than the max-extend; no need to do SW
605 qb = s->qbeg, qe = s->qbeg + s->len;
606 rb = s->rbeg, re = s->rbeg + s->len;
607 mid = (rb + re) >> 1;
608 qb -= MEM_SHORT_EXT; qb = qb > 0? qb : 0;
609 qe += MEM_SHORT_EXT; qe = qe < l_query? qe : l_query;
610 rb -= MEM_SHORT_EXT; rb = rb > 0? rb : 0;
611 re += MEM_SHORT_EXT; re = re < l_pac<<1? re : l_pac<<1;
612 if (rb < l_pac && l_pac < re) {
613 if (mid < l_pac) re = l_pac;
614 else rb = l_pac;
615 }
616 if (qe - qb >= MEM_SHORT_LEN || re - rb >= MEM_SHORT_LEN) return -1; // the seed seems good enough; no need to do SW
617
618 rseq = bns_fetch_seq(bns, pac, &rb, mid, &re, &rid);
619 x = ksw_align2(qe - qb, (uint8_t*)query + qb, re - rb, rseq, 5, opt->mat, opt->o_del, opt->e_del, opt->o_ins, opt->e_ins, KSW_XSTART, 0);
620 free(rseq);
621 return x.score;
622 }
623
624 void mem_flt_chained_seeds(const mem_opt_t *opt, const bntseq_t *bns, const uint8_t *pac, int l_query, const uint8_t *query, int n_chn, mem_chain_t *a)
625 {
626 double min_l = opt->min_chain_weight? MEM_HSP_COEF * opt->min_chain_weight : MEM_MINSC_COEF * log(l_query);
627 int i, j, k, min_HSP_score = (int)(opt->a * min_l + .499);
628 if (min_l > MEM_SEEDSW_COEF * l_query) return; // don't run the following for short reads
629 for (i = 0; i < n_chn; ++i) {
630 mem_chain_t *c = &a[i];
631 for (j = k = 0; j < c->n; ++j) {
632 mem_seed_t *s = &c->seeds[j];
633 s->score = mem_seed_sw(opt, bns, pac, l_query, query, s);
634 if (s->score < 0 || s->score >= min_HSP_score) {
635 s->score = s->score < 0? s->len * opt->a : s->score;
636 c->seeds[k++] = *s;
637 }
638 }
639 c->n = k;
640 }
641 }
642
643 /****************************************
644 * Construct the alignment from a chain *
645 ****************************************/
646
647 static inline int cal_max_gap(const mem_opt_t *opt, int qlen)
648 {
649 int l_del = (int)((double)(qlen * opt->a - opt->o_del) / opt->e_del + 1.);
650 int l_ins = (int)((double)(qlen * opt->a - opt->o_ins) / opt->e_ins + 1.);
651 int l = l_del > l_ins? l_del : l_ins;
652 l = l > 1? l : 1;
653 return l < opt->w<<1? l : opt->w<<1;
654 }
655
656 #define MAX_BAND_TRY 2
657
658 void mem_chain2aln(const mem_opt_t *opt, const bntseq_t *bns, const uint8_t *pac, int l_query, const uint8_t *query, const mem_chain_t *c, mem_alnreg_v *av)
659 {
660 int i, k, rid, max_off[2], aw[2]; // aw: actual bandwidth used in extension
661 int64_t l_pac = bns->l_pac, rmax[2], tmp, max = 0;
662 const mem_seed_t *s;
663 uint8_t *rseq = 0;
664 uint64_t *srt;
665
666 if (c->n == 0) return;
667 // get the max possible span
668 rmax[0] = l_pac<<1; rmax[1] = 0;
669 for (i = 0; i < c->n; ++i) {
670 int64_t b, e;
671 const mem_seed_t *t = &c->seeds[i];
672 b = t->rbeg - (t->qbeg + cal_max_gap(opt, t->qbeg));
673 e = t->rbeg + t->len + ((l_query - t->qbeg - t->len) + cal_max_gap(opt, l_query - t->qbeg - t->len));
674 rmax[0] = rmax[0] < b? rmax[0] : b;
675 rmax[1] = rmax[1] > e? rmax[1] : e;
676 if (t->len > max) max = t->len;
677 }
678 rmax[0] = rmax[0] > 0? rmax[0] : 0;
679 rmax[1] = rmax[1] < l_pac<<1? rmax[1] : l_pac<<1;
680 if (rmax[0] < l_pac && l_pac < rmax[1]) { // crossing the forward-reverse boundary; then choose one side
681 if (c->seeds[0].rbeg < l_pac) rmax[1] = l_pac; // this works because all seeds are guaranteed to be on the same strand
682 else rmax[0] = l_pac;
683 }
684 // retrieve the reference sequence
685 rseq = bns_fetch_seq(bns, pac, &rmax[0], c->seeds[0].rbeg, &rmax[1], &rid);
686 assert(c->rid == rid);
687
688 srt = malloc(c->n * 8);
689 for (i = 0; i < c->n; ++i)
690 srt[i] = (uint64_t)c->seeds[i].score<<32 | i;
691 ks_introsort_64(c->n, srt);
692
693 for (k = c->n - 1; k >= 0; --k) {
694 mem_alnreg_t *a;
695 s = &c->seeds[(uint32_t)srt[k]];
696
697 for (i = 0; i < av->n; ++i) { // test whether extension has been made before
698 mem_alnreg_t *p = &av->a[i];
699 int64_t rd;
700 int qd, w, max_gap;
701 if (s->rbeg < p->rb || s->rbeg + s->len > p->re || s->qbeg < p->qb || s->qbeg + s->len > p->qe) continue; // not fully contained
702 if (s->len - p->seedlen0 > .1 * l_query) continue; // this seed may give a better alignment
703 // qd: distance ahead of the seed on query; rd: on reference
704 qd = s->qbeg - p->qb; rd = s->rbeg - p->rb;
705 max_gap = cal_max_gap(opt, qd < rd? qd : rd); // the maximal gap allowed in regions ahead of the seed
706 w = max_gap < p->w? max_gap : p->w; // bounded by the band width
707 if (qd - rd < w && rd - qd < w) break; // the seed is "around" a previous hit
708 // similar to the previous four lines, but this time we look at the region behind
709 qd = p->qe - (s->qbeg + s->len); rd = p->re - (s->rbeg + s->len);
710 max_gap = cal_max_gap(opt, qd < rd? qd : rd);
711 w = max_gap < p->w? max_gap : p->w;
712 if (qd - rd < w && rd - qd < w) break;
713 }
714 if (i < av->n) { // the seed is (almost) contained in an existing alignment; further testing is needed to confirm it is not leading to a different aln
715 if (bwa_verbose >= 4)
716 printf("** Seed(%d) [%ld;%ld,%ld] is almost contained in an existing alignment [%d,%d) <=> [%ld,%ld)\n",
717 k, (long)s->len, (long)s->qbeg, (long)s->rbeg, av->a[i].qb, av->a[i].qe, (long)av->a[i].rb, (long)av->a[i].re);
718 for (i = k + 1; i < c->n; ++i) { // check overlapping seeds in the same chain
719 const mem_seed_t *t;
720 if (srt[i] == 0) continue;
721 t = &c->seeds[(uint32_t)srt[i]];
722 if (t->len < s->len * .95) continue; // only check overlapping if t is long enough; TODO: more efficient by early stopping
723 if (s->qbeg <= t->qbeg && s->qbeg + s->len - t->qbeg >= s->len>>2 && t->qbeg - s->qbeg != t->rbeg - s->rbeg) break;
724 if (t->qbeg <= s->qbeg && t->qbeg + t->len - s->qbeg >= s->len>>2 && s->qbeg - t->qbeg != s->rbeg - t->rbeg) break;
725 }
726 if (i == c->n) { // no overlapping seeds; then skip extension
727 srt[k] = 0; // mark that seed extension has not been performed
728 continue;
729 }
730 if (bwa_verbose >= 4)
731 printf("** Seed(%d) might lead to a different alignment even though it is contained. Extension will be performed.\n", k);
732 }
733
734 a = kv_pushp(mem_alnreg_t, *av);
735 memset(a, 0, sizeof(mem_alnreg_t));
736 a->w = aw[0] = aw[1] = opt->w;
737 a->score = a->truesc = -1;
738 a->rid = c->rid;
739
740 if (bwa_verbose >= 4) err_printf("** ---> Extending from seed(%d) [%ld;%ld,%ld] @ %s <---\n", k, (long)s->len, (long)s->qbeg, (long)s->rbeg, bns->anns[c->rid].name);
741 if (s->qbeg) { // left extension
742 uint8_t *rs, *qs;
743 int qle, tle, gtle, gscore;
744 qs = malloc(s->qbeg);
745 for (i = 0; i < s->qbeg; ++i) qs[i] = query[s->qbeg - 1 - i];
746 tmp = s->rbeg - rmax[0];
747 rs = malloc(tmp);
748 for (i = 0; i < tmp; ++i) rs[i] = rseq[tmp - 1 - i];
749 for (i = 0; i < MAX_BAND_TRY; ++i) {
750 int prev = a->score;
751 aw[0] = opt->w << i;
752 if (bwa_verbose >= 4) {
753 int j;
754 printf("*** Left ref: "); for (j = 0; j < tmp; ++j) putchar("ACGTN"[(int)rs[j]]); putchar('\n');
755 printf("*** Left query: "); for (j = 0; j < s->qbeg; ++j) putchar("ACGTN"[(int)qs[j]]); putchar('\n');
756 }
757 a->score = ksw_extend2(s->qbeg, qs, tmp, rs, 5, opt->mat, opt->o_del, opt->e_del, opt->o_ins, opt->e_ins, aw[0], opt->pen_clip5, opt->zdrop, s->len * opt->a, &qle, &tle, &gtle, &gscore, &max_off[0]);
758 if (bwa_verbose >= 4) { printf("*** Left extension: prev_score=%d; score=%d; bandwidth=%d; max_off_diagonal_dist=%d\n", prev, a->score, aw[0], max_off[0]); fflush(stdout); }
759 if (a->score == prev || max_off[0] < (aw[0]>>1) + (aw[0]>>2)) break;
760 }
761 // check whether we prefer to reach the end of the query
762 if (gscore <= 0 || gscore <= a->score - opt->pen_clip5) { // local extension
763 a->qb = s->qbeg - qle, a->rb = s->rbeg - tle;
764 a->truesc = a->score;
765 } else { // to-end extension
766 a->qb = 0, a->rb = s->rbeg - gtle;
767 a->truesc = gscore;
768 }
769 free(qs); free(rs);
770 } else a->score = a->truesc = s->len * opt->a, a->qb = 0, a->rb = s->rbeg;
771
772 if (s->qbeg + s->len != l_query) { // right extension
773 int qle, tle, qe, re, gtle, gscore, sc0 = a->score;
774 qe = s->qbeg + s->len;
775 re = s->rbeg + s->len - rmax[0];
776 assert(re >= 0);
777 for (i = 0; i < MAX_BAND_TRY; ++i) {
778 int prev = a->score;
779 aw[1] = opt->w << i;
780 if (bwa_verbose >= 4) {
781 int j;
782 printf("*** Right ref: "); for (j = 0; j < rmax[1] - rmax[0] - re; ++j) putchar("ACGTN"[(int)rseq[re+j]]); putchar('\n');
783 printf("*** Right query: "); for (j = 0; j < l_query - qe; ++j) putchar("ACGTN"[(int)query[qe+j]]); putchar('\n');
784 }
785 a->score = ksw_extend2(l_query - qe, query + qe, rmax[1] - rmax[0] - re, rseq + re, 5, opt->mat, opt->o_del, opt->e_del, opt->o_ins, opt->e_ins, aw[1], opt->pen_clip3, opt->zdrop, sc0, &qle, &tle, &gtle, &gscore, &max_off[1]);
786 if (bwa_verbose >= 4) { printf("*** Right extension: prev_score=%d; score=%d; bandwidth=%d; max_off_diagonal_dist=%d\n", prev, a->score, aw[1], max_off[1]); fflush(stdout); }
787 if (a->score == prev || max_off[1] < (aw[1]>>1) + (aw[1]>>2)) break;
788 }
789 // similar to the above
790 if (gscore <= 0 || gscore <= a->score - opt->pen_clip3) { // local extension
791 a->qe = qe + qle, a->re = rmax[0] + re + tle;
792 a->truesc += a->score - sc0;
793 } else { // to-end extension
794 a->qe = l_query, a->re = rmax[0] + re + gtle;
795 a->truesc += gscore - sc0;
796 }
797 } else a->qe = l_query, a->re = s->rbeg + s->len;
798 if (bwa_verbose >= 4) printf("*** Added alignment region: [%d,%d) <=> [%ld,%ld); score=%d; {left,right}_bandwidth={%d,%d}\n", a->qb, a->qe, (long)a->rb, (long)a->re, a->score, aw[0], aw[1]);
799
800 // compute seedcov
801 for (i = 0, a->seedcov = 0; i < c->n; ++i) {
802 const mem_seed_t *t = &c->seeds[i];
803 if (t->qbeg >= a->qb && t->qbeg + t->len <= a->qe && t->rbeg >= a->rb && t->rbeg + t->len <= a->re) // seed fully contained
804 a->seedcov += t->len; // this is not very accurate, but for approx. mapQ, this is good enough
805 }
806 a->w = aw[0] > aw[1]? aw[0] : aw[1];
807 a->seedlen0 = s->len;
808
809 a->frac_rep = c->frac_rep;
810 }
811 free(srt); free(rseq);
812 }
813
814 /*****************************
815 * Basic hit->SAM conversion *
816 *****************************/
817
818 static inline int infer_bw(int l1, int l2, int score, int a, int q, int r)
819 {
820 int w;
821 if (l1 == l2 && l1 * a - score < (q + r - a)<<1) return 0; // to get equal alignment length, we need at least two gaps
822 w = ((double)((l1 < l2? l1 : l2) * a - score - q) / r + 2.);
823 if (w < abs(l1 - l2)) w = abs(l1 - l2);
824 return w;
825 }
826
827 static inline int get_rlen(int n_cigar, const uint32_t *cigar)
828 {
829 int k, l;
830 for (k = l = 0; k < n_cigar; ++k) {
831 int op = cigar[k]&0xf;
832 if (op == 0 || op == 2)
833 l += cigar[k]>>4;
834 }
835 return l;
836 }
837
838 void mem_fmt_sam(const mem_opt_t *opt, const bntseq_t *bns, kstring_t *str, bseq1_t *s, int n, const mem_aln_t *list, int which, const mem_aln_t *p, const mem_aln_t *m) {
839 // print up to CIGAR
840 int i, l_name = strlen(s->name);
841 ks_resize(str, str->l + s->l_seq + l_name + (s->qual? s->l_seq : 0) + 20);
842 kputsn(s->name, l_name, str); kputc('\t', str); // QNAME
843 kputw((p->flag&0xffff) | (p->flag&0x10000? 0x100 : 0), str); kputc('\t', str); // FLAG
844 if (p->rid >= 0) { // with coordinate
845 kputs(bns->anns[p->rid].name, str); kputc('\t', str); // RNAME
846 kputl(p->pos + 1, str); kputc('\t', str); // POS
847 kputw(p->mapq, str); kputc('\t', str); // MAPQ
848 if (p->n_cigar) { // aligned
849 for (i = 0; i < p->n_cigar; ++i) {
850 int c = p->cigar[i]&0xf;
851 if (!(opt->flag&MEM_F_SOFTCLIP) && !p->is_alt && (c == 3 || c == 4))
852 c = which? 4 : 3; // use hard clipping for supplementary alignments
853 kputw(p->cigar[i]>>4, str); kputc("MIDSH"[c], str);
854 }
855 } else kputc('*', str); // having a coordinate but unaligned (e.g. when copy_mate is true)
856 } else kputsn("*\t0\t0\t*", 7, str); // without coordinate
857 kputc('\t', str);
858
859 // print the mate position if applicable
860 if (m && m->rid >= 0) {
861 if (p->rid == m->rid) kputc('=', str);
862 else kputs(bns->anns[m->rid].name, str);
863 kputc('\t', str);
864 kputl(m->pos + 1, str); kputc('\t', str);
865 if (p->rid == m->rid) {
866 int64_t p0 = p->pos + (p->is_rev? get_rlen(p->n_cigar, p->cigar) - 1 : 0);
867 int64_t p1 = m->pos + (m->is_rev? get_rlen(m->n_cigar, m->cigar) - 1 : 0);
868 if (m->n_cigar == 0 || p->n_cigar == 0) kputc('0', str);
869 else kputl(-(p0 - p1 + (p0 > p1? 1 : p0 < p1? -1 : 0)), str);
870 } else kputc('0', str);
871 } else kputsn("*\t0\t0", 5, str);
872 kputc('\t', str);
873
874 // print SEQ and QUAL
875 if (p->flag & 0x100) { // for secondary alignments, don't write SEQ and QUAL
876 kputsn("*\t*", 3, str);
877 } else if (!p->is_rev) { // the forward strand
878 int i, qb = 0, qe = s->l_seq;
879 if (p->n_cigar && which && !(opt->flag&MEM_F_SOFTCLIP) && !p->is_alt) { // have cigar && not the primary alignment && not softclip all
880 if ((p->cigar[0]&0xf) == 4 || (p->cigar[0]&0xf) == 3) qb += p->cigar[0]>>4;
881 if ((p->cigar[p->n_cigar-1]&0xf) == 4 || (p->cigar[p->n_cigar-1]&0xf) == 3) qe -= p->cigar[p->n_cigar-1]>>4;
882 }
883 ks_resize(str, str->l + (qe - qb) + 1);
884 for (i = qb; i < qe; ++i) str->s[str->l++] = "ACGTN"[(int)s->seq[i]];
885 kputc('\t', str);
886 if (s->qual) { // printf qual
887 ks_resize(str, str->l + (qe - qb) + 1);
888 for (i = qb; i < qe; ++i) str->s[str->l++] = s->qual[i];
889 str->s[str->l] = 0;
890 } else kputc('*', str);
891 } else { // the reverse strand
892 int i, qb = 0, qe = s->l_seq;
893 if (p->n_cigar && which && !(opt->flag&MEM_F_SOFTCLIP) && !p->is_alt) {
894 if ((p->cigar[0]&0xf) == 4 || (p->cigar[0]&0xf) == 3) qe -= p->cigar[0]>>4;
895 if ((p->cigar[p->n_cigar-1]&0xf) == 4 || (p->cigar[p->n_cigar-1]&0xf) == 3) qb += p->cigar[p->n_cigar-1]>>4;
896 }
897 ks_resize(str, str->l + (qe - qb) + 1);
898 for (i = qe-1; i >= qb; --i) str->s[str->l++] = "TGCAN"[(int)s->seq[i]];
899 kputc('\t', str);
900 if (s->qual) { // printf qual
901 ks_resize(str, str->l + (qe - qb) + 1);
902 for (i = qe-1; i >= qb; --i) str->s[str->l++] = s->qual[i];
903 str->s[str->l] = 0;
904 } else kputc('*', str);
905 }
906
907 // print optional tags
908 if (p->n_cigar) {
909 kputsn("\tNM:i:", 6, str); kputw(p->NM, str);
910 kputsn("\tMD:Z:", 6, str); kputs((char*)(p->cigar + p->n_cigar), str);
911 }
912 if (m) { kputsn("\tMQ:i:", 6, str); kputw(m->mapq, str);}
913 if (p->score >= 0) { kputsn("\tAS:i:", 6, str); kputw(p->score, str); }
914 if (p->sub >= 0) { kputsn("\tXS:i:", 6, str); kputw(p->sub, str); }
915 if (bwa_rg_id[0]) { kputsn("\tRG:Z:", 6, str); kputs(bwa_rg_id, str); }
916 if (!(p->flag & 0x100)) { // not multi-hit
917 for (i = 0; i < n; ++i)
918 if (i != which && !(list[i].flag&0x100)) break;
919 if (i < n) { // there are other primary hits; output them
920 kputsn("\tSA:Z:", 6, str);
921 for (i = 0; i < n; ++i) {
922 const mem_aln_t *r = &list[i];
923 int k;
924 if (i == which || (r->flag&0x100)) continue; // proceed if: 1) different from the current; 2) not shadowed multi hit
925 kputs(bns->anns[r->rid].name, str); kputc(',', str);
926 kputl(r->pos+1, str); kputc(',', str);
927 kputc("+-"[r->is_rev], str); kputc(',', str);
928 for (k = 0; k < r->n_cigar; ++k) {
929 kputw(r->cigar[k]>>4, str); kputc("MIDSH"[r->cigar[k]&0xf], str);
930 }
931 kputc(',', str); kputw(r->mapq, str);
932 kputc(',', str); kputw(r->NM, str);
933 kputc(';', str);
934 }
935 }
936 if (p->alt_sc > 0)
937 ksprintf(str, "\tpa:f:%.3f", (double)p->score / p->alt_sc);
938 }
939 if (p->XA) {
940 kputsn((opt->flag&MEM_F_XB)? "\tXB:Z:" : "\tXA:Z:", 6, str);
941 kputs(p->XA, str);
942 }
943 if (s->comment) { kputc('\t', str); kputs(s->comment, str); }
944 if ((opt->flag&MEM_F_REF_HDR) && p->rid >= 0 && bns->anns[p->rid].anno != 0 && bns->anns[p->rid].anno[0] != 0) {
945 int tmp;
946 kputsn("\tXR:Z:", 6, str);
947 tmp = str->l;
948 kputs(bns->anns[p->rid].anno, str);
949 for (i = tmp; i < str->l; ++i) // replace TAB in the comment to SPACE
950 if (str->s[i] == '\t') str->s[i] = ' ';
951 }
952 kputc('\n', str);
953 }
954
955 void (*mem_fmt_fnc)(const mem_opt_t*, const bntseq_t*, kstring_t*, bseq1_t*, int, const mem_aln_t*, int, const mem_aln_t*, const mem_aln_t*) = &mem_fmt_sam;
956
957 void mem_aln2sam(const mem_opt_t *opt, const bntseq_t *bns, kstring_t *str, bseq1_t *s, int n, const mem_aln_t *list, int which, const mem_aln_t *m_)
958 {
959 mem_aln_t ptmp = list[which], *p = &ptmp, mtmp, *m = 0; // make a copy of the alignment to convert
960
961 if (m_) mtmp = *m_, m = &mtmp;
962 // set flag
963 p->flag |= m? 0x1 : 0; // is paired in sequencing
964 p->flag |= p->rid < 0? 0x4 : 0; // is mapped
965 p->flag |= m && m->rid < 0? 0x8 : 0; // is mate mapped
966 if (p->rid < 0 && m && m->rid >= 0) // copy mate to alignment
967 p->rid = m->rid, p->pos = m->pos, p->is_rev = m->is_rev, p->n_cigar = 0;
968 if (m && m->rid < 0 && p->rid >= 0) // copy alignment to mate
969 m->rid = p->rid, m->pos = p->pos, m->is_rev = p->is_rev, m->n_cigar = 0;
970 p->flag |= p->is_rev? 0x10 : 0; // is on the reverse strand
971 p->flag |= m && m->is_rev? 0x20 : 0; // is mate on the reverse strand
972
973 (*mem_fmt_fnc)(opt, bns, str, s, n, list, which, p, m);
974 }
975
976 /************************
977 * Integrated interface *
978 ************************/
979
980 int mem_approx_mapq_se(const mem_opt_t *opt, const mem_alnreg_t *a)
981 {
982 int mapq, l, sub = a->sub? a->sub : opt->min_seed_len * opt->a;
983 double identity;
984 sub = a->csub > sub? a->csub : sub;
985 if (sub >= a->score) return 0;
986 l = a->qe - a->qb > a->re - a->rb? a->qe - a->qb : a->re - a->rb;
987 identity = 1. - (double)(l * opt->a - a->score) / (opt->a + opt->b) / l;
988 if (a->score == 0) {
989 mapq = 0;
990 } else if (opt->mapQ_coef_len > 0) {
991 double tmp;
992 tmp = l < opt->mapQ_coef_len? 1. : opt->mapQ_coef_fac / log(l);
993 tmp *= identity * identity;
994 mapq = (int)(6.02 * (a->score - sub) / opt->a * tmp * tmp + .499);
995 } else {
996 mapq = (int)(MEM_MAPQ_COEF * (1. - (double)sub / a->score) * log(a->seedcov) + .499);
997 mapq = identity < 0.95? (int)(mapq * identity * identity + .499) : mapq;
998 }
999 if (a->sub_n > 0) mapq -= (int)(4.343 * log(a->sub_n+1) + .499);
1000 if (mapq > 60) mapq = 60;
1001 if (mapq < 0) mapq = 0;
1002 mapq = (int)(mapq * (1. - a->frac_rep) + .499);
1003 return mapq;
1004 }
1005
1006 void mem_reorder_primary5(int T, mem_alnreg_v *a)
1007 {
1008 int k, n_pri = 0, left_st = INT_MAX, left_k = -1;
1009 mem_alnreg_t t;
1010 for (k = 0; k < a->n; ++k)
1011 if (a->a[k].secondary < 0 && !a->a[k].is_alt && a->a[k].score >= T) ++n_pri;
1012 if (n_pri <= 1) return; // only one alignment
1013 for (k = 0; k < a->n; ++k) {
1014 mem_alnreg_t *p = &a->a[k];
1015 if (p->secondary >= 0 || p->is_alt || p->score < T) continue;
1016 if (p->qb < left_st) left_st = p->qb, left_k = k;
1017 }
1018 assert(a->a[0].secondary < 0);
1019 if (left_k == 0) return; // no need to reorder
1020 t = a->a[0], a->a[0] = a->a[left_k], a->a[left_k] = t;
1021 for (k = 1; k < a->n; ++k) { // update secondary and secondary_all
1022 mem_alnreg_t *p = &a->a[k];
1023 if (p->secondary == 0) p->secondary = left_k;
1024 else if (p->secondary == left_k) p->secondary = 0;
1025 if (p->secondary_all == 0) p->secondary_all = left_k;
1026 else if (p->secondary_all == left_k) p->secondary_all = 0;
1027 }
1028 }
1029
1030 // TODO (future plan): group hits into a uint64_t[] array. This will be cleaner and more flexible
1031 void mem_reg2sam(const mem_opt_t *opt, const bntseq_t *bns, const uint8_t *pac, bseq1_t *s, mem_alnreg_v *a, int extra_flag, const mem_aln_t *m)
1032 {
1033 extern char **mem_gen_alt(const mem_opt_t *opt, const bntseq_t *bns, const uint8_t *pac, mem_alnreg_v *a, int l_query, const char *query);
1034 kstring_t str;
1035 kvec_t(mem_aln_t) aa;
1036 int k, l;
1037 char **XA = 0;
1038
1039 if (!(opt->flag & MEM_F_ALL))
1040 XA = mem_gen_alt(opt, bns, pac, a, s->l_seq, s->seq);
1041 kv_init(aa);
1042 str.l = str.m = 0; str.s = 0;
1043 for (k = l = 0; k < a->n; ++k) {
1044 mem_alnreg_t *p = &a->a[k];
1045 mem_aln_t *q;
1046 if (p->score < opt->T) continue;
1047 if (p->secondary >= 0 && (p->is_alt || !(opt->flag&MEM_F_ALL))) continue;
1048 if (p->secondary >= 0 && p->secondary < INT_MAX && p->score < a->a[p->secondary].score * opt->drop_ratio) continue;
1049 q = kv_pushp(mem_aln_t, aa);
1050 *q = mem_reg2aln(opt, bns, pac, s->l_seq, s->seq, p);
1051 assert(q->rid >= 0); // this should not happen with the new code
1052 q->XA = XA? XA[k] : 0;
1053 q->flag |= extra_flag; // flag secondary
1054 if (p->secondary >= 0) q->sub = -1; // don't output sub-optimal score
1055 if (l && p->secondary < 0) // if supplementary
1056 q->flag |= (opt->flag&MEM_F_NO_MULTI)? 0x10000 : 0x800;
1057 if (!(opt->flag & MEM_F_KEEP_SUPP_MAPQ) && l && !p->is_alt && q->mapq > aa.a[0].mapq)
1058 q->mapq = aa.a[0].mapq; // lower mapq for supplementary mappings, unless -5 or -q is applied
1059 ++l;
1060 }
1061 if (aa.n == 0) { // no alignments good enough; then write an unaligned record
1062 mem_aln_t t;
1063 t = mem_reg2aln(opt, bns, pac, s->l_seq, s->seq, 0);
1064 t.flag |= extra_flag;
1065 mem_aln2sam(opt, bns, &str, s, 1, &t, 0, m);
1066 } else {
1067 for (k = 0; k < aa.n; ++k)
1068 mem_aln2sam(opt, bns, &str, s, aa.n, aa.a, k, m);
1069 for (k = 0; k < aa.n; ++k) free(aa.a[k].cigar);
1070 free(aa.a);
1071 }
1072 s->sam = str.s;
1073 if (XA) {
1074 for (k = 0; k < a->n; ++k) free(XA[k]);
1075 free(XA);
1076 }
1077 }
1078
1079 mem_alnreg_v mem_align1_core(const mem_opt_t *opt, const bwt_t *bwt, const bntseq_t *bns, const uint8_t *pac, int l_seq, char *seq, void *buf)
1080 {
1081 int i;
1082 mem_chain_v chn;
1083 mem_alnreg_v regs;
1084
1085 for (i = 0; i < l_seq; ++i) // convert to 2-bit encoding if we have not done so
1086 seq[i] = seq[i] < 4? seq[i] : nst_nt4_table[(int)seq[i]];
1087
1088 chn = mem_chain(opt, bwt, bns, l_seq, (uint8_t*)seq, buf);
1089 chn.n = mem_chain_flt(opt, chn.n, chn.a);
1090 mem_flt_chained_seeds(opt, bns, pac, l_seq, (uint8_t*)seq, chn.n, chn.a);
1091 if (bwa_verbose >= 4) mem_print_chain(bns, &chn);
1092
1093 kv_init(regs);
1094 for (i = 0; i < chn.n; ++i) {
1095 mem_chain_t *p = &chn.a[i];
1096 if (bwa_verbose >= 4) err_printf("* ---> Processing chain(%d) <---\n", i);
1097 mem_chain2aln(opt, bns, pac, l_seq, (uint8_t*)seq, p, &regs);
1098 free(chn.a[i].seeds);
1099 }
1100 free(chn.a);
1101 regs.n = mem_sort_dedup_patch(opt, bns, pac, (uint8_t*)seq, regs.n, regs.a);
1102 if (bwa_verbose >= 4) {
1103 err_printf("* %ld chains remain after removing duplicated chains\n", regs.n);
1104 for (i = 0; i < regs.n; ++i) {
1105 mem_alnreg_t *p = &regs.a[i];
1106 printf("** %d, [%d,%d) <=> [%ld,%ld)\n", p->score, p->qb, p->qe, (long)p->rb, (long)p->re);
1107 }
1108 }
1109 for (i = 0; i < regs.n; ++i) {
1110 mem_alnreg_t *p = &regs.a[i];
1111 if (p->rid >= 0 && bns->anns[p->rid].is_alt)
1112 p->is_alt = 1;
1113 }
1114 return regs;
1115 }
1116
1117 mem_aln_t mem_reg2aln(const mem_opt_t *opt, const bntseq_t *bns, const uint8_t *pac, int l_query, const char *query_, const mem_alnreg_t *ar)
1118 {
1119 mem_aln_t a;
1120 int i, w2, tmp, qb, qe, NM, score, is_rev, last_sc = -(1<<30), l_MD;
1121 int64_t pos, rb, re;
1122 uint8_t *query;
1123
1124 memset(&a, 0, sizeof(mem_aln_t));
1125 if (ar == 0 || ar->rb < 0 || ar->re < 0) { // generate an unmapped record
1126 a.rid = -1; a.pos = -1; a.flag |= 0x4;
1127 return a;
1128 }
1129 qb = ar->qb, qe = ar->qe;
1130 rb = ar->rb, re = ar->re;
1131 query = malloc(l_query);
1132 for (i = 0; i < l_query; ++i) // convert to the nt4 encoding
1133 query[i] = query_[i] < 5? query_[i] : nst_nt4_table[(int)query_[i]];
1134 a.mapq = ar->secondary < 0? mem_approx_mapq_se(opt, ar) : 0;
1135 if (ar->secondary >= 0) a.flag |= 0x100; // secondary alignment
1136 tmp = infer_bw(qe - qb, re - rb, ar->truesc, opt->a, opt->o_del, opt->e_del);
1137 w2 = infer_bw(qe - qb, re - rb, ar->truesc, opt->a, opt->o_ins, opt->e_ins);
1138 w2 = w2 > tmp? w2 : tmp;
1139 if (bwa_verbose >= 4) printf("* Band width: inferred=%d, cmd_opt=%d, alnreg=%d\n", w2, opt->w, ar->w);
1140 if (w2 > opt->w) w2 = w2 < ar->w? w2 : ar->w;
1141 i = 0; a.cigar = 0;
1142 do {
1143 free(a.cigar);
1144 w2 = w2 < opt->w<<2? w2 : opt->w<<2;
1145 a.cigar = bwa_gen_cigar2(opt->mat, opt->o_del, opt->e_del, opt->o_ins, opt->e_ins, w2, bns->l_pac, pac, qe - qb, (uint8_t*)&query[qb], rb, re, &score, &a.n_cigar, &NM);
1146 if (bwa_verbose >= 4) printf("* Final alignment: w2=%d, global_sc=%d, local_sc=%d\n", w2, score, ar->truesc);
1147 if (score == last_sc || w2 == opt->w<<2) break; // it is possible that global alignment and local alignment give different scores
1148 last_sc = score;
1149 w2 <<= 1;
1150 } while (++i < 3 && score < ar->truesc - opt->a);
1151 l_MD = strlen((char*)(a.cigar + a.n_cigar)) + 1;
1152 a.NM = NM;
1153 pos = bns_depos(bns, rb < bns->l_pac? rb : re - 1, &is_rev);
1154 a.is_rev = is_rev;
1155 if (a.n_cigar > 0) { // squeeze out leading or trailing deletions
1156 if ((a.cigar[0]&0xf) == 2) {
1157 pos += a.cigar[0]>>4;
1158 --a.n_cigar;
1159 memmove(a.cigar, a.cigar + 1, a.n_cigar * 4 + l_MD);
1160 } else if ((a.cigar[a.n_cigar-1]&0xf) == 2) {
1161 --a.n_cigar;
1162 memmove(a.cigar + a.n_cigar, a.cigar + a.n_cigar + 1, l_MD); // MD needs to be moved accordingly
1163 }
1164 }
1165 if (qb != 0 || qe != l_query) { // add clipping to CIGAR
1166 int clip5, clip3;
1167 clip5 = is_rev? l_query - qe : qb;
1168 clip3 = is_rev? qb : l_query - qe;
1169 a.cigar = realloc(a.cigar, 4 * (a.n_cigar + 2) + l_MD);
1170 if (clip5) {
1171 memmove(a.cigar+1, a.cigar, a.n_cigar * 4 + l_MD); // make room for 5'-end clipping
1172 a.cigar[0] = clip5<<4 | 3;
1173 ++a.n_cigar;
1174 }
1175 if (clip3) {
1176 memmove(a.cigar + a.n_cigar + 1, a.cigar + a.n_cigar, l_MD); // make room for 3'-end clipping
1177 a.cigar[a.n_cigar++] = clip3<<4 | 3;
1178 }
1179 }
1180 a.rid = bns_pos2rid(bns, pos);
1181 assert(a.rid == ar->rid);
1182 a.pos = pos - bns->anns[a.rid].offset;
1183 a.score = ar->score; a.sub = ar->sub > ar->csub? ar->sub : ar->csub;
1184 a.is_alt = ar->is_alt; a.alt_sc = ar->alt_sc;
1185 free(query);
1186 return a;
1187 }
1188
1189 typedef struct {
1190 const mem_opt_t *opt;
1191 const bwt_t *bwt;
1192 const bntseq_t *bns;
1193 const uint8_t *pac;
1194 const mem_pestat_t *pes;
1195 smem_aux_t **aux;
1196 bseq1_t *seqs;
1197 mem_alnreg_v *regs;
1198 int64_t n_processed;
1199 } worker_t;
1200
1201 static void worker1(void *data, long i, int tid)
1202 {
1203 worker_t *w = (worker_t*)data;
1204 if (!(w->opt->flag&MEM_F_PE)) {
1205 if (bwa_verbose >= 4) printf("=====> Processing read '%s' <=====\n", w->seqs[i].name);
1206 w->regs[i] = mem_align1_core(w->opt, w->bwt, w->bns, w->pac, w->seqs[i].l_seq, w->seqs[i].seq, w->aux[tid]);
1207 } else {
1208 if (bwa_verbose >= 4) printf("=====> Processing read '%s'/1 <=====\n", w->seqs[i<<1|0].name);
1209 w->regs[i<<1|0] = mem_align1_core(w->opt, w->bwt, w->bns, w->pac, w->seqs[i<<1|0].l_seq, w->seqs[i<<1|0].seq, w->aux[tid]);
1210 if (bwa_verbose >= 4) printf("=====> Processing read '%s'/2 <=====\n", w->seqs[i<<1|1].name);
1211 w->regs[i<<1|1] = mem_align1_core(w->opt, w->bwt, w->bns, w->pac, w->seqs[i<<1|1].l_seq, w->seqs[i<<1|1].seq, w->aux[tid]);
1212 }
1213 }
1214
1215 static void worker2(void *data, long i, int tid)
1216 {
1217 extern int mem_sam_pe(const mem_opt_t *opt, const bntseq_t *bns, const uint8_t *pac, const mem_pestat_t pes[4], uint64_t id, bseq1_t s[2], mem_alnreg_v a[2]);
1218 extern void mem_reg2ovlp(const mem_opt_t *opt, const bntseq_t *bns, const uint8_t *pac, bseq1_t *s, mem_alnreg_v *a);
1219 worker_t *w = (worker_t*)data;
1220 if (!(w->opt->flag&MEM_F_PE)) {
1221 if (bwa_verbose >= 4) printf("=====> Finalizing read '%s' <=====\n", w->seqs[i].name);
1222 mem_mark_primary_se(w->opt, w->regs[i].n, w->regs[i].a, w->n_processed + i);
1223 if (w->opt->flag & MEM_F_PRIMARY5) mem_reorder_primary5(w->opt->T, &w->regs[i]);
1224 mem_reg2sam(w->opt, w->bns, w->pac, &w->seqs[i], &w->regs[i], 0, 0);
1225 free(w->regs[i].a);
1226 } else {
1227 if (bwa_verbose >= 4) printf("=====> Finalizing read pair '%s' <=====\n", w->seqs[i<<1|0].name);
1228 mem_sam_pe(w->opt, w->bns, w->pac, w->pes, (w->n_processed>>1) + i, &w->seqs[i<<1], &w->regs[i<<1]);
1229 free(w->regs[i<<1|0].a); free(w->regs[i<<1|1].a);
1230 }
1231 }
1232
1233 void mem_process_seqs(const mem_opt_t *opt, const bwt_t *bwt, const bntseq_t *bns, const uint8_t *pac, int64_t n_processed, int n, bseq1_t *seqs, const mem_pestat_t *pes0)
1234 {
1235 extern void kt_for(int n_threads, void (*func)(void*,long,int), void *data, long n);
1236 worker_t w;
1237 mem_pestat_t pes[4];
1238 double ctime, rtime;
1239 int i;
1240
1241 ctime = cputime(); rtime = realtime();
1242 global_bns = bns;
1243 w.regs = malloc(n * sizeof(mem_alnreg_v));
1244 w.opt = opt; w.bwt = bwt; w.bns = bns; w.pac = pac;
1245 w.seqs = seqs; w.n_processed = n_processed;
1246 w.pes = &pes[0];
1247 w.aux = malloc(opt->n_threads * sizeof(smem_aux_t*));
1248 for (i = 0; i < opt->n_threads; ++i)
1249 w.aux[i] = smem_aux_init();
1250 kt_for(opt->n_threads, worker1, &w, (opt->flag&MEM_F_PE)? n>>1 : n); // find mapping positions
1251 for (i = 0; i < opt->n_threads; ++i)
1252 smem_aux_destroy(w.aux[i]);
1253 free(w.aux);
1254 if (opt->flag&MEM_F_PE) { // infer insert sizes if not provided
1255 if (pes0) memcpy(pes, pes0, 4 * sizeof(mem_pestat_t)); // if pes0 != NULL, set the insert-size distribution as pes0
1256 else mem_pestat(opt, bns->l_pac, n, w.regs, pes); // otherwise, infer the insert size distribution from data
1257 }
1258 kt_for(opt->n_threads, worker2, &w, (opt->flag&MEM_F_PE)? n>>1 : n); // generate alignment
1259 free(w.regs);
1260 if (bwa_verbose >= 3)
1261 fprintf(stderr, "[M::%s] Processed %d reads in %.3f CPU sec, %.3f real sec\n", __func__, n, cputime() - ctime, realtime() - rtime);
1262 }