Debian Codegraph @

bwa-apache2/pemerge.c

raw
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <unistd.h>
4 #include <string.h>
5 #include <zlib.h>
6 #include <pthread.h>
7 #include <errno.h>
8 #include "ksw.h"
9 #include "kseq.h"
10 #include "kstring.h"
11 #include "bwa.h"
12 #include "utils.h"
13 KSEQ_DECLARE(gzFile)
14
15 #ifdef USE_MALLOC_WRAPPERS
16 # include "malloc_wrap.h"
17 #endif
18
19 #define MAX_SCORE_RATIO 0.9f
20 #define MAX_ERR 8
21
22 static const char *err_msg[MAX_ERR+1] = {
23 "successful merges",
24 "low-scoring pairs",
25 "pairs where the best SW alignment is not an overlap (long left end)",
26 "pairs where the best SW alignment is not an overlap (long right end)",
27 "pairs with large 2nd best SW score",
28 "pairs with gapped overlap",
29 "pairs where the end-to-end alignment is inconsistent with SW",
30 "pairs potentially with tandem overlaps",
31 "pairs with high sum of errors"
32 };
33
34 typedef struct {
35 int a, b, q, r, w;
36 int q_def, q_thres;
37 int T;
38 int chunk_size;
39 int n_threads;
40 int flag; // bit 1: print merged; 2: print unmerged
41 int8_t mat[25];
42 } pem_opt_t;
43
44 pem_opt_t *pem_opt_init()
45 {
46 pem_opt_t *opt;
47 opt = calloc(1, sizeof(pem_opt_t));
48 opt->a = 5; opt->b = 4; opt->q = 2, opt->r = 17; opt->w = 20;
49 opt->T = opt->a * 10;
50 opt->q_def = 20;
51 opt->q_thres = 70;
52 opt->chunk_size = 10000000;
53 opt->n_threads = 1;
54 opt->flag = 3;
55 bwa_fill_scmat(opt->a, opt->b, opt->mat);
56 return opt;
57 }
58
59 int bwa_pemerge(const pem_opt_t *opt, bseq1_t x[2])
60 {
61 uint8_t *s[2], *q[2], *seq, *qual;
62 int i, xtra, l, l_seq, sum_q, ret = 0;
63 kswr_t r;
64
65 s[0] = malloc(x[0].l_seq); q[0] = malloc(x[0].l_seq);
66 s[1] = malloc(x[1].l_seq); q[1] = malloc(x[1].l_seq);
67 for (i = 0; i < x[0].l_seq; ++i) {
68 int c = x[0].seq[i];
69 s[0][i] = c < 0 || c > 127? 4 : c <= 4? c : nst_nt4_table[c];
70 q[0][i] = x[0].qual? x[0].qual[i] - 33 : opt->q_def;
71 }
72 for (i = 0; i < x[1].l_seq; ++i) {
73 int c = x[1].seq[x[1].l_seq - 1 - i];
74 c = c < 0 || c > 127? 4 : c < 4? c : nst_nt4_table[c];
75 s[1][i] = c < 4? 3 - c : 4;
76 q[1][i] = x[1].qual? x[1].qual[x[1].l_seq - 1 - i] - 33 : opt->q_def;
77 }
78
79 xtra = KSW_XSTART | KSW_XSUBO;
80 r = ksw_align(x[1].l_seq, s[1], x[0].l_seq, s[0], 5, opt->mat, opt->q, opt->r, xtra, 0);
81 ++r.qe; ++r.te; // change to the half-close-half-open coordinates
82
83 if (r.score < opt->T) { ret = -1; goto pem_ret; } // poor alignment
84 if (r.tb < r.qb) { ret = -2; goto pem_ret; } // no enough space for the left end
85 if (x[0].l_seq - r.te > x[1].l_seq - r.qe) { ret = -3; goto pem_ret; } // no enough space for the right end
86 if ((double)r.score2 / r.score >= MAX_SCORE_RATIO) { ret = -4; goto pem_ret; } // the second best score is too large
87 if (r.qe - r.qb != r.te - r.tb) { ret = -5; goto pem_ret; } // we do not allow gaps
88
89 { // test tandem match; O(n^2)
90 int max_m, max_m2, min_l, max_l, max_l2;
91 max_m = max_m2 = 0; max_l = max_l2 = 0;
92 min_l = x[0].l_seq < x[1].l_seq? x[0].l_seq : x[1].l_seq;
93 for (l = 1; l < min_l; ++l) {
94 int m = 0, o = x[0].l_seq - l;
95 uint8_t *s0o = &s[0][o], *s1 = s[1];
96 for (i = 0; i < l; ++i) // TODO: in principle, this can be done with SSE2. It is the bottleneck!
97 m += opt->mat[(s1[i]<<2) + s1[i] + s0o[i]]; // equivalent to s[1][i]*5 + s[0][o+i]
98 if (m > max_m) max_m2 = max_m, max_m = m, max_l2 = max_l, max_l = l;
99 else if (m > max_m2) max_m2 = m, max_l2 = l;
100 }
101 if (max_m < opt->T || max_l != x[0].l_seq - (r.tb - r.qb)) { ret = -6; goto pem_ret; }
102 if (max_l2 < max_l && max_m2 >= opt->T && (double)(max_m2 + (max_l - max_l2) * opt->a) / max_m >= MAX_SCORE_RATIO) {
103 ret = -7; goto pem_ret;
104 }
105 if (max_l2 > max_l && (double)max_m2 / max_m >= MAX_SCORE_RATIO) { ret = -7; goto pem_ret; }
106 }
107
108 l = x[0].l_seq - (r.tb - r.qb); // length to merge
109 l_seq = x[0].l_seq + x[1].l_seq - l;
110 seq = malloc(l_seq + 1);
111 qual = malloc(l_seq + 1);
112 memcpy(seq, s[0], x[0].l_seq); memcpy(seq + x[0].l_seq, &s[1][l], x[1].l_seq - l);
113 memcpy(qual, q[0], x[0].l_seq); memcpy(qual + x[0].l_seq, &q[1][l], x[1].l_seq - l);
114 for (i = 0, sum_q = 0; i < l; ++i) {
115 int k = x[0].l_seq - l + i;
116 if (s[0][k] == 4) { // ambiguous
117 seq[k] = s[1][i];
118 qual[k] = q[1][i];
119 } else if (s[1][i] == 4) { // do nothing
120 } else if (s[0][k] == s[1][i]) {
121 qual[k] = qual[k] > q[1][i]? qual[k] : q[1][i];
122 } else { // s[0][k] != s[1][i] and neither is N
123 int qq = q[0][k] < q[1][i]? q[0][k] : q[1][i];
124 sum_q += qq >= 3? qq<<1 : 1;
125 seq[k] = q[0][k] > q[1][i]? s[0][k] : s[1][i];
126 qual[k] = abs((int)q[0][k] - (int)q[1][i]);
127 }
128 }
129 if (sum_q>>1 > opt->q_thres) { // too many mismatches
130 free(seq); free(qual);
131 ret = -8; goto pem_ret;
132 }
133
134 for (i = 0; i < l_seq; ++i) seq[i] = "ACGTN"[(int)seq[i]], qual[i] += 33;
135 seq[l_seq] = qual[l_seq] = 0;
136
137 free(x[1].name); free(x[1].seq); free(x[1].qual); free(x[1].comment);
138 memset(&x[1], 0, sizeof(bseq1_t));
139 free(x[0].seq); free(x[0].qual);
140 x[0].l_seq = l_seq; x[0].seq = (char*)seq; x[0].qual = (char*)qual;
141
142 pem_ret:
143 free(s[0]); free(s[1]); free(q[0]); free(q[1]);
144 return ret;
145 }
146
147 static inline void print_bseq(const bseq1_t *s, int rn)
148 {
149 err_putchar(s->qual? '@' : '>');
150 err_fputs(s->name, stdout);
151 if (rn == 1 || rn == 2) {
152 err_putchar('/'); err_putchar('0' + rn); err_putchar('\n');
153 } else err_puts(" merged");
154 err_puts(s->seq);
155 if (s->qual) {
156 err_puts("+"); err_puts(s->qual);
157 }
158 }
159
160 typedef struct {
161 int n, start;
162 bseq1_t *seqs;
163 int64_t cnt[MAX_ERR+1];
164 const pem_opt_t *opt;
165 } worker_t;
166
167 void *worker(void *data)
168 {
169 worker_t *w = (worker_t*)data;
170 int i;
171 for (i = w->start; i < w->n>>1; i += w->opt->n_threads)
172 ++w->cnt[-bwa_pemerge(w->opt, &w->seqs[i<<1])];
173 return 0;
174 }
175
176 static void process_seqs(const pem_opt_t *opt, int n_, bseq1_t *seqs, int64_t cnt[MAX_ERR+1])
177 {
178 int i, j, n = n_>>1<<1;
179 worker_t *w;
180
181 w = calloc(opt->n_threads, sizeof(worker_t));
182 for (i = 0; i < opt->n_threads; ++i) {
183 worker_t *p = &w[i];
184 p->start = i; p->n = n;
185 p->opt = opt;
186 p->seqs = seqs;
187 }
188 if (opt->n_threads == 1) {
189 worker(w);
190 } else {
191 pthread_t *tid;
192 tid = (pthread_t*)calloc(opt->n_threads, sizeof(pthread_t));
193 for (i = 0; i < opt->n_threads; ++i) pthread_create(&tid[i], 0, worker, &w[i]);
194 for (i = 0; i < opt->n_threads; ++i) pthread_join(tid[i], 0);
195 free(tid);
196 }
197 for (i = 0; i < opt->n_threads; ++i) {
198 worker_t *p = &w[i];
199 for (j = 0; j <= MAX_ERR; ++j) cnt[j] += p->cnt[j];
200 }
201 free(w);
202 for (i = 0; i < n>>1; ++i) {
203 if (seqs[i<<1|1].l_seq != 0) {
204 if (opt->flag&2) {
205 print_bseq(&seqs[i<<1|0], 1);
206 print_bseq(&seqs[i<<1|1], 2);
207 }
208 } else if (opt->flag&1)
209 print_bseq(&seqs[i<<1|0], 0);
210 }
211 for (i = 0; i < n; ++i) {
212 bseq1_t *s = &seqs[i];
213 free(s->name); free(s->seq); free(s->qual); free(s->comment);
214 }
215 }
216
217 int main_pemerge(int argc, char *argv[])
218 {
219 int c, flag = 0, i, n, min_ovlp = 10;
220 int64_t cnt[MAX_ERR+1];
221 bseq1_t *bseq;
222 gzFile fp, fp2 = 0;
223 kseq_t *ks, *ks2 = 0;
224 pem_opt_t *opt;
225
226 opt = pem_opt_init();
227 while ((c = getopt(argc, argv, "muQ:t:T:")) >= 0) {
228 if (c == 'm') flag |= 1;
229 else if (c == 'u') flag |= 2;
230 else if (c == 'Q') opt->q_thres = atoi(optarg);
231 else if (c == 't') opt->n_threads = atoi(optarg);
232 else if (c == 'T') min_ovlp = atoi(optarg);
233 else return 1;
234 }
235 if (flag == 0) flag = 3;
236 opt->flag = flag;
237 opt->T = opt->a * min_ovlp;
238
239 if (optind == argc) {
240 fprintf(stderr, "\n");
241 fprintf(stderr, "Usage: bwa pemerge [-mu] <read1.fq> [read2.fq]\n\n");
242 fprintf(stderr, "Options: -m output merged reads only\n");
243 fprintf(stderr, " -u output unmerged reads only\n");
244 fprintf(stderr, " -t INT number of threads [%d]\n", opt->n_threads);
245 fprintf(stderr, " -T INT minimum end overlap [%d]\n", min_ovlp);
246 fprintf(stderr, " -Q INT max sum of errors [%d]\n", opt->q_thres);
247 fprintf(stderr, "\n");
248 free(opt);
249 return 1;
250 }
251
252 fp = strcmp(argv[optind], "-")? gzopen(argv[optind], "r") : gzdopen(fileno(stdin), "r");
253 if (NULL == fp) {
254 fprintf(stderr, "Couldn't open %s : %s\n",
255 strcmp(argv[optind], "-") ? argv[optind] : "stdin",
256 errno ? strerror(errno) : "Out of memory");
257 exit(EXIT_FAILURE);
258 }
259 ks = kseq_init(fp);
260 if (optind + 1 < argc) {
261 fp2 = strcmp(argv[optind+1], "-")? gzopen(argv[optind+1], "r") : gzdopen(fileno(stdin), "r");
262 if (NULL == fp) {
263 fprintf(stderr, "Couldn't open %s : %s\n",
264 strcmp(argv[optind+1], "-") ? argv[optind+1] : "stdin",
265 errno ? strerror(errno) : "Out of memory");
266 exit(EXIT_FAILURE);
267 }
268 ks2 = kseq_init(fp2);
269 }
270
271 memset(cnt, 0, 8 * (MAX_ERR+1));
272 while ((bseq = bseq_read(opt->n_threads * opt->chunk_size, &n, ks, ks2)) != 0) {
273 process_seqs(opt, n, bseq, cnt);
274 free(bseq);
275 }
276
277 fprintf(stderr, "%12ld %s\n", (long)cnt[0], err_msg[0]);
278 for (i = 1; i <= MAX_ERR; ++i)
279 fprintf(stderr, "%12ld %s\n", (long)cnt[i], err_msg[i]);
280 kseq_destroy(ks);
281 err_gzclose(fp);
282 if (ks2) {
283 kseq_destroy(ks2);
284 err_gzclose(fp2);
285 }
286 free(opt);
287
288 err_fflush(stdout);
289
290 return 0;
291 }