Debian Codegraph @

bwa-apache2/bwa.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 <string.h>
28 #include <stdio.h>
29 #include <zlib.h>
30 #include <assert.h>
31 #include "bntseq.h"
32 #include "bwa.h"
33 #include "ksw.h"
34 #include "utils.h"
35 #include "kstring.h"
36 #include "kvec.h"
37
38 #ifdef USE_MALLOC_WRAPPERS
39 # include "malloc_wrap.h"
40 #endif
41
42 int bwa_verbose = 3;
43 int bwa_dbg = 0;
44 char bwa_rg_id[256];
45 char *bwa_pg;
46
47 /************************
48 * Batch FASTA/Q reader *
49 ************************/
50
51 #include "kseq.h"
52 KSEQ_DECLARE(gzFile)
53
54 static inline void trim_readno(kstring_t *s)
55 {
56 if (s->l > 2 && s->s[s->l-2] == '/' && isdigit(s->s[s->l-1]))
57 s->l -= 2, s->s[s->l] = 0;
58 }
59
60 static inline char *dupkstring(const kstring_t *str, int dupempty)
61 {
62 char *s = (str->l > 0 || dupempty)? malloc(str->l + 1) : NULL;
63 if (!s) return NULL;
64
65 memcpy(s, str->s, str->l);
66 s[str->l] = '\0';
67 return s;
68 }
69
70 static inline void kseq2bseq1(const kseq_t *ks, bseq1_t *s)
71 { // TODO: it would be better to allocate one chunk of memory, but probably it does not matter in practice
72 s->name = dupkstring(&ks->name, 1);
73 s->comment = dupkstring(&ks->comment, 0);
74 s->seq = dupkstring(&ks->seq, 1);
75 s->qual = dupkstring(&ks->qual, 0);
76 s->l_seq = ks->seq.l;
77 }
78
79 bseq1_t *bseq_read(int chunk_size, int *n_, void *ks1_, void *ks2_)
80 {
81 kseq_t *ks = (kseq_t*)ks1_, *ks2 = (kseq_t*)ks2_;
82 int size = 0, m, n;
83 bseq1_t *seqs;
84 m = n = 0; seqs = 0;
85 while (kseq_read(ks) >= 0) {
86 if (ks2 && kseq_read(ks2) < 0) { // the 2nd file has fewer reads
87 fprintf(stderr, "[W::%s] the 2nd file has fewer sequences.\n", __func__);
88 break;
89 }
90 if (n >= m) {
91 m = m? m<<1 : 256;
92 seqs = realloc(seqs, m * sizeof(bseq1_t));
93 }
94 trim_readno(&ks->name);
95 kseq2bseq1(ks, &seqs[n]);
96 seqs[n].id = n;
97 size += seqs[n++].l_seq;
98 if (ks2) {
99 trim_readno(&ks2->name);
100 kseq2bseq1(ks2, &seqs[n]);
101 seqs[n].id = n;
102 size += seqs[n++].l_seq;
103 }
104 if (size >= chunk_size && (n&1) == 0) break;
105 }
106 if (size == 0) { // test if the 2nd file is finished
107 if (ks2 && kseq_read(ks2) >= 0)
108 fprintf(stderr, "[W::%s] the 1st file has fewer sequences.\n", __func__);
109 }
110 *n_ = n;
111 return seqs;
112 }
113
114 void bseq_classify(int n, bseq1_t *seqs, int m[2], bseq1_t *sep[2])
115 {
116 int i, has_last;
117 kvec_t(bseq1_t) a[2] = {{0,0,0}, {0,0,0}};
118 for (i = 1, has_last = 1; i < n; ++i) {
119 if (has_last) {
120 if (strcmp(seqs[i].name, seqs[i-1].name) == 0) {
121 kv_push(bseq1_t, a[1], seqs[i-1]);
122 kv_push(bseq1_t, a[1], seqs[i]);
123 has_last = 0;
124 } else kv_push(bseq1_t, a[0], seqs[i-1]);
125 } else has_last = 1;
126 }
127 if (has_last) kv_push(bseq1_t, a[0], seqs[i-1]);
128 sep[0] = a[0].a, m[0] = a[0].n;
129 sep[1] = a[1].a, m[1] = a[1].n;
130 }
131
132 /*****************
133 * CIGAR related *
134 *****************/
135
136 void bwa_fill_scmat(int a, int b, int8_t mat[25])
137 {
138 int i, j, k;
139 for (i = k = 0; i < 4; ++i) {
140 for (j = 0; j < 4; ++j)
141 mat[k++] = i == j? a : -b;
142 mat[k++] = -1; // ambiguous base
143 }
144 for (j = 0; j < 5; ++j) mat[k++] = -1;
145 }
146
147 // Generate CIGAR when the alignment end points are known
148 uint32_t *bwa_gen_cigar2(const int8_t mat[25], int o_del, int e_del, int o_ins, int e_ins, int w_, int64_t l_pac, const uint8_t *pac, int l_query, uint8_t *query, int64_t rb, int64_t re, int *score, int *n_cigar, int *NM)
149 {
150 uint32_t *cigar = 0;
151 uint8_t tmp, *rseq;
152 int i;
153 int64_t rlen;
154 kstring_t str;
155 const char *int2base;
156
157 if (n_cigar) *n_cigar = 0;
158 if (NM) *NM = -1;
159 if (l_query <= 0 || rb >= re || (rb < l_pac && re > l_pac)) return 0; // reject if negative length or bridging the forward and reverse strand
160 rseq = bns_get_seq(l_pac, pac, rb, re, &rlen);
161 if (re - rb != rlen) goto ret_gen_cigar; // possible if out of range
162 if (rb >= l_pac) { // then reverse both query and rseq; this is to ensure indels to be placed at the leftmost position
163 for (i = 0; i < l_query>>1; ++i)
164 tmp = query[i], query[i] = query[l_query - 1 - i], query[l_query - 1 - i] = tmp;
165 for (i = 0; i < rlen>>1; ++i)
166 tmp = rseq[i], rseq[i] = rseq[rlen - 1 - i], rseq[rlen - 1 - i] = tmp;
167 }
168 if (l_query == re - rb && w_ == 0) { // no gap; no need to do DP
169 // UPDATE: we come to this block now... FIXME: due to an issue in mem_reg2aln(), we never come to this block. This does not affect accuracy, but it hurts performance.
170 if (n_cigar) {
171 cigar = malloc(4);
172 cigar[0] = l_query<<4 | 0;
173 *n_cigar = 1;
174 }
175 for (i = 0, *score = 0; i < l_query; ++i)
176 *score += mat[rseq[i]*5 + query[i]];
177 } else {
178 int w, max_gap, max_ins, max_del, min_w;
179 // set the band-width
180 max_ins = (int)((double)(((l_query+1)>>1) * mat[0] - o_ins) / e_ins + 1.);
181 max_del = (int)((double)(((l_query+1)>>1) * mat[0] - o_del) / e_del + 1.);
182 max_gap = max_ins > max_del? max_ins : max_del;
183 max_gap = max_gap > 1? max_gap : 1;
184 w = (max_gap + abs((int)rlen - l_query) + 1) >> 1;
185 w = w < w_? w : w_;
186 min_w = abs((int)rlen - l_query) + 3;
187 w = w > min_w? w : min_w;
188 // NW alignment
189 if (bwa_verbose >= 4) {
190 printf("* Global bandwidth: %d\n", w);
191 printf("* Global ref: "); for (i = 0; i < rlen; ++i) putchar("ACGTN"[(int)rseq[i]]); putchar('\n');
192 printf("* Global query: "); for (i = 0; i < l_query; ++i) putchar("ACGTN"[(int)query[i]]); putchar('\n');
193 }
194 *score = ksw_global2(l_query, query, rlen, rseq, 5, mat, o_del, e_del, o_ins, e_ins, w, n_cigar, &cigar);
195 }
196 if (NM && n_cigar) {// compute NM and MD
197 int k, x, y, u, n_mm = 0, n_gap = 0;
198 str.l = str.m = *n_cigar * 4; str.s = (char*)cigar; // append MD to CIGAR
199 int2base = rb < l_pac? "ACGTN" : "TGCAN";
200 for (k = 0, x = y = u = 0; k < *n_cigar; ++k) {
201 int op, len;
202 cigar = (uint32_t*)str.s;
203 op = cigar[k]&0xf, len = cigar[k]>>4;
204 if (op == 0) { // match
205 for (i = 0; i < len; ++i) {
206 if (query[x + i] != rseq[y + i]) {
207 kputw(u, &str);
208 kputc(int2base[rseq[y+i]], &str);
209 ++n_mm; u = 0;
210 } else ++u;
211 }
212 x += len; y += len;
213 } else if (op == 2) { // deletion
214 if (k > 0 && k < *n_cigar - 1) { // don't do the following if D is the first or the last CIGAR
215 kputw(u, &str); kputc('^', &str);
216 for (i = 0; i < len; ++i)
217 kputc(int2base[rseq[y+i]], &str);
218 u = 0; n_gap += len;
219 }
220 y += len;
221 } else if (op == 1) x += len, n_gap += len; // insertion
222 }
223 kputw(u, &str); kputc(0, &str);
224 *NM = n_mm + n_gap;
225 cigar = (uint32_t*)str.s;
226 }
227 if (rb >= l_pac) // reverse back query
228 for (i = 0; i < l_query>>1; ++i)
229 tmp = query[i], query[i] = query[l_query - 1 - i], query[l_query - 1 - i] = tmp;
230
231 ret_gen_cigar:
232 free(rseq);
233 return cigar;
234 }
235
236 uint32_t *bwa_gen_cigar(const int8_t mat[25], int q, int r, int w_, int64_t l_pac, const uint8_t *pac, int l_query, uint8_t *query, int64_t rb, int64_t re, int *score, int *n_cigar, int *NM)
237 {
238 return bwa_gen_cigar2(mat, q, r, q, r, w_, l_pac, pac, l_query, query, rb, re, score, n_cigar, NM);
239 }
240
241 /*********************
242 * Full index reader *
243 *********************/
244
245 char *bwa_idx_infer_prefix(const char *hint)
246 {
247 char *prefix;
248 int l_hint;
249 FILE *fp;
250 l_hint = strlen(hint);
251 prefix = malloc(l_hint + 3 + 4 + 1);
252 strcpy(prefix, hint);
253 strcpy(prefix + l_hint, ".64.bwt");
254 if ((fp = fopen(prefix, "rb")) != 0) {
255 fclose(fp);
256 prefix[l_hint + 3] = 0;
257 return prefix;
258 } else {
259 strcpy(prefix + l_hint, ".bwt");
260 if ((fp = fopen(prefix, "rb")) == 0) {
261 free(prefix);
262 return 0;
263 } else {
264 fclose(fp);
265 prefix[l_hint] = 0;
266 return prefix;
267 }
268 }
269 }
270
271 bwt_t *bwa_idx_load_bwt(const char *hint)
272 {
273 char *tmp, *prefix;
274 bwt_t *bwt;
275 prefix = bwa_idx_infer_prefix(hint);
276 if (prefix == 0) {
277 if (bwa_verbose >= 1) fprintf(stderr, "[E::%s] fail to locate the index files\n", __func__);
278 return 0;
279 }
280 tmp = calloc(strlen(prefix) + 5, 1);
281 strcat(strcpy(tmp, prefix), ".bwt"); // FM-index
282 bwt = bwt_restore_bwt(tmp);
283 strcat(strcpy(tmp, prefix), ".sa"); // partial suffix array (SA)
284 bwt_restore_sa(tmp, bwt);
285 free(tmp); free(prefix);
286 return bwt;
287 }
288
289 bwaidx_t *bwa_idx_load_from_disk(const char *hint, int which)
290 {
291 bwaidx_t *idx;
292 char *prefix;
293 prefix = bwa_idx_infer_prefix(hint);
294 if (prefix == 0) {
295 if (bwa_verbose >= 1) fprintf(stderr, "[E::%s] fail to locate the index files\n", __func__);
296 return 0;
297 }
298 idx = calloc(1, sizeof(bwaidx_t));
299 if (which & BWA_IDX_BWT) idx->bwt = bwa_idx_load_bwt(hint);
300 if (which & BWA_IDX_BNS) {
301 int i, c;
302 idx->bns = bns_restore(prefix);
303 for (i = c = 0; i < idx->bns->n_seqs; ++i)
304 if (idx->bns->anns[i].is_alt) ++c;
305 if (bwa_verbose >= 3)
306 fprintf(stderr, "[M::%s] read %d ALT contigs\n", __func__, c);
307 if (which & BWA_IDX_PAC) {
308 idx->pac = calloc(idx->bns->l_pac/4+1, 1);
309 err_fread_noeof(idx->pac, 1, idx->bns->l_pac/4+1, idx->bns->fp_pac); // concatenated 2-bit encoded sequence
310 err_fclose(idx->bns->fp_pac);
311 idx->bns->fp_pac = 0;
312 }
313 }
314 free(prefix);
315 return idx;
316 }
317
318 bwaidx_t *bwa_idx_load(const char *hint, int which)
319 {
320 return bwa_idx_load_from_disk(hint, which);
321 }
322
323 void bwa_idx_destroy(bwaidx_t *idx)
324 {
325 if (idx == 0) return;
326 if (idx->mem == 0) {
327 if (idx->bwt) bwt_destroy(idx->bwt);
328 if (idx->bns) bns_destroy(idx->bns);
329 if (idx->pac) free(idx->pac);
330 } else {
331 free(idx->bwt); free(idx->bns->anns); free(idx->bns);
332 if (!idx->is_shm) free(idx->mem);
333 }
334 free(idx);
335 }
336
337 int bwa_mem2idx(int64_t l_mem, uint8_t *mem, bwaidx_t *idx)
338 {
339 int64_t k = 0, x;
340 int i;
341
342 // generate idx->bwt
343 x = sizeof(bwt_t); idx->bwt = malloc(x); memcpy(idx->bwt, mem + k, x); k += x;
344 x = idx->bwt->bwt_size * 4; idx->bwt->bwt = (uint32_t*)(mem + k); k += x;
345 x = idx->bwt->n_sa * sizeof(bwtint_t); idx->bwt->sa = (bwtint_t*)(mem + k); k += x;
346
347 // generate idx->bns and idx->pac
348 x = sizeof(bntseq_t); idx->bns = malloc(x); memcpy(idx->bns, mem + k, x); k += x;
349 x = idx->bns->n_holes * sizeof(bntamb1_t); idx->bns->ambs = (bntamb1_t*)(mem + k); k += x;
350 x = idx->bns->n_seqs * sizeof(bntann1_t); idx->bns->anns = malloc(x); memcpy(idx->bns->anns, mem + k, x); k += x;
351 for (i = 0; i < idx->bns->n_seqs; ++i) {
352 idx->bns->anns[i].name = (char*)(mem + k); k += strlen(idx->bns->anns[i].name) + 1;
353 idx->bns->anns[i].anno = (char*)(mem + k); k += strlen(idx->bns->anns[i].anno) + 1;
354 }
355 idx->pac = (uint8_t*)(mem + k); k += idx->bns->l_pac/4+1;
356 assert(k == l_mem);
357
358 idx->l_mem = k; idx->mem = mem;
359 return 0;
360 }
361
362 int bwa_idx2mem(bwaidx_t *idx)
363 {
364 int i;
365 int64_t k, x, tmp;
366 uint8_t *mem;
367
368 // copy idx->bwt
369 x = idx->bwt->bwt_size * 4;
370 mem = realloc(idx->bwt->bwt, sizeof(bwt_t) + x); idx->bwt->bwt = 0;
371 memmove(mem + sizeof(bwt_t), mem, x);
372 memcpy(mem, idx->bwt, sizeof(bwt_t)); k = sizeof(bwt_t) + x;
373 x = idx->bwt->n_sa * sizeof(bwtint_t); mem = realloc(mem, k + x); memcpy(mem + k, idx->bwt->sa, x); k += x;
374 free(idx->bwt->sa);
375 free(idx->bwt); idx->bwt = 0;
376
377 // copy idx->bns
378 tmp = idx->bns->n_seqs * sizeof(bntann1_t) + idx->bns->n_holes * sizeof(bntamb1_t);
379 for (i = 0; i < idx->bns->n_seqs; ++i) // compute the size of heap-allocated memory
380 tmp += strlen(idx->bns->anns[i].name) + strlen(idx->bns->anns[i].anno) + 2;
381 mem = realloc(mem, k + sizeof(bntseq_t) + tmp);
382 x = sizeof(bntseq_t); memcpy(mem + k, idx->bns, x); k += x;
383 x = idx->bns->n_holes * sizeof(bntamb1_t); memcpy(mem + k, idx->bns->ambs, x); k += x;
384 free(idx->bns->ambs);
385 x = idx->bns->n_seqs * sizeof(bntann1_t); memcpy(mem + k, idx->bns->anns, x); k += x;
386 for (i = 0; i < idx->bns->n_seqs; ++i) {
387 x = strlen(idx->bns->anns[i].name) + 1; memcpy(mem + k, idx->bns->anns[i].name, x); k += x;
388 x = strlen(idx->bns->anns[i].anno) + 1; memcpy(mem + k, idx->bns->anns[i].anno, x); k += x;
389 free(idx->bns->anns[i].name); free(idx->bns->anns[i].anno);
390 }
391 free(idx->bns->anns);
392
393 // copy idx->pac
394 x = idx->bns->l_pac/4+1;
395 mem = realloc(mem, k + x);
396 memcpy(mem + k, idx->pac, x); k += x;
397 free(idx->bns); idx->bns = 0;
398 free(idx->pac); idx->pac = 0;
399
400 return bwa_mem2idx(k, mem, idx);
401 }
402
403 /***********************
404 * SAM header routines *
405 ***********************/
406
407 void bwa_print_sam_hdr(const bntseq_t *bns, const char *hdr_line)
408 {
409 int i, n_HD = 0, n_SQ = 0;
410 extern char *bwa_pg;
411
412 if (hdr_line) {
413 // check for HD line
414 const char *p = hdr_line;
415 if ((p = strstr(p, "@HD")) != 0) {
416 ++n_HD;
417 }
418 // check for SQ lines
419 p = hdr_line;
420 while ((p = strstr(p, "@SQ\t")) != 0) {
421 if (p == hdr_line || *(p-1) == '\n') ++n_SQ;
422 p += 4;
423 }
424 }
425 if (n_SQ == 0) {
426 for (i = 0; i < bns->n_seqs; ++i) {
427 err_printf("@SQ\tSN:%s\tLN:%d", bns->anns[i].name, bns->anns[i].len);
428 if (bns->anns[i].is_alt) err_printf("\tAH:*\n");
429 else err_fputc('\n', stdout);
430 }
431 } else if (n_SQ != bns->n_seqs && bwa_verbose >= 2)
432 fprintf(stderr, "[W::%s] %d @SQ lines provided with -H; %d sequences in the index. Continue anyway.\n", __func__, n_SQ, bns->n_seqs);
433 if (n_HD == 0) {
434 err_printf("@HD\tVN:1.5\tSO:unsorted\tGO:query\n");
435 }
436 if (hdr_line) err_printf("%s\n", hdr_line);
437 if (bwa_pg) err_printf("%s\n", bwa_pg);
438 }
439
440 static char *bwa_escape(char *s)
441 {
442 char *p, *q;
443 for (p = q = s; *p; ++p) {
444 if (*p == '\\') {
445 ++p;
446 if (*p == 't') *q++ = '\t';
447 else if (*p == 'n') *q++ = '\n';
448 else if (*p == 'r') *q++ = '\r';
449 else if (*p == '\\') *q++ = '\\';
450 } else *q++ = *p;
451 }
452 *q = '\0';
453 return s;
454 }
455
456 char *bwa_set_rg(const char *s)
457 {
458 char *p, *q, *r, *rg_line = 0;
459 memset(bwa_rg_id, 0, 256);
460 if (strstr(s, "@RG") != s) {
461 if (bwa_verbose >= 1) fprintf(stderr, "[E::%s] the read group line is not started with @RG\n", __func__);
462 goto err_set_rg;
463 }
464 if (strstr(s, "\t") != NULL) {
465 if (bwa_verbose >= 1) fprintf(stderr, "[E::%s] the read group line contained literal <tab> characters -- replace with escaped tabs: \\t\n", __func__);
466 goto err_set_rg;
467 }
468 rg_line = strdup(s);
469 bwa_escape(rg_line);
470 if ((p = strstr(rg_line, "\tID:")) == 0) {
471 if (bwa_verbose >= 1) fprintf(stderr, "[E::%s] no ID within the read group line\n", __func__);
472 goto err_set_rg;
473 }
474 p += 4;
475 for (q = p; *q && *q != '\t' && *q != '\n'; ++q);
476 if (q - p + 1 > 256) {
477 if (bwa_verbose >= 1) fprintf(stderr, "[E::%s] @RG:ID is longer than 255 characters\n", __func__);
478 goto err_set_rg;
479 }
480 for (q = p, r = bwa_rg_id; *q && *q != '\t' && *q != '\n'; ++q)
481 *r++ = *q;
482 return rg_line;
483
484 err_set_rg:
485 free(rg_line);
486 return 0;
487 }
488
489 char *bwa_insert_header(const char *s, char *hdr)
490 {
491 int len = 0;
492 if (s == 0 || s[0] != '@') return hdr;
493 if (hdr) {
494 len = strlen(hdr);
495 hdr = realloc(hdr, len + strlen(s) + 2);
496 hdr[len++] = '\n';
497 strcpy(hdr + len, s);
498 } else hdr = strdup(s);
499 bwa_escape(hdr + len);
500 return hdr;
501 }