Debian Codegraph @

bwa-apache2/bwtaln.c

raw
1 #include <stdio.h>
2 #include <unistd.h>
3 #include <math.h>
4 #include <stdlib.h>
5 #include <string.h>
6 #include <time.h>
7 #include <stdint.h>
8 #ifdef HAVE_CONFIG_H
9 #include "config.h"
10 #endif
11 #include "bwtaln.h"
12 #include "bwtgap.h"
13 #include "utils.h"
14 #include "bwa.h"
15
16 #ifdef HAVE_PTHREAD
17 #include <pthread.h>
18 #endif
19
20 #ifdef USE_MALLOC_WRAPPERS
21 # include "malloc_wrap.h"
22 #endif
23
24 gap_opt_t *gap_init_opt()
25 {
26 gap_opt_t *o;
27 o = (gap_opt_t*)calloc(1, sizeof(gap_opt_t));
28 /* IMPORTANT: s_mm*10 should be about the average base error
29 rate. Voilating this requirement will break pairing! */
30 o->s_mm = 3; o->s_gapo = 11; o->s_gape = 4;
31 o->max_diff = -1; o->max_gapo = 1; o->max_gape = 6;
32 o->indel_end_skip = 5; o->max_del_occ = 10; o->max_entries = 2000000;
33 o->mode = BWA_MODE_GAPE | BWA_MODE_COMPREAD;
34 o->seed_len = 32; o->max_seed_diff = 2;
35 o->fnr = 0.04;
36 o->n_threads = 1;
37 o->max_top2 = 30;
38 o->trim_qual = 0;
39 return o;
40 }
41
42 int bwa_cal_maxdiff(int l, double err, double thres)
43 {
44 double elambda = exp(-l * err);
45 double sum, y = 1.0;
46 int k, x = 1;
47 for (k = 1, sum = elambda; k < 1000; ++k) {
48 y *= l * err;
49 x *= k;
50 sum += elambda * y / x;
51 if (1.0 - sum < thres) return k;
52 }
53 return 2;
54 }
55
56 // width must be filled as zero
57 int bwt_cal_width(const bwt_t *bwt, int len, const ubyte_t *str, bwt_width_t *width)
58 {
59 bwtint_t k, l, ok, ol;
60 int i, bid;
61 bid = 0;
62 k = 0; l = bwt->seq_len;
63 for (i = 0; i < len; ++i) {
64 ubyte_t c = str[i];
65 if (c < 4) {
66 bwt_2occ(bwt, k - 1, l, c, &ok, &ol);
67 k = bwt->L2[c] + ok + 1;
68 l = bwt->L2[c] + ol;
69 }
70 if (k > l || c > 3) { // then restart
71 k = 0;
72 l = bwt->seq_len;
73 ++bid;
74 }
75 width[i].w = l - k + 1;
76 width[i].bid = bid;
77 }
78 width[len].w = 0;
79 width[len].bid = ++bid;
80 return bid;
81 }
82
83 void bwa_cal_sa_reg_gap(int tid, bwt_t *const bwt, int n_seqs, bwa_seq_t *seqs, const gap_opt_t *opt)
84 {
85 int i, j, max_l = 0, max_len;
86 gap_stack_t *stack;
87 bwt_width_t *w, *seed_w;
88 gap_opt_t local_opt = *opt;
89
90 // initiate priority stack
91 for (i = max_len = 0; i != n_seqs; ++i)
92 if (seqs[i].len > max_len) max_len = seqs[i].len;
93 if (opt->fnr > 0.0) local_opt.max_diff = bwa_cal_maxdiff(max_len, BWA_AVG_ERR, opt->fnr);
94 if (local_opt.max_diff < local_opt.max_gapo) local_opt.max_gapo = local_opt.max_diff;
95 stack = gap_init_stack(local_opt.max_diff, local_opt.max_gapo, local_opt.max_gape, &local_opt);
96
97 seed_w = (bwt_width_t*)calloc(opt->seed_len+1, sizeof(bwt_width_t));
98 w = 0;
99 for (i = 0; i != n_seqs; ++i) {
100 bwa_seq_t *p = seqs + i;
101 #ifdef HAVE_PTHREAD
102 if (i % opt->n_threads != tid) continue;
103 #endif
104 p->sa = 0; p->type = BWA_TYPE_NO_MATCH; p->c1 = p->c2 = 0; p->n_aln = 0; p->aln = 0;
105 if (max_l < p->len) {
106 max_l = p->len;
107 w = (bwt_width_t*)realloc(w, (max_l + 1) * sizeof(bwt_width_t));
108 memset(w, 0, (max_l + 1) * sizeof(bwt_width_t));
109 }
110 bwt_cal_width(bwt, p->len, p->seq, w);
111 if (opt->fnr > 0.0) local_opt.max_diff = bwa_cal_maxdiff(p->len, BWA_AVG_ERR, opt->fnr);
112 local_opt.seed_len = opt->seed_len < p->len? opt->seed_len : 0x7fffffff;
113 if (p->len > opt->seed_len)
114 bwt_cal_width(bwt, opt->seed_len, p->seq + (p->len - opt->seed_len), seed_w);
115 // core function
116 for (j = 0; j < p->len; ++j) // we need to complement
117 p->seq[j] = p->seq[j] > 3? 4 : 3 - p->seq[j];
118 p->aln = bwt_match_gap(bwt, p->len, p->seq, w, p->len <= opt->seed_len? 0 : seed_w, &local_opt, &p->n_aln, stack);
119 //fprintf(stderr, "mm=%lld,ins=%lld,del=%lld,gapo=%lld\n", p->aln->n_mm, p->aln->n_ins, p->aln->n_del, p->aln->n_gapo);
120 // clean up the unused data in the record
121 free(p->name); free(p->seq); free(p->rseq); free(p->qual);
122 p->name = 0; p->seq = p->rseq = p->qual = 0;
123 }
124 free(seed_w); free(w);
125 gap_destroy_stack(stack);
126 }
127
128 #ifdef HAVE_PTHREAD
129 typedef struct {
130 int tid;
131 bwt_t *bwt;
132 int n_seqs;
133 bwa_seq_t *seqs;
134 const gap_opt_t *opt;
135 } thread_aux_t;
136
137 static void *worker(void *data)
138 {
139 thread_aux_t *d = (thread_aux_t*)data;
140 bwa_cal_sa_reg_gap(d->tid, d->bwt, d->n_seqs, d->seqs, d->opt);
141 return 0;
142 }
143 #endif
144
145 bwa_seqio_t *bwa_open_reads(int mode, const char *fn_fa)
146 {
147 bwa_seqio_t *ks;
148 if (mode & BWA_MODE_BAM) { // open BAM
149 int which = 0;
150 if (mode & BWA_MODE_BAM_SE) which |= 4;
151 if (mode & BWA_MODE_BAM_READ1) which |= 1;
152 if (mode & BWA_MODE_BAM_READ2) which |= 2;
153 if (which == 0) which = 7; // then read all reads
154 ks = bwa_bam_open(fn_fa, which);
155 } else ks = bwa_seq_open(fn_fa);
156 return ks;
157 }
158
159 void bwa_aln_core(const char *prefix, const char *fn_fa, const gap_opt_t *opt)
160 {
161 int i, n_seqs;
162 long long tot_seqs = 0;
163 bwa_seq_t *seqs;
164 bwa_seqio_t *ks;
165 clock_t t;
166 bwt_t *bwt;
167
168 // initialization
169 ks = bwa_open_reads(opt->mode, fn_fa);
170
171 { // load BWT
172 char *str = (char*)calloc(strlen(prefix) + 10, 1);
173 strcpy(str, prefix); strcat(str, ".bwt"); bwt = bwt_restore_bwt(str);
174 free(str);
175 }
176
177 // core loop
178 err_fwrite(SAI_MAGIC, 1, 4, stdout);
179 err_fwrite(opt, sizeof(gap_opt_t), 1, stdout);
180 while ((seqs = bwa_read_seq(ks, 0x40000, &n_seqs, opt->mode, opt->trim_qual)) != 0) {
181 tot_seqs += n_seqs;
182 t = clock();
183
184 fprintf(stderr, "[bwa_aln_core] calculate SA coordinate... ");
185
186 #ifdef HAVE_PTHREAD
187 if (opt->n_threads <= 1) { // no multi-threading at all
188 bwa_cal_sa_reg_gap(0, bwt, n_seqs, seqs, opt);
189 } else {
190 pthread_t *tid;
191 pthread_attr_t attr;
192 thread_aux_t *data;
193 int j;
194 pthread_attr_init(&attr);
195 pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_JOINABLE);
196 data = (thread_aux_t*)calloc(opt->n_threads, sizeof(thread_aux_t));
197 tid = (pthread_t*)calloc(opt->n_threads, sizeof(pthread_t));
198 for (j = 0; j < opt->n_threads; ++j) {
199 data[j].tid = j; data[j].bwt = bwt;
200 data[j].n_seqs = n_seqs; data[j].seqs = seqs; data[j].opt = opt;
201 pthread_create(&tid[j], &attr, worker, data + j);
202 }
203 for (j = 0; j < opt->n_threads; ++j) pthread_join(tid[j], 0);
204 free(data); free(tid);
205 }
206 #else
207 bwa_cal_sa_reg_gap(0, bwt, n_seqs, seqs, opt);
208 #endif
209
210 fprintf(stderr, "%.2f sec\n", (float)(clock() - t) / CLOCKS_PER_SEC);
211
212 t = clock();
213 fprintf(stderr, "[bwa_aln_core] write to the disk... ");
214 for (i = 0; i < n_seqs; ++i) {
215 bwa_seq_t *p = seqs + i;
216 err_fwrite(&p->n_aln, 4, 1, stdout);
217 if (p->n_aln) err_fwrite(p->aln, sizeof(bwt_aln1_t), p->n_aln, stdout);
218 }
219 fprintf(stderr, "%.2f sec\n", (float)(clock() - t) / CLOCKS_PER_SEC);
220
221 bwa_free_read_seq(n_seqs, seqs);
222 fprintf(stderr, "[bwa_aln_core] %lld sequences have been processed.\n", tot_seqs);
223 }
224
225 // destroy
226 bwt_destroy(bwt);
227 bwa_seq_close(ks);
228 }
229
230 int bwa_aln(int argc, char *argv[])
231 {
232 int c, opte = -1;
233 gap_opt_t *opt;
234 char *prefix;
235
236 opt = gap_init_opt();
237 while ((c = getopt(argc, argv, "n:o:e:i:d:l:k:LR:m:t:NM:O:E:q:f:b012IYB:")) >= 0) {
238 switch (c) {
239 case 'n':
240 if (strstr(optarg, ".")) opt->fnr = atof(optarg), opt->max_diff = -1;
241 else opt->max_diff = atoi(optarg), opt->fnr = -1.0;
242 break;
243 case 'o': opt->max_gapo = atoi(optarg); break;
244 case 'e': opte = atoi(optarg); break;
245 case 'M': opt->s_mm = atoi(optarg); break;
246 case 'O': opt->s_gapo = atoi(optarg); break;
247 case 'E': opt->s_gape = atoi(optarg); break;
248 case 'd': opt->max_del_occ = atoi(optarg); break;
249 case 'i': opt->indel_end_skip = atoi(optarg); break;
250 case 'l': opt->seed_len = atoi(optarg); break;
251 case 'k': opt->max_seed_diff = atoi(optarg); break;
252 case 'm': opt->max_entries = atoi(optarg); break;
253 case 't': opt->n_threads = atoi(optarg); break;
254 case 'L': opt->mode |= BWA_MODE_LOGGAP; break;
255 case 'R': opt->max_top2 = atoi(optarg); break;
256 case 'q': opt->trim_qual = atoi(optarg); break;
257 case 'N': opt->mode |= BWA_MODE_NONSTOP; opt->max_top2 = 0x7fffffff; break;
258 case 'f': xreopen(optarg, "wb", stdout); break;
259 case 'b': opt->mode |= BWA_MODE_BAM; break;
260 case '0': opt->mode |= BWA_MODE_BAM_SE; break;
261 case '1': opt->mode |= BWA_MODE_BAM_READ1; break;
262 case '2': opt->mode |= BWA_MODE_BAM_READ2; break;
263 case 'I': opt->mode |= BWA_MODE_IL13; break;
264 case 'Y': opt->mode |= BWA_MODE_CFY; break;
265 case 'B': opt->mode |= atoi(optarg) << 24; break;
266 default: return 1;
267 }
268 }
269 if (opte > 0) {
270 opt->max_gape = opte;
271 opt->mode &= ~BWA_MODE_GAPE;
272 }
273
274 if (optind + 2 > argc) {
275 fprintf(stderr, "\n");
276 fprintf(stderr, "Usage: bwa aln [options] <prefix> <in.fq>\n\n");
277 fprintf(stderr, "Options: -n NUM max #diff (int) or missing prob under %.2f err rate (float) [%.2f]\n",
278 BWA_AVG_ERR, opt->fnr);
279 fprintf(stderr, " -o INT maximum number or fraction of gap opens [%d]\n", opt->max_gapo);
280 fprintf(stderr, " -e INT maximum number of gap extensions, -1 for disabling long gaps [-1]\n");
281 fprintf(stderr, " -i INT do not put an indel within INT bp towards the ends [%d]\n", opt->indel_end_skip);
282 fprintf(stderr, " -d INT maximum occurrences for extending a long deletion [%d]\n", opt->max_del_occ);
283 fprintf(stderr, " -l INT seed length [%d]\n", opt->seed_len);
284 fprintf(stderr, " -k INT maximum differences in the seed [%d]\n", opt->max_seed_diff);
285 fprintf(stderr, " -m INT maximum entries in the queue [%d]\n", opt->max_entries);
286 fprintf(stderr, " -t INT number of threads [%d]\n", opt->n_threads);
287 fprintf(stderr, " -M INT mismatch penalty [%d]\n", opt->s_mm);
288 fprintf(stderr, " -O INT gap open penalty [%d]\n", opt->s_gapo);
289 fprintf(stderr, " -E INT gap extension penalty [%d]\n", opt->s_gape);
290 fprintf(stderr, " -R INT stop searching when there are >INT equally best hits [%d]\n", opt->max_top2);
291 fprintf(stderr, " -q INT quality threshold for read trimming down to %dbp [%d]\n", BWA_MIN_RDLEN, opt->trim_qual);
292 fprintf(stderr, " -f FILE file to write output to instead of stdout\n");
293 fprintf(stderr, " -B INT length of barcode\n");
294 fprintf(stderr, " -L log-scaled gap penalty for long deletions\n");
295 fprintf(stderr, " -N non-iterative mode: search for all n-difference hits (slooow)\n");
296 fprintf(stderr, " -I the input is in the Illumina 1.3+ FASTQ-like format\n");
297 fprintf(stderr, " -b the input read file is in the BAM format\n");
298 fprintf(stderr, " -0 use single-end reads only (effective with -b)\n");
299 fprintf(stderr, " -1 use the 1st read in a pair (effective with -b)\n");
300 fprintf(stderr, " -2 use the 2nd read in a pair (effective with -b)\n");
301 fprintf(stderr, " -Y filter Casava-filtered sequences\n");
302 fprintf(stderr, "\n");
303 return 1;
304 }
305 if (opt->fnr > 0.0) {
306 int i, k;
307 for (i = 17, k = 0; i <= 250; ++i) {
308 int l = bwa_cal_maxdiff(i, BWA_AVG_ERR, opt->fnr);
309 if (l != k) fprintf(stderr, "[bwa_aln] %dbp reads: max_diff = %d\n", i, l);
310 k = l;
311 }
312 }
313 if ((prefix = bwa_idx_infer_prefix(argv[optind])) == 0) {
314 fprintf(stderr, "[%s] fail to locate the index\n", __func__);
315 free(opt);
316 return 1;
317 }
318 bwa_aln_core(prefix, argv[optind+1], opt);
319 free(opt); free(prefix);
320 return 0;
321 }