upstream-dependencies/samtools/bam_md.c
1/* bam_md.c -- calmd subcommand.
2
3 Copyright (C) 2009-2011, 2014-2015, 2019-2020, 2022 Genome Research Ltd.
4 Portions copyright (C) 2009-2011 Broad Institute.
5
6 Author: Heng Li <lh3@sanger.ac.uk>
7
8Permission is hereby granted, free of charge, to any person obtaining a copy
9of this software and associated documentation files (the "Software"), to deal
10in the Software without restriction, including without limitation the rights
11to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
12copies of the Software, and to permit persons to whom the Software is
13furnished to do so, subject to the following conditions:
14
15The above copyright notice and this permission notice shall be included in
16all copies or substantial portions of the Software.
17
18THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
19IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
20FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
21THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
22LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
23FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
24DEALINGS IN THE SOFTWARE. */
25
26#include <config.h>
27
28#include <stdio.h>
29#include <stdlib.h>
30#include <string.h>
31#include <ctype.h>
32#include <limits.h>
33#include <errno.h>
34#include <assert.h>
35#include "htslib/faidx.h"
36#include "htslib/sam.h"
37#include "htslib/kstring.h"
38#include "htslib/thread_pool.h"
39#include "sam_opts.h"
40#include "samtools.h"
41
42#define USE_EQUAL 1
43#define DROP_TAG 2
44#define BIN_QUAL 4
45#define UPDATE_NM 8
46#define UPDATE_MD 16
47#define HASH_QNM 32
48
49typedef struct cached_ref_entry {
50 char *ref;
51 hts_pos_t len;
52} cached_ref_entry;
53
54typedef struct ref_cache {
55 cached_ref_entry *refs;
56 char *last_ref;
57 hts_pos_t last_len;
58 int nref;
59 int last_tid;
60} ref_cache;
61
62int bam_aux_drop_other(bam1_t *b, uint8_t *s);
63
64static int bam_fillmd1_core(const char *ref_name, bam1_t *b, char *ref,
65 hts_pos_t ref_len, int flag, int max_nm,
66 int quiet_mode, uint32_t *skipped)
67{
68 uint8_t *seq = bam_get_seq(b);
69 uint32_t *cigar = bam_get_cigar(b);
70 bam1_core_t *c = &b->core;
71 int i, qpos, matched = 0;
72 hts_pos_t rpos;
73 kstring_t str = KS_INITIALIZE;
74 int32_t old_nm_i = -1, nm = 0;
75 uint32_t err = 0;
76
77 if (c->l_qseq == 0) {
78 if (!quiet_mode) {
79 if (ref_name) {
80 fprintf(stderr, "[bam_fillmd1] no sequence in alignment "
81 "record for '%s' at %s:%"PRIhts_pos", skipped\n",
82 bam_get_qname(b), ref_name, c->pos + 1);
83 } else {
84 fprintf(stderr, "[bam_fillmd1] no sequence in alignment "
85 "record for '%s', skipped", bam_get_qname(b));
86 }
87 }
88 if (skipped) (*skipped)++;
89 return 0;
90 }
91
92 for (i = qpos = 0, rpos = c->pos; i < c->n_cigar; ++i) {
93 int j, oplen = cigar[i]>>4, op = cigar[i]&0xf;
94 if (op == BAM_CMATCH || op == BAM_CEQUAL || op == BAM_CDIFF) {
95 for (j = 0; j < oplen; ++j) {
96 int c1, c2, z = qpos + j;
97 if (rpos+j >= ref_len || z >= c->l_qseq || ref[rpos+j] == '\0')
98 break; // out of bounds
99 c1 = bam_seqi(seq, z);
100 c2 = seq_nt16_table[(uint8_t)ref[rpos+j]];
101 if ((c1 == c2 && c1 != 15 && c2 != 15) || c1 == 0) { // a match
102 if (flag&USE_EQUAL) seq[z/2] &= (z&1)? 0xf0 : 0x0f;
103 ++matched;
104 } else {
105 err |= kputw(matched, &str) < 0;
106 err |= kputc(toupper(ref[rpos+j]), &str) < 0;
107 matched = 0; ++nm;
108 }
109 }
110 if (j < oplen) break;
111 rpos += oplen; qpos += oplen;
112 } else if (op == BAM_CDEL) {
113 err |= kputw(matched, &str) < 0;
114 err |= kputc('^', &str) < 0;
115 for (j = 0; j < oplen; ++j) {
116 if (rpos+j >= ref_len || ref[rpos+j] == '\0') break;
117 err |= kputc(toupper(ref[rpos+j]), &str) < 0;
118 }
119 matched = 0;
120 rpos += j; nm += j;
121 if (j < oplen) break;
122 } else if (op == BAM_CINS || op == BAM_CSOFT_CLIP) {
123 qpos += oplen;
124 if (op == BAM_CINS) nm += oplen;
125 } else if (op == BAM_CREF_SKIP) {
126 rpos += oplen;
127 }
128 }
129 err |= kputw(matched, &str) < 0;
130 if (err) {
131 print_error_errno("calmd", "Couldn't build new MD string");
132 goto fail;
133 }
134 // apply max_nm
135 if (max_nm > 0 && nm >= max_nm) {
136 for (i = qpos = 0, rpos = c->pos; i < c->n_cigar; ++i) {
137 int j, oplen = cigar[i]>>4, op = cigar[i]&0xf;
138 if (op == BAM_CMATCH || op == BAM_CEQUAL || op == BAM_CDIFF) {
139 for (j = 0; j < oplen; ++j) {
140 int c1, c2, z = qpos + j;
141 if (rpos+j >= ref_len || z >= c->l_qseq || ref[rpos+j] == '\0')
142 break; // out of bounds
143 c1 = bam_seqi(seq, z);
144 c2 = seq_nt16_table[(uint8_t)ref[rpos+j]];
145 if ((c1 == c2 && c1 != 15 && c2 != 15) || c1 == 0) { // a match
146 seq[z/2] |= (z&1)? 0x0f : 0xf0;
147 bam_get_qual(b)[z] = 0;
148 }
149 }
150 if (j < oplen) break;
151 rpos += oplen; qpos += oplen;
152 } else if (op == BAM_CDEL || op == BAM_CREF_SKIP) rpos += oplen;
153 else if (op == BAM_CINS || op == BAM_CSOFT_CLIP) qpos += oplen;
154 }
155 }
156 // update NM
157 if ((flag & UPDATE_NM) && !(c->flag & BAM_FUNMAP)) {
158 uint8_t *old_nm = bam_aux_get(b, "NM");
159 if (old_nm) old_nm_i = bam_aux2i(old_nm);
160 if (!old_nm) {
161 if (bam_aux_append(b, "NM", 'i', 4, (uint8_t*)&nm) < 0)
162 goto aux_fail;
163 }
164 else if (nm != old_nm_i) {
165 if (!quiet_mode) {
166 fprintf(stderr, "[bam_fillmd1] different NM for read '%s': %d -> %d\n", bam_get_qname(b), old_nm_i, nm);
167 }
168 if (bam_aux_del(b, old_nm) < 0) goto aux_fail;
169 if (bam_aux_append(b, "NM", 'i', 4, (uint8_t*)&nm) < 0)
170 goto aux_fail;
171 }
172 }
173 // update MD
174 if ((flag & UPDATE_MD) && !(c->flag & BAM_FUNMAP)) {
175 uint8_t *old_md = bam_aux_get(b, "MD");
176 if (!old_md) {
177 if (bam_aux_append(b, "MD", 'Z', str.l + 1, (uint8_t*)str.s) < 0)
178 goto aux_fail;
179 } else {
180 int is_diff = 0;
181 if (strlen((char*)old_md+1) == str.l) {
182 for (i = 0; i < str.l; ++i)
183 if (toupper(old_md[i+1]) != toupper(str.s[i]))
184 break;
185 if (i < str.l) is_diff = 1;
186 } else is_diff = 1;
187 if (is_diff) {
188 if (!quiet_mode) {
189 fprintf(stderr, "[bam_fillmd1] different MD for read '%s': '%s' -> '%s'\n", bam_get_qname(b), old_md+1, str.s);
190 }
191 if (bam_aux_del(b, old_md) < 0) goto aux_fail;
192 if (bam_aux_append(b, "MD", 'Z', str.l + 1, (uint8_t*)str.s) < 0)
193 goto aux_fail;
194 }
195 }
196 }
197
198 // drop all tags but RG
199 if (flag&DROP_TAG) {
200 uint8_t *q = bam_aux_get(b, "RG");
201 bam_aux_drop_other(b, q);
202 }
203 // reduce the resolution of base quality
204 if (flag&BIN_QUAL) {
205 uint8_t *qual = bam_get_qual(b);
206 for (i = 0; i < b->core.l_qseq; ++i)
207 if (qual[i] >= 3) qual[i] = qual[i]/10*10 + 7;
208 }
209
210 free(str.s);
211 return 0;
212
213 aux_fail:
214 if (errno == ENOMEM) {
215 print_error("calmd", "Couldn't add aux tag (too long)");
216 } else if (errno == EINVAL) {
217 print_error("calmd", "Corrupt aux data");
218 } else {
219 print_error_errno("calmd", "Couldn't add aux tag");
220 }
221 fail:
222 free(str.s);
223 return -1;
224}
225
226int bam_fillmd1(bam1_t *b, char *ref, int flag, int quiet_mode)
227{
228 return bam_fillmd1_core(NULL, b, ref, INT_MAX, flag, 0, quiet_mode, NULL);
229}
230
231// Get a new reference sequence.
232// For position-sorted inputs, the previous reference should never be
233// needed again and can be discarded to save memory. For other orderings,
234// references are stored in a cache in case they're required in the future.
235// The caching mode is turned on if the requested tid is less than the last
236// one used, indicating the file ordering doesn't match the sequence dictionary.
237static int get_ref(faidx_t *fai, sam_hdr_t *header, ref_cache *cache,
238 int tid, char **ref_out, const char **ref_name_out,
239 hts_pos_t *len_out)
240{
241 char *ref = NULL;
242 const char *ref_name;
243 hts_pos_t len = 0;
244
245 // This should only be called when tid changes
246 assert(tid != cache->last_tid);
247
248 // Array lookup, should be fast
249 ref_name = sam_hdr_tid2name(header, tid);
250 *ref_name_out = ref_name;
251
252 // Return a cached entry, if available
253 if (cache->refs && tid >= 0 && tid < cache->nref
254 && cache->refs[tid].ref) {
255 assert(cache->last_ref == NULL);
256 *ref_out = cache->refs[tid].ref;
257 *len_out = cache->refs[tid].len;
258 cache->last_tid = tid;
259 return 0;
260 }
261
262 // Try to get the reference
263 if (ref_name)
264 ref = fai_fetch64(fai, ref_name, &len);
265
266 if (!ref) {
267 // Historically, calmd doesn't worry too much about missing refs
268 *ref_out = NULL;
269 *len_out = 0;
270 return 0;
271 }
272
273 if (!cache->refs && cache->last_tid > tid) {
274 // Going backwards throught the list of tids implies
275 // a non-position-ordered file, so turn on caching mode
276 cache->nref = sam_hdr_nref(header);
277 if (cache->nref < 0) {
278 print_error("calmd", "couldn't get number of refs from header");
279 return -1;
280 }
281 if (cache->nref > 0) {
282 cache->refs = calloc(cache->nref, sizeof(cache->refs[0]));
283 if (!cache->refs) {
284 print_error_errno("calmd",
285 "couldn't allocate reference cache");
286 return -1;
287 }
288 // Add the reference we already have as the first entry
289 if (cache->last_tid >= 0 && cache->last_tid < cache->nref) {
290 cache->refs[cache->last_tid].ref = cache->last_ref;
291 cache->refs[cache->last_tid].len = cache->last_len;
292 } else {
293 free(cache->last_ref);
294 }
295 cache->last_ref = NULL;
296 }
297 }
298
299 if (cache->refs) {
300 assert(cache->last_ref == NULL); // Shouldn't be set when caching
301 // Add the new reference to the cache
302 if (tid >= 0 && tid < cache->nref) {
303 cache->refs[tid].ref = ref;
304 cache->refs[tid].len = len;
305 }
306 } else {
307 // Streaming mode - free the last ref and replace it with this one
308 free(cache->last_ref);
309 cache->last_ref = ref;
310 cache->last_len = len;
311 }
312
313 *ref_out = ref;
314 *len_out = len;
315 cache->last_tid = tid;
316 return 0;
317}
318
319static void refs_destroy(ref_cache *cache) {
320 if (cache->refs) {
321 int i;
322 assert(cache->last_ref == NULL);
323 for (i = 0; i < cache->nref; i++)
324 free(cache->refs[i].ref);
325 free(cache->refs);
326 } else {
327 free(cache->last_ref);
328 }
329}
330
331int calmd_usage(void) {
332 fprintf(stderr,
333"Usage: samtools calmd [-eubrAESQ] <aln.bam> <ref.fasta>\n"
334"Options:\n"
335" -e change identical bases to '='\n"
336" -u uncompressed BAM output (for piping)\n"
337" -b compressed BAM output\n"
338" -S ignored (input format is auto-detected)\n"
339" -A modify the quality string\n"
340" -Q use quiet mode to output less debug info to stdout\n"
341" -r compute the BQ tag (without -A) or cap baseQ by BAQ (with -A)\n"
342" -E extended BAQ for better sensitivity but lower specificity\n"
343" --no-PG do not add a PG line\n");
344
345 sam_global_opt_help(stderr, "-....@-.");
346 return 1;
347}
348
349int bam_fillmd(int argc, char *argv[])
350{
351 int c, flt_flag, ret, is_bam_out, is_uncompressed, max_nm, is_realn, capQ, baq_flag, quiet_mode, no_pg = 0;
352 hts_pos_t len = 0;
353 htsThreadPool p = {NULL, 0};
354 samFile *fp = NULL, *fpout = NULL;
355 sam_hdr_t *header = NULL;
356 faidx_t *fai = NULL;
357 char *ref = NULL, mode_w[8], *ref_file, *arg_list = NULL;
358 ref_cache refs = { NULL, NULL, 0, 0, -2 };
359 const char *ref_name = NULL;
360 bam1_t *b = NULL;
361 sam_global_args ga = SAM_GLOBAL_ARGS_INIT;
362 uint32_t skipped = 0;
363
364 static const struct option lopts[] = {
365 SAM_OPT_GLOBAL_OPTIONS('-', 0, 0, 0, 0,'@'),
366 {"no-PG", no_argument, NULL, 1},
367 { NULL, 0, NULL, 0 }
368 };
369
370 flt_flag = UPDATE_NM | UPDATE_MD;
371 is_bam_out = is_uncompressed = is_realn = max_nm = capQ = baq_flag = quiet_mode = 0;
372 strcpy(mode_w, "w");
373 while ((c = getopt_long(argc, argv, "EqQreuNhbSC:n:Ad@:", lopts, NULL)) >= 0) {
374 switch (c) {
375 case 'r': is_realn = 1; break;
376 case 'e': flt_flag |= USE_EQUAL; break;
377 case 'd': flt_flag |= DROP_TAG; break;
378 case 'q': flt_flag |= BIN_QUAL; break;
379 case 'h': flt_flag |= HASH_QNM; break;
380 case 'N': flt_flag &= ~(UPDATE_MD|UPDATE_NM); break;
381 case 'b': is_bam_out = 1; break;
382 case 'u': is_uncompressed = is_bam_out = 1; break;
383 case 'S': break;
384 case 'n': max_nm = atoi(optarg); break;
385 case 'C': capQ = atoi(optarg); break;
386 case 'A': baq_flag |= 1; break;
387 case 'E': baq_flag |= 2; break;
388 case 'Q': quiet_mode = 1; break;
389 case 1: no_pg = 1; break;
390 default: if (parse_sam_global_opt(c, optarg, lopts, &ga) == 0) break;
391 fprintf(stderr, "[bam_fillmd] unrecognized option '-%c'\n\n", c);
392 /* else fall-through */
393 case '?': return calmd_usage();
394 }
395 }
396 if (is_bam_out) strcat(mode_w, "b");
397 else strcat(mode_w, "h");
398 if (is_uncompressed) strcat(mode_w, "0");
399 if (optind + (ga.reference == NULL) >= argc)
400 return calmd_usage();
401 fp = sam_open_format(argv[optind], "r", &ga.in);
402 if (fp == NULL) {
403 print_error_errno("calmd", "Failed to open input file '%s'", argv[optind]);
404 return 1;
405 }
406
407 if (!no_pg && !(arg_list = stringify_argv(argc+1, argv-1))) {
408 print_error("calmd", "failed to create arg_list");
409 return 1;
410 }
411
412 header = sam_hdr_read(fp);
413 if (header == NULL || sam_hdr_nref(header) == 0) {
414 // NB: if we have no SQ headers but have aligned data, then this will
415 // be caught during processing with e.g.
416 // "[E::sam_parse1] no SQ lines present in the header"
417 fprintf(stderr, "[bam_fillmd] warning: input SAM does not have "
418 "header, performing a no-op.\n");
419 }
420
421 fpout = sam_open_format("-", mode_w, &ga.out);
422 if (fpout == NULL) {
423 print_error_errno("calmd", "Failed to open output");
424 goto fail;
425 }
426 if (!no_pg && sam_hdr_add_pg(header, "samtools",
427 "VN", samtools_version(),
428 arg_list ? "CL": NULL,
429 arg_list ? arg_list : NULL,
430 NULL)) {
431 print_error("calmd", "failed to add PG line to header");
432 goto fail;
433 }
434 if (sam_hdr_write(fpout, header) < 0) {
435 print_error_errno("calmd", "Failed to write sam header");
436 goto fail;
437 }
438
439 if (ga.nthreads > 0) {
440 if (!(p.pool = hts_tpool_init(ga.nthreads))) {
441 fprintf(stderr, "Error creating thread pool\n");
442 goto fail;
443 }
444 hts_set_opt(fp, HTS_OPT_THREAD_POOL, &p);
445 hts_set_opt(fpout, HTS_OPT_THREAD_POOL, &p);
446 }
447
448 ref_file = argc > optind + 1 ? argv[optind+1] : ga.reference;
449 fai = fai_load(ref_file);
450
451 if (!fai) {
452 print_error_errno("calmd", "Failed to open reference file '%s'", ref_file);
453 goto fail;
454 }
455
456 b = bam_init1();
457 if (!b) {
458 fprintf(stderr, "[bam_fillmd] Failed to allocate bam struct\n");
459 goto fail;
460 }
461 while ((ret = sam_read1(fp, header, b)) >= 0) {
462 if (b->core.tid >= 0) {
463 if (refs.last_tid != b->core.tid) {
464 if (get_ref(fai, header, &refs, b->core.tid,
465 &ref, &ref_name, &len) < 0) {
466 goto fail;
467 }
468 if (ref == 0) { // FIXME: Should this always be fatal?
469 fprintf(stderr, "[bam_fillmd] fail to find sequence '%s' in the reference.\n",
470 ref_name ? ref_name : "(unknown)");
471 if (is_realn || capQ > 10) goto fail; // Would otherwise crash
472 }
473 }
474 if (is_realn) {
475 if (sam_prob_realn(b, ref, len, baq_flag) < -3) {
476 print_error_errno("calmd", "BAQ alignment failed");
477 goto fail;
478 }
479 }
480 if (capQ > 10) {
481 int q = sam_cap_mapq(b, ref, len, capQ);
482 if (b->core.qual > q) b->core.qual = q;
483 }
484 if (ref) {
485 if (bam_fillmd1_core(ref_name, b, ref, len, flt_flag, max_nm,
486 quiet_mode, &skipped) < 0)
487 goto fail;
488 }
489 }
490 if (sam_write1(fpout, header, b) < 0) {
491 print_error_errno("calmd", "failed to write to output file");
492 goto fail;
493 }
494 }
495 if (ret < -1) {
496 fprintf(stderr, "[bam_fillmd] Error reading input.\n");
497 goto fail;
498 }
499
500 if (skipped) {
501 fprintf(stderr, "[calmd] Warning: %"PRIu32" records skipped due "
502 "to no query sequence\n",
503 skipped);
504 }
505
506 bam_destroy1(b);
507 sam_hdr_destroy(header);
508
509 free(arg_list);
510 refs_destroy(&refs);
511 fai_destroy(fai);
512 sam_close(fp);
513 if (sam_close(fpout) < 0) {
514 fprintf(stderr, "[bam_fillmd] error when closing output file\n");
515 return 1;
516 }
517 if (p.pool) hts_tpool_destroy(p.pool);
518
519 return 0;
520
521 fail:
522 free(arg_list);
523 refs_destroy(&refs);
524 if (b) bam_destroy1(b);
525 if (header) sam_hdr_destroy(header);
526 if (fai) fai_destroy(fai);
527 if (fp) sam_close(fp);
528 if (fpout) sam_close(fpout);
529 if (p.pool) hts_tpool_destroy(p.pool);
530
531 return 1;
532}