| 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, >le, &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, >le, &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, ®s); |
| 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 = ®s.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 = ®s.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 |
} |