| 1 |
#include <unistd.h> |
| 2 |
#include <string.h> |
| 3 |
#include <stdio.h> |
| 4 |
#include <stdlib.h> |
| 5 |
#include <math.h> |
| 6 |
#include <time.h> |
| 7 |
#include <assert.h> |
| 8 |
#include "bwase.h" |
| 9 |
#include "bwtaln.h" |
| 10 |
#include "bntseq.h" |
| 11 |
#include "utils.h" |
| 12 |
#include "kstring.h" |
| 13 |
#include "bwa.h" |
| 14 |
#include "ksw.h" |
| 15 |
|
| 16 |
#ifdef USE_MALLOC_WRAPPERS |
| 17 |
# include "malloc_wrap.h" |
| 18 |
#endif |
| 19 |
|
| 20 |
int g_log_n[256]; |
| 21 |
|
| 22 |
void bwa_aln2seq_core(int n_aln, const bwt_aln1_t *aln, bwa_seq_t *s, int set_main, int n_multi) |
| 23 |
{ |
| 24 |
int i, cnt, best; |
| 25 |
if (n_aln == 0) { |
| 26 |
s->type = BWA_TYPE_NO_MATCH; |
| 27 |
s->c1 = s->c2 = 0; |
| 28 |
return; |
| 29 |
} |
| 30 |
|
| 31 |
if (set_main) { |
| 32 |
best = aln[0].score; |
| 33 |
for (i = cnt = 0; i < n_aln; ++i) { |
| 34 |
const bwt_aln1_t *p = aln + i; |
| 35 |
if (p->score > best) break; |
| 36 |
if (drand48() * (p->l - p->k + 1 + cnt) > (double)cnt) { |
| 37 |
s->n_mm = p->n_mm; s->n_gapo = p->n_gapo; s->n_gape = p->n_gape; |
| 38 |
s->ref_shift = (int)p->n_del - (int)p->n_ins; |
| 39 |
s->score = p->score; |
| 40 |
s->sa = p->k + (bwtint_t)((p->l - p->k + 1) * drand48()); |
| 41 |
} |
| 42 |
cnt += p->l - p->k + 1; |
| 43 |
} |
| 44 |
s->c1 = cnt; |
| 45 |
for (; i < n_aln; ++i) cnt += aln[i].l - aln[i].k + 1; |
| 46 |
s->c2 = cnt - s->c1; |
| 47 |
s->type = s->c1 > 1? BWA_TYPE_REPEAT : BWA_TYPE_UNIQUE; |
| 48 |
} |
| 49 |
|
| 50 |
if (n_multi) { |
| 51 |
int k, rest, n_occ, z = 0; |
| 52 |
for (k = n_occ = 0; k < n_aln; ++k) { |
| 53 |
const bwt_aln1_t *q = aln + k; |
| 54 |
n_occ += q->l - q->k + 1; |
| 55 |
} |
| 56 |
if (s->multi) free(s->multi); |
| 57 |
if (n_occ > n_multi + 1) { // if there are too many hits, generate none of them |
| 58 |
s->multi = 0; s->n_multi = 0; |
| 59 |
return; |
| 60 |
} |
| 61 |
/* The following code is more flexible than what is required |
| 62 |
* here. In principle, due to the requirement above, we can |
| 63 |
* simply output all hits, but the following samples "rest" |
| 64 |
* number of random hits. */ |
| 65 |
rest = n_occ > n_multi + 1? n_multi + 1 : n_occ; // find one additional for ->sa |
| 66 |
s->multi = calloc(rest, sizeof(bwt_multi1_t)); |
| 67 |
for (k = 0; k < n_aln; ++k) { |
| 68 |
const bwt_aln1_t *q = aln + k; |
| 69 |
if (q->l - q->k + 1 <= rest) { |
| 70 |
bwtint_t l; |
| 71 |
for (l = q->k; l <= q->l; ++l) { |
| 72 |
s->multi[z].pos = l; |
| 73 |
s->multi[z].gap = q->n_gapo + q->n_gape; |
| 74 |
s->multi[z].ref_shift = (int)q->n_del - (int)q->n_ins; |
| 75 |
s->multi[z++].mm = q->n_mm; |
| 76 |
} |
| 77 |
rest -= q->l - q->k + 1; |
| 78 |
} else { // Random sampling (http://code.activestate.com/recipes/272884/). In fact, we never come here. |
| 79 |
int j, i; |
| 80 |
for (j = rest, i = q->l - q->k + 1; j > 0; --j) { |
| 81 |
double p = 1.0, x = drand48(); |
| 82 |
while (x < p) p -= p * j / (i--); |
| 83 |
s->multi[z].pos = q->l - i; |
| 84 |
s->multi[z].gap = q->n_gapo + q->n_gape; |
| 85 |
s->multi[z].ref_shift = (int)q->n_del - (int)q->n_ins; |
| 86 |
s->multi[z++].mm = q->n_mm; |
| 87 |
} |
| 88 |
rest = 0; |
| 89 |
break; |
| 90 |
} |
| 91 |
} |
| 92 |
s->n_multi = z; |
| 93 |
} |
| 94 |
} |
| 95 |
|
| 96 |
void bwa_aln2seq(int n_aln, const bwt_aln1_t *aln, bwa_seq_t *s) |
| 97 |
{ |
| 98 |
bwa_aln2seq_core(n_aln, aln, s, 1, 0); |
| 99 |
} |
| 100 |
|
| 101 |
int bwa_approx_mapQ(const bwa_seq_t *p, int mm) |
| 102 |
{ |
| 103 |
int n; |
| 104 |
if (p->c1 == 0) return 23; |
| 105 |
if (p->c1 > 1) return 0; |
| 106 |
if (p->n_mm == mm) return 25; |
| 107 |
if (p->c2 == 0) return 37; |
| 108 |
n = (p->c2 >= 255)? 255 : p->c2; |
| 109 |
return (23 < g_log_n[n])? 0 : 23 - g_log_n[n]; |
| 110 |
} |
| 111 |
|
| 112 |
bwtint_t bwa_sa2pos(const bntseq_t *bns, const bwt_t *bwt, bwtint_t sapos, int ref_len, int *strand) |
| 113 |
{ |
| 114 |
bwtint_t pos_f; |
| 115 |
int is_rev; |
| 116 |
*strand = 0; // initialise strand to 0 otherwise we could return without setting it |
| 117 |
pos_f = bwt_sa(bwt, sapos); // position on the forward-reverse coordinate |
| 118 |
if (pos_f < bns->l_pac && bns->l_pac < pos_f + ref_len) return (bwtint_t)-1; |
| 119 |
pos_f = bns_depos(bns, pos_f, &is_rev); // position on the forward strand; this may be the first base or the last base |
| 120 |
*strand = !is_rev; |
| 121 |
if (is_rev) pos_f = pos_f + 1 < ref_len? 0 : pos_f - ref_len + 1; // position of the first base |
| 122 |
return pos_f; // FIXME: it is possible that pos_f < bns->anns[ref_id].offset |
| 123 |
} |
| 124 |
|
| 125 |
/** |
| 126 |
* Derive the actual position in the read from the given suffix array |
| 127 |
* coordinates. Note that the position will be approximate based on |
| 128 |
* whether indels appear in the read and whether calculations are |
| 129 |
* performed from the start or end of the read. |
| 130 |
*/ |
| 131 |
void bwa_cal_pac_pos_core(const bntseq_t *bns, const bwt_t *bwt, bwa_seq_t *seq, const int max_mm, const float fnr) |
| 132 |
{ |
| 133 |
int max_diff, strand; |
| 134 |
if (seq->type != BWA_TYPE_UNIQUE && seq->type != BWA_TYPE_REPEAT) return; |
| 135 |
max_diff = fnr > 0.0? bwa_cal_maxdiff(seq->len, BWA_AVG_ERR, fnr) : max_mm; |
| 136 |
seq->seQ = seq->mapQ = bwa_approx_mapQ(seq, max_diff); |
| 137 |
//fprintf(stderr, "%d\n", seq->ref_shift); |
| 138 |
seq->pos = bwa_sa2pos(bns, bwt, seq->sa, seq->len + seq->ref_shift, &strand); |
| 139 |
seq->strand = strand; |
| 140 |
seq->seQ = seq->mapQ = bwa_approx_mapQ(seq, max_diff); |
| 141 |
if (seq->pos == (bwtint_t)-1) seq->type = BWA_TYPE_NO_MATCH; |
| 142 |
} |
| 143 |
|
| 144 |
void bwa_cal_pac_pos(const bntseq_t *bns, const char *prefix, int n_seqs, bwa_seq_t *seqs, int max_mm, float fnr) |
| 145 |
{ |
| 146 |
int i, j, strand, n_multi; |
| 147 |
char str[1024]; |
| 148 |
bwt_t *bwt; |
| 149 |
// load forward SA |
| 150 |
strcpy(str, prefix); strcat(str, ".bwt"); bwt = bwt_restore_bwt(str); |
| 151 |
strcpy(str, prefix); strcat(str, ".sa"); bwt_restore_sa(str, bwt); |
| 152 |
for (i = 0; i != n_seqs; ++i) { |
| 153 |
bwa_seq_t *p = &seqs[i]; |
| 154 |
bwa_cal_pac_pos_core(bns, bwt, p, max_mm, fnr); |
| 155 |
for (j = n_multi = 0; j < p->n_multi; ++j) { |
| 156 |
bwt_multi1_t *q = p->multi + j; |
| 157 |
q->pos = bwa_sa2pos(bns, bwt, q->pos, p->len + q->ref_shift, &strand); |
| 158 |
q->strand = strand; |
| 159 |
if (q->pos != p->pos && q->pos != (bwtint_t)-1) |
| 160 |
p->multi[n_multi++] = *q; |
| 161 |
} |
| 162 |
p->n_multi = n_multi; |
| 163 |
} |
| 164 |
bwt_destroy(bwt); |
| 165 |
} |
| 166 |
|
| 167 |
#define SW_BW 50 |
| 168 |
|
| 169 |
bwa_cigar_t *bwa_refine_gapped_core(bwtint_t l_pac, const ubyte_t *pacseq, int len, ubyte_t *seq, int ref_shift, bwtint_t *_rb, int *n_cigar) |
| 170 |
{ |
| 171 |
bwa_cigar_t *cigar = 0; |
| 172 |
uint32_t *cigar32 = 0; |
| 173 |
ubyte_t *rseq; |
| 174 |
int64_t k, rb, re, rlen; |
| 175 |
int8_t mat[25]; |
| 176 |
int w; |
| 177 |
|
| 178 |
bwa_fill_scmat(1, 3, mat); |
| 179 |
rb = *_rb; re = rb + len + ref_shift; |
| 180 |
assert(re <= l_pac); |
| 181 |
rseq = bns_get_seq(l_pac, pacseq, rb, re, &rlen); |
| 182 |
assert(re - rb == rlen); |
| 183 |
w = abs((int)rlen - len) * 1.5; |
| 184 |
ksw_global(len, seq, rlen, rseq, 5, mat, 5, 1, SW_BW > w? SW_BW : w, n_cigar, &cigar32); |
| 185 |
assert(*n_cigar > 0); |
| 186 |
if ((cigar32[*n_cigar - 1]&0xf) == 1) cigar32[*n_cigar - 1] = (cigar32[*n_cigar - 1]>>4<<4) | 3; // change endding ins to soft clipping |
| 187 |
if ((cigar32[0]&0xf) == 1) cigar32[0] = (cigar32[0]>>4<<4) | 3; // change beginning ins to soft clipping |
| 188 |
if ((cigar32[*n_cigar - 1]&0xf) == 2) --*n_cigar; // delete endding del |
| 189 |
if ((cigar32[0]&0xf) == 2) { // delete beginning del |
| 190 |
*_rb += cigar32[0]>>4; |
| 191 |
--*n_cigar; |
| 192 |
memmove(cigar32, cigar32+1, (*n_cigar) * 4); |
| 193 |
} |
| 194 |
cigar = (bwa_cigar_t*)cigar32; |
| 195 |
for (k = 0; k < *n_cigar; ++k) |
| 196 |
cigar[k] = __cigar_create((cigar32[k]&0xf), (cigar32[k]>>4)); |
| 197 |
free(rseq); |
| 198 |
return cigar; |
| 199 |
} |
| 200 |
|
| 201 |
char *bwa_cal_md1(int n_cigar, bwa_cigar_t *cigar, int len, bwtint_t pos, ubyte_t *seq, |
| 202 |
bwtint_t l_pac, ubyte_t *pacseq, kstring_t *str, int *_nm) |
| 203 |
{ |
| 204 |
bwtint_t x, y; |
| 205 |
int z, u, c, nm = 0; |
| 206 |
str->l = 0; // reset |
| 207 |
x = pos; y = 0; |
| 208 |
if (cigar) { |
| 209 |
int k, l; |
| 210 |
for (k = u = 0; k < n_cigar; ++k) { |
| 211 |
l = __cigar_len(cigar[k]); |
| 212 |
if (__cigar_op(cigar[k]) == FROM_M) { |
| 213 |
for (z = 0; z < l && x+z < l_pac; ++z) { |
| 214 |
c = pacseq[(x+z)>>2] >> ((~(x+z)&3)<<1) & 3; |
| 215 |
if (c > 3 || seq[y+z] > 3 || c != seq[y+z]) { |
| 216 |
ksprintf(str, "%d", u); |
| 217 |
kputc("ACGTN"[c], str); |
| 218 |
++nm; |
| 219 |
u = 0; |
| 220 |
} else ++u; |
| 221 |
} |
| 222 |
x += l; y += l; |
| 223 |
} else if (__cigar_op(cigar[k]) == FROM_I || __cigar_op(cigar[k]) == FROM_S) { |
| 224 |
y += l; |
| 225 |
if (__cigar_op(cigar[k]) == FROM_I) nm += l; |
| 226 |
} else if (__cigar_op(cigar[k]) == FROM_D) { |
| 227 |
ksprintf(str, "%d", u); |
| 228 |
kputc('^', str); |
| 229 |
for (z = 0; z < l && x+z < l_pac; ++z) |
| 230 |
kputc("ACGT"[pacseq[(x+z)>>2] >> ((~(x+z)&3)<<1) & 3], str); |
| 231 |
u = 0; |
| 232 |
x += l; nm += l; |
| 233 |
} |
| 234 |
} |
| 235 |
} else { // no gaps |
| 236 |
for (z = u = 0; z < (bwtint_t)len && x+z < l_pac; ++z) { |
| 237 |
c = pacseq[(x+z)>>2] >> ((~(x+z)&3)<<1) & 3; |
| 238 |
if (c > 3 || seq[y+z] > 3 || c != seq[y+z]) { |
| 239 |
ksprintf(str, "%d", u); |
| 240 |
kputc("ACGTN"[c], str); |
| 241 |
++nm; |
| 242 |
u = 0; |
| 243 |
} else ++u; |
| 244 |
} |
| 245 |
} |
| 246 |
ksprintf(str, "%d", u); |
| 247 |
*_nm = nm; |
| 248 |
return strdup(str->s); |
| 249 |
} |
| 250 |
|
| 251 |
void bwa_correct_trimmed(bwa_seq_t *s) |
| 252 |
{ |
| 253 |
if (s->len == s->full_len) return; |
| 254 |
if (s->strand == 0) { // forward |
| 255 |
if (s->cigar && __cigar_op(s->cigar[s->n_cigar-1]) == FROM_S) { // the last is S |
| 256 |
s->cigar[s->n_cigar-1] += s->full_len - s->len; |
| 257 |
} else { |
| 258 |
if (s->cigar == 0) { |
| 259 |
s->n_cigar = 2; |
| 260 |
s->cigar = calloc(s->n_cigar, sizeof(bwa_cigar_t)); |
| 261 |
s->cigar[0] = __cigar_create(0, s->len); |
| 262 |
} else { |
| 263 |
++s->n_cigar; |
| 264 |
s->cigar = realloc(s->cigar, s->n_cigar * sizeof(bwa_cigar_t)); |
| 265 |
} |
| 266 |
s->cigar[s->n_cigar-1] = __cigar_create(3, (s->full_len - s->len)); |
| 267 |
} |
| 268 |
} else { // reverse |
| 269 |
if (s->cigar && __cigar_op(s->cigar[0]) == FROM_S) { // the first is S |
| 270 |
s->cigar[0] += s->full_len - s->len; |
| 271 |
} else { |
| 272 |
if (s->cigar == 0) { |
| 273 |
s->n_cigar = 2; |
| 274 |
s->cigar = calloc(s->n_cigar, sizeof(bwa_cigar_t)); |
| 275 |
s->cigar[1] = __cigar_create(0, s->len); |
| 276 |
} else { |
| 277 |
++s->n_cigar; |
| 278 |
s->cigar = realloc(s->cigar, s->n_cigar * sizeof(bwa_cigar_t)); |
| 279 |
memmove(s->cigar + 1, s->cigar, (s->n_cigar-1) * sizeof(bwa_cigar_t)); |
| 280 |
} |
| 281 |
s->cigar[0] = __cigar_create(3, (s->full_len - s->len)); |
| 282 |
} |
| 283 |
} |
| 284 |
s->len = s->full_len; |
| 285 |
} |
| 286 |
|
| 287 |
void bwa_refine_gapped(const bntseq_t *bns, int n_seqs, bwa_seq_t *seqs, ubyte_t *_pacseq) |
| 288 |
{ |
| 289 |
ubyte_t *pacseq; |
| 290 |
int i, j, k; |
| 291 |
kstring_t *str; |
| 292 |
|
| 293 |
if (!_pacseq) { |
| 294 |
pacseq = (ubyte_t*)calloc(bns->l_pac/4+1, 1); |
| 295 |
err_rewind(bns->fp_pac); |
| 296 |
err_fread_noeof(pacseq, 1, bns->l_pac/4+1, bns->fp_pac); |
| 297 |
} else pacseq = _pacseq; |
| 298 |
for (i = 0; i != n_seqs; ++i) { |
| 299 |
bwa_seq_t *s = seqs + i; |
| 300 |
seq_reverse(s->len, s->seq, 0); // IMPORTANT: s->seq is reversed here!!! |
| 301 |
for (j = k = 0; j < s->n_multi; ++j) { |
| 302 |
bwt_multi1_t *q = s->multi + j; |
| 303 |
int n_cigar; |
| 304 |
if (q->gap) { // gapped alignment |
| 305 |
q->cigar = bwa_refine_gapped_core(bns->l_pac, pacseq, s->len, q->strand? s->rseq : s->seq, q->ref_shift, &q->pos, &n_cigar); |
| 306 |
q->n_cigar = n_cigar; |
| 307 |
if (q->cigar) s->multi[k++] = *q; |
| 308 |
} else s->multi[k++] = *q; |
| 309 |
} |
| 310 |
s->n_multi = k; // this squeezes out gapped alignments which failed the CIGAR generation |
| 311 |
if (s->type == BWA_TYPE_NO_MATCH || s->type == BWA_TYPE_MATESW || s->n_gapo == 0) continue; |
| 312 |
s->cigar = bwa_refine_gapped_core(bns->l_pac, pacseq, s->len, s->strand? s->rseq : s->seq, s->ref_shift, &s->pos, &s->n_cigar); |
| 313 |
if (s->cigar == 0) s->type = BWA_TYPE_NO_MATCH; |
| 314 |
} |
| 315 |
// generate MD tag |
| 316 |
str = (kstring_t*)calloc(1, sizeof(kstring_t)); |
| 317 |
for (i = 0; i != n_seqs; ++i) { |
| 318 |
bwa_seq_t *s = seqs + i; |
| 319 |
if (s->type != BWA_TYPE_NO_MATCH) { |
| 320 |
int nm; |
| 321 |
s->md = bwa_cal_md1(s->n_cigar, s->cigar, s->len, s->pos, s->strand? s->rseq : s->seq, bns->l_pac, pacseq, str, &nm); |
| 322 |
s->nm = nm; |
| 323 |
} |
| 324 |
} |
| 325 |
free(str->s); free(str); |
| 326 |
|
| 327 |
// correct for trimmed reads |
| 328 |
for (i = 0; i < n_seqs; ++i) bwa_correct_trimmed(seqs + i); |
| 329 |
|
| 330 |
if (!_pacseq) free(pacseq); |
| 331 |
} |
| 332 |
|
| 333 |
int64_t pos_end(const bwa_seq_t *p) |
| 334 |
{ |
| 335 |
if (p->cigar) { |
| 336 |
int j; |
| 337 |
int64_t x = p->pos; |
| 338 |
for (j = 0; j != p->n_cigar; ++j) { |
| 339 |
int op = __cigar_op(p->cigar[j]); |
| 340 |
if (op == 0 || op == 2) x += __cigar_len(p->cigar[j]); |
| 341 |
} |
| 342 |
return x; |
| 343 |
} else return p->pos + p->len; |
| 344 |
} |
| 345 |
|
| 346 |
int64_t pos_end_multi(const bwt_multi1_t *p, int len) // analogy to pos_end() |
| 347 |
{ |
| 348 |
if (p->cigar) { |
| 349 |
int j; |
| 350 |
int64_t x = p->pos; |
| 351 |
for (j = 0; j != p->n_cigar; ++j) { |
| 352 |
int op = __cigar_op(p->cigar[j]); |
| 353 |
if (op == 0 || op == 2) x += __cigar_len(p->cigar[j]); |
| 354 |
} |
| 355 |
return x; |
| 356 |
} else return p->pos + len; |
| 357 |
} |
| 358 |
|
| 359 |
static int64_t pos_5(const bwa_seq_t *p) |
| 360 |
{ |
| 361 |
if (p->type != BWA_TYPE_NO_MATCH) |
| 362 |
return p->strand? pos_end(p) : p->pos; |
| 363 |
return -1; |
| 364 |
} |
| 365 |
|
| 366 |
void bwa_print_seq(FILE *stream, bwa_seq_t *seq) { |
| 367 |
char buffer[4096]; |
| 368 |
const int bsz = sizeof(buffer); |
| 369 |
int i, j, l; |
| 370 |
|
| 371 |
if (seq->strand == 0) { |
| 372 |
for (i = 0; i < seq->full_len; i += bsz) { |
| 373 |
l = seq->full_len - i > bsz ? bsz : seq->full_len - i; |
| 374 |
for (j = 0; j < l; j++) buffer[j] = "ACGTN"[seq->seq[i + j]]; |
| 375 |
err_fwrite(buffer, 1, l, stream); |
| 376 |
} |
| 377 |
} else { |
| 378 |
for (i = seq->full_len - 1; i >= 0; i -= bsz) { |
| 379 |
l = i + 1 > bsz ? bsz : i + 1; |
| 380 |
for (j = 0; j < l; j++) buffer[j] = "TGCAN"[seq->seq[i - j]]; |
| 381 |
err_fwrite(buffer, 1, l, stream); |
| 382 |
} |
| 383 |
} |
| 384 |
} |
| 385 |
|
| 386 |
void bwa_print_sam1(const bntseq_t *bns, bwa_seq_t *p, const bwa_seq_t *mate, int mode, int max_top2) |
| 387 |
{ |
| 388 |
int j; |
| 389 |
if (p->type != BWA_TYPE_NO_MATCH || (mate && mate->type != BWA_TYPE_NO_MATCH)) { |
| 390 |
int seqid, nn, am = 0, flag = p->extra_flag; |
| 391 |
char XT; |
| 392 |
|
| 393 |
if (p->type == BWA_TYPE_NO_MATCH) { |
| 394 |
p->pos = mate->pos; |
| 395 |
p->strand = mate->strand; |
| 396 |
flag |= SAM_FSU; |
| 397 |
j = 1; |
| 398 |
} else j = pos_end(p) - p->pos; // j is the length of the reference in the alignment |
| 399 |
|
| 400 |
// get seqid |
| 401 |
nn = bns_cnt_ambi(bns, p->pos, j, &seqid); |
| 402 |
if (p->type != BWA_TYPE_NO_MATCH && p->pos + j - bns->anns[seqid].offset > bns->anns[seqid].len) |
| 403 |
flag |= SAM_FSU; // flag UNMAP as this alignment bridges two adjacent reference sequences |
| 404 |
|
| 405 |
// update flag and print it |
| 406 |
if (p->strand) flag |= SAM_FSR; |
| 407 |
if (mate) { |
| 408 |
if (mate->type != BWA_TYPE_NO_MATCH) { |
| 409 |
if (mate->strand) flag |= SAM_FMR; |
| 410 |
} else flag |= SAM_FMU; |
| 411 |
} |
| 412 |
err_printf("%s\t%d\t%s\t", p->name, flag, bns->anns[seqid].name); |
| 413 |
err_printf("%d\t%d\t", (int)(p->pos - bns->anns[seqid].offset + 1), p->mapQ); |
| 414 |
|
| 415 |
// print CIGAR |
| 416 |
if (p->cigar) { |
| 417 |
for (j = 0; j != p->n_cigar; ++j) |
| 418 |
err_printf("%d%c", __cigar_len(p->cigar[j]), "MIDS"[__cigar_op(p->cigar[j])]); |
| 419 |
} else if (p->type == BWA_TYPE_NO_MATCH) err_printf("*"); |
| 420 |
else err_printf("%dM", p->len); |
| 421 |
|
| 422 |
// print mate coordinate |
| 423 |
if (mate && mate->type != BWA_TYPE_NO_MATCH) { |
| 424 |
int m_seqid; |
| 425 |
long long isize; |
| 426 |
am = mate->seQ < p->seQ? mate->seQ : p->seQ; // smaller single-end mapping quality |
| 427 |
// redundant calculation here, but should not matter too much |
| 428 |
bns_cnt_ambi(bns, mate->pos, mate->len, &m_seqid); |
| 429 |
err_printf("\t%s\t", (seqid == m_seqid)? "=" : bns->anns[m_seqid].name); |
| 430 |
isize = (seqid == m_seqid)? pos_5(mate) - pos_5(p) : 0; |
| 431 |
if (p->type == BWA_TYPE_NO_MATCH) isize = 0; |
| 432 |
err_printf("%d\t%lld\t", (int)(mate->pos - bns->anns[m_seqid].offset + 1), isize); |
| 433 |
} else if (mate) err_printf("\t=\t%d\t0\t", (int)(p->pos - bns->anns[seqid].offset + 1)); |
| 434 |
else err_printf("\t*\t0\t0\t"); |
| 435 |
|
| 436 |
// print sequence and quality |
| 437 |
bwa_print_seq(stdout, p); |
| 438 |
err_putchar('\t'); |
| 439 |
if (p->qual) { |
| 440 |
if (p->strand) seq_reverse(p->len, p->qual, 0); // reverse quality |
| 441 |
err_printf("%s", p->qual); |
| 442 |
} else err_printf("*"); |
| 443 |
|
| 444 |
if (bwa_rg_id[0]) err_printf("\tRG:Z:%s", bwa_rg_id); |
| 445 |
if (p->bc[0]) err_printf("\tBC:Z:%s", p->bc); |
| 446 |
if (p->clip_len < p->full_len) err_printf("\tXC:i:%d", p->clip_len); |
| 447 |
if (p->type != BWA_TYPE_NO_MATCH) { |
| 448 |
int i; |
| 449 |
// calculate XT tag |
| 450 |
XT = "NURM"[p->type]; |
| 451 |
if (nn > 10) XT = 'N'; |
| 452 |
// print tags |
| 453 |
err_printf("\tXT:A:%c\t%s:i:%d", XT, (mode & BWA_MODE_COMPREAD)? "NM" : "CM", p->nm); |
| 454 |
if (nn) err_printf("\tXN:i:%d", nn); |
| 455 |
if (mate) err_printf("\tSM:i:%d\tAM:i:%d", p->seQ, am); |
| 456 |
if (p->type != BWA_TYPE_MATESW) { // X0 and X1 are not available for this type of alignment |
| 457 |
err_printf("\tX0:i:%d", p->c1); |
| 458 |
if (p->c1 <= max_top2) err_printf("\tX1:i:%d", p->c2); |
| 459 |
} |
| 460 |
err_printf("\tXM:i:%d\tXO:i:%d\tXG:i:%d", p->n_mm, p->n_gapo, p->n_gapo+p->n_gape); |
| 461 |
if (p->md) err_printf("\tMD:Z:%s", p->md); |
| 462 |
// print multiple hits |
| 463 |
if (p->n_multi) { |
| 464 |
err_printf("\tXA:Z:"); |
| 465 |
for (i = 0; i < p->n_multi; ++i) { |
| 466 |
bwt_multi1_t *q = p->multi + i; |
| 467 |
int k; |
| 468 |
j = pos_end_multi(q, p->len) - q->pos; |
| 469 |
nn = bns_cnt_ambi(bns, q->pos, j, &seqid); |
| 470 |
err_printf("%s,%c%d,", bns->anns[seqid].name, q->strand? '-' : '+', |
| 471 |
(int)(q->pos - bns->anns[seqid].offset + 1)); |
| 472 |
if (q->cigar) { |
| 473 |
for (k = 0; k < q->n_cigar; ++k) |
| 474 |
err_printf("%d%c", __cigar_len(q->cigar[k]), "MIDS"[__cigar_op(q->cigar[k])]); |
| 475 |
} else err_printf("%dM", p->len); |
| 476 |
err_printf(",%d;", q->gap + q->mm); |
| 477 |
} |
| 478 |
} |
| 479 |
} |
| 480 |
err_putchar('\n'); |
| 481 |
} else { // this read has no match |
| 482 |
//ubyte_t *s = p->strand? p->rseq : p->seq; |
| 483 |
int flag = p->extra_flag | SAM_FSU; |
| 484 |
if (mate && mate->type == BWA_TYPE_NO_MATCH) flag |= SAM_FMU; |
| 485 |
err_printf("%s\t%d\t*\t0\t0\t*\t*\t0\t0\t", p->name, flag); |
| 486 |
//Why did this work differently to the version above?? |
| 487 |
//for (j = 0; j != p->len; ++j) putchar("ACGTN"[(int)s[j]]); |
| 488 |
bwa_print_seq(stdout, p); |
| 489 |
err_putchar('\t'); |
| 490 |
if (p->qual) { |
| 491 |
if (p->strand) seq_reverse(p->len, p->qual, 0); // reverse quality |
| 492 |
err_printf("%s", p->qual); |
| 493 |
} else err_printf("*"); |
| 494 |
if (bwa_rg_id[0]) err_printf("\tRG:Z:%s", bwa_rg_id); |
| 495 |
if (p->bc[0]) err_printf("\tBC:Z:%s", p->bc); |
| 496 |
if (p->clip_len < p->full_len) err_printf("\tXC:i:%d", p->clip_len); |
| 497 |
err_putchar('\n'); |
| 498 |
} |
| 499 |
} |
| 500 |
|
| 501 |
void bwase_initialize() |
| 502 |
{ |
| 503 |
int i; |
| 504 |
for (i = 1; i != 256; ++i) g_log_n[i] = (int)(4.343 * log(i) + 0.5); |
| 505 |
} |
| 506 |
|
| 507 |
void bwa_sai2sam_se_core(const char *prefix, const char *fn_sa, const char *fn_fa, int n_occ, const char *rg_line) |
| 508 |
{ |
| 509 |
extern bwa_seqio_t *bwa_open_reads(int mode, const char *fn_fa); |
| 510 |
int i, n_seqs, m_aln; |
| 511 |
long long tot_seqs = 0; |
| 512 |
bwt_aln1_t *aln = 0; |
| 513 |
bwa_seq_t *seqs; |
| 514 |
bwa_seqio_t *ks; |
| 515 |
clock_t t; |
| 516 |
bntseq_t *bns; |
| 517 |
FILE *fp_sa; |
| 518 |
gap_opt_t opt; |
| 519 |
char magic[4]; |
| 520 |
|
| 521 |
// initialization |
| 522 |
bwase_initialize(); |
| 523 |
bns = bns_restore(prefix); |
| 524 |
srand48(bns->seed); |
| 525 |
fp_sa = xopen(fn_sa, "r"); |
| 526 |
|
| 527 |
m_aln = 0; |
| 528 |
err_fread_noeof(magic, 1, 4, fp_sa); |
| 529 |
if (strncmp(magic, SAI_MAGIC, 4) != 0) { |
| 530 |
fprintf(stderr, "[E::%s] Unmatched SAI magic. Please re-run `aln' with the same version of bwa.\n", __func__); |
| 531 |
exit(1); |
| 532 |
} |
| 533 |
err_fread_noeof(&opt, sizeof(gap_opt_t), 1, fp_sa); |
| 534 |
bwa_print_sam_hdr(bns, rg_line); |
| 535 |
// set ks |
| 536 |
ks = bwa_open_reads(opt.mode, fn_fa); |
| 537 |
// core loop |
| 538 |
while ((seqs = bwa_read_seq(ks, 0x40000, &n_seqs, opt.mode, opt.trim_qual)) != 0) { |
| 539 |
tot_seqs += n_seqs; |
| 540 |
t = clock(); |
| 541 |
|
| 542 |
// read alignment |
| 543 |
for (i = 0; i < n_seqs; ++i) { |
| 544 |
bwa_seq_t *p = seqs + i; |
| 545 |
int n_aln; |
| 546 |
err_fread_noeof(&n_aln, 4, 1, fp_sa); |
| 547 |
if (n_aln > m_aln) { |
| 548 |
m_aln = n_aln; |
| 549 |
aln = (bwt_aln1_t*)realloc(aln, sizeof(bwt_aln1_t) * m_aln); |
| 550 |
} |
| 551 |
err_fread_noeof(aln, sizeof(bwt_aln1_t), n_aln, fp_sa); |
| 552 |
bwa_aln2seq_core(n_aln, aln, p, 1, n_occ); |
| 553 |
} |
| 554 |
|
| 555 |
fprintf(stderr, "[bwa_aln_core] convert to sequence coordinate... "); |
| 556 |
bwa_cal_pac_pos(bns, prefix, n_seqs, seqs, opt.max_diff, opt.fnr); // forward bwt will be destroyed here |
| 557 |
fprintf(stderr, "%.2f sec\n", (float)(clock() - t) / CLOCKS_PER_SEC); t = clock(); |
| 558 |
|
| 559 |
fprintf(stderr, "[bwa_aln_core] refine gapped alignments... "); |
| 560 |
bwa_refine_gapped(bns, n_seqs, seqs, 0); |
| 561 |
fprintf(stderr, "%.2f sec\n", (float)(clock() - t) / CLOCKS_PER_SEC); t = clock(); |
| 562 |
|
| 563 |
fprintf(stderr, "[bwa_aln_core] print alignments... "); |
| 564 |
for (i = 0; i < n_seqs; ++i) |
| 565 |
bwa_print_sam1(bns, seqs + i, 0, opt.mode, opt.max_top2); |
| 566 |
fprintf(stderr, "%.2f sec\n", (float)(clock() - t) / CLOCKS_PER_SEC); |
| 567 |
|
| 568 |
bwa_free_read_seq(n_seqs, seqs); |
| 569 |
fprintf(stderr, "[bwa_aln_core] %lld sequences have been processed.\n", tot_seqs); |
| 570 |
} |
| 571 |
|
| 572 |
// destroy |
| 573 |
bwa_seq_close(ks); |
| 574 |
bns_destroy(bns); |
| 575 |
err_fclose(fp_sa); |
| 576 |
free(aln); |
| 577 |
} |
| 578 |
|
| 579 |
int bwa_sai2sam_se(int argc, char *argv[]) |
| 580 |
{ |
| 581 |
int c, n_occ = 3; |
| 582 |
char *prefix, *rg_line = 0; |
| 583 |
while ((c = getopt(argc, argv, "hn:f:r:")) >= 0) { |
| 584 |
switch (c) { |
| 585 |
case 'h': break; |
| 586 |
case 'r': |
| 587 |
if ((rg_line = bwa_set_rg(optarg)) == 0) return 1; |
| 588 |
break; |
| 589 |
case 'n': n_occ = atoi(optarg); break; |
| 590 |
case 'f': xreopen(optarg, "w", stdout); break; |
| 591 |
default: return 1; |
| 592 |
} |
| 593 |
} |
| 594 |
|
| 595 |
if (optind + 3 > argc) { |
| 596 |
fprintf(stderr, "Usage: bwa samse [-n max_occ] [-f out.sam] [-r RG_line] <prefix> <in.sai> <in.fq>\n"); |
| 597 |
return 1; |
| 598 |
} |
| 599 |
if ((prefix = bwa_idx_infer_prefix(argv[optind])) == 0) { |
| 600 |
fprintf(stderr, "[%s] fail to locate the index\n", __func__); |
| 601 |
return 1; |
| 602 |
} |
| 603 |
bwa_sai2sam_se_core(prefix, argv[optind+1], argv[optind+2], n_occ, rg_line); |
| 604 |
free(prefix); |
| 605 |
return 0; |
| 606 |
} |