Source code

Download source archive ↓

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}