Debian Codegraph @

bwa-apache2/bwamem_extra.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 <limits.h>
28 #include "bwa.h"
29 #include "bwamem.h"
30 #include "bntseq.h"
31 #include "kstring.h"
32
33 /***************************
34 * SMEM iterator interface *
35 ***************************/
36
37 struct __smem_i {
38 const bwt_t *bwt;
39 const uint8_t *query;
40 int start, len;
41 int min_intv, max_len;
42 uint64_t max_intv;
43 bwtintv_v *matches; // matches; to be returned by smem_next()
44 bwtintv_v *sub; // sub-matches inside the longest match; temporary
45 bwtintv_v *tmpvec[2]; // temporary arrays
46 };
47
48 smem_i *smem_itr_init(const bwt_t *bwt)
49 {
50 smem_i *itr;
51 itr = calloc(1, sizeof(smem_i));
52 itr->bwt = bwt;
53 itr->tmpvec[0] = calloc(1, sizeof(bwtintv_v));
54 itr->tmpvec[1] = calloc(1, sizeof(bwtintv_v));
55 itr->matches = calloc(1, sizeof(bwtintv_v));
56 itr->sub = calloc(1, sizeof(bwtintv_v));
57 itr->min_intv = 1;
58 itr->max_len = INT_MAX;
59 itr->max_intv = 0;
60 return itr;
61 }
62
63 void smem_itr_destroy(smem_i *itr)
64 {
65 free(itr->tmpvec[0]->a); free(itr->tmpvec[0]);
66 free(itr->tmpvec[1]->a); free(itr->tmpvec[1]);
67 free(itr->matches->a); free(itr->matches);
68 free(itr->sub->a); free(itr->sub);
69 free(itr);
70 }
71
72 void smem_set_query(smem_i *itr, int len, const uint8_t *query)
73 {
74 itr->query = query;
75 itr->start = 0;
76 itr->len = len;
77 }
78
79 void smem_config(smem_i *itr, int min_intv, int max_len, uint64_t max_intv)
80 {
81 itr->min_intv = min_intv;
82 itr->max_len = max_len;
83 itr->max_intv = max_intv;
84 }
85
86 const bwtintv_v *smem_next(smem_i *itr)
87 {
88 int ori_start;
89 itr->tmpvec[0]->n = itr->tmpvec[1]->n = itr->matches->n = itr->sub->n = 0;
90 if (itr->start >= itr->len || itr->start < 0) return 0;
91 while (itr->start < itr->len && itr->query[itr->start] > 3) ++itr->start; // skip ambiguous bases
92 if (itr->start == itr->len) return 0;
93 ori_start = itr->start;
94 itr->start = bwt_smem1a(itr->bwt, itr->len, itr->query, ori_start, itr->min_intv, itr->max_intv, itr->matches, itr->tmpvec); // search for SMEM
95 return itr->matches;
96 }
97
98 /***********************
99 *** Extra functions ***
100 ***********************/
101
102 mem_alnreg_v mem_align1(const mem_opt_t *opt, const bwt_t *bwt, const bntseq_t *bns, const uint8_t *pac, int l_seq, const char *seq_)
103 { // the difference from mem_align1_core() is that this routine: 1) calls mem_mark_primary_se(); 2) does not modify the input sequence
104 extern 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);
105 extern void mem_mark_primary_se(const mem_opt_t *opt, int n, mem_alnreg_t *a, int64_t id);
106 mem_alnreg_v ar;
107 char *seq;
108 seq = malloc(l_seq);
109 memcpy(seq, seq_, l_seq); // makes a copy of seq_
110 ar = mem_align1_core(opt, bwt, bns, pac, l_seq, seq, 0);
111 mem_mark_primary_se(opt, ar.n, ar.a, lrand48());
112 free(seq);
113 return ar;
114 }
115
116 static inline int get_pri_idx(double XA_drop_ratio, const mem_alnreg_t *a, int i)
117 {
118 int k = a[i].secondary_all;
119 if (k >= 0 && a[i].score >= a[k].score * XA_drop_ratio) return k;
120 return -1;
121 }
122
123 // Okay, returning strings is bad, but this has happened a lot elsewhere. If I have time, I need serious code cleanup.
124 char **mem_gen_alt(const mem_opt_t *opt, const bntseq_t *bns, const uint8_t *pac, const mem_alnreg_v *a, int l_query, const char *query) // ONLY work after mem_mark_primary_se()
125 {
126 int i, k, r, *cnt, tot;
127 kstring_t *aln = 0, str = {0,0,0};
128 char **XA = 0, *has_alt;
129
130 cnt = calloc(a->n, sizeof(int));
131 has_alt = calloc(a->n, 1);
132 for (i = 0, tot = 0; i < a->n; ++i) {
133 r = get_pri_idx(opt->XA_drop_ratio, a->a, i);
134 if (r >= 0) {
135 ++cnt[r], ++tot;
136 if (a->a[i].is_alt) has_alt[r] = 1;
137 }
138 }
139 if (tot == 0) goto end_gen_alt;
140 aln = calloc(a->n, sizeof(kstring_t));
141 for (i = 0; i < a->n; ++i) {
142 mem_aln_t t;
143 if ((r = get_pri_idx(opt->XA_drop_ratio, a->a, i)) < 0) continue;
144 if (cnt[r] > opt->max_XA_hits_alt || (!has_alt[r] && cnt[r] > opt->max_XA_hits)) continue;
145 t = mem_reg2aln(opt, bns, pac, l_query, query, &a->a[i]);
146 str.l = 0;
147 kputs(bns->anns[t.rid].name, &str);
148 kputc(',', &str); kputc("+-"[t.is_rev], &str); kputl(t.pos + 1, &str);
149 kputc(',', &str);
150 for (k = 0; k < t.n_cigar; ++k) {
151 kputw(t.cigar[k]>>4, &str);
152 kputc("MIDSHN"[t.cigar[k]&0xf], &str);
153 }
154 kputc(',', &str); kputw(t.NM, &str);
155 if (opt->flag & MEM_F_XB) {
156 kputc(',', &str);
157 kputw(t.score, &str);
158 kputc(',', &str);
159 kputw(t.mapq, &str);
160 }
161 kputc(';', &str);
162 free(t.cigar);
163 kputsn(str.s, str.l, &aln[r]);
164 }
165 XA = calloc(a->n, sizeof(char*));
166 for (k = 0; k < a->n; ++k)
167 XA[k] = aln[k].s;
168
169 end_gen_alt:
170 free(has_alt); free(cnt); free(aln); free(str.s);
171 return XA;
172 }