Debian Codegraph @

bwa-apache2/bntseq.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 <stdio.h>
28 #include <stdlib.h>
29 #include <string.h>
30 #include <zlib.h>
31 #include <unistd.h>
32 #include <errno.h>
33 #include "bntseq.h"
34 #include "utils.h"
35
36 #include "kseq.h"
37 KSEQ_DECLARE(gzFile)
38
39 #include "khash.h"
40 KHASH_MAP_INIT_STR(str, int)
41
42 #ifdef USE_MALLOC_WRAPPERS
43 # include "malloc_wrap.h"
44 #endif
45
46 unsigned char nst_nt4_table[256] = {
47 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
48 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
49 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5 /*'-'*/, 4, 4,
50 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
51 4, 0, 4, 1, 4, 4, 4, 2, 4, 4, 4, 4, 4, 4, 4, 4,
52 4, 4, 4, 4, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
53 4, 0, 4, 1, 4, 4, 4, 2, 4, 4, 4, 4, 4, 4, 4, 4,
54 4, 4, 4, 4, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
55 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
56 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
57 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
58 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
59 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
60 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
61 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
62 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4
63 };
64
65 void bns_dump(const bntseq_t *bns, const char *prefix)
66 {
67 char str[1024];
68 FILE *fp;
69 int i;
70 { // dump .ann
71 strcpy(str, prefix); strcat(str, ".ann");
72 fp = xopen(str, "w");
73 err_fprintf(fp, "%lld %d %u\n", (long long)bns->l_pac, bns->n_seqs, bns->seed);
74 for (i = 0; i != bns->n_seqs; ++i) {
75 bntann1_t *p = bns->anns + i;
76 err_fprintf(fp, "%d %s", p->gi, p->name);
77 if (p->anno[0]) err_fprintf(fp, " %s\n", p->anno);
78 else err_fprintf(fp, "\n");
79 err_fprintf(fp, "%lld %d %d\n", (long long)p->offset, p->len, p->n_ambs);
80 }
81 err_fflush(fp);
82 err_fclose(fp);
83 }
84 { // dump .amb
85 strcpy(str, prefix); strcat(str, ".amb");
86 fp = xopen(str, "w");
87 err_fprintf(fp, "%lld %d %u\n", (long long)bns->l_pac, bns->n_seqs, bns->n_holes);
88 for (i = 0; i != bns->n_holes; ++i) {
89 bntamb1_t *p = bns->ambs + i;
90 err_fprintf(fp, "%lld %d %c\n", (long long)p->offset, p->len, p->amb);
91 }
92 err_fflush(fp);
93 err_fclose(fp);
94 }
95 }
96
97 bntseq_t *bns_restore_core(const char *ann_filename, const char* amb_filename, const char* pac_filename)
98 {
99 char str[8192];
100 FILE *fp;
101 const char *fname;
102 bntseq_t *bns;
103 long long xx;
104 int i;
105 int scanres;
106 bns = (bntseq_t*)calloc(1, sizeof(bntseq_t));
107 { // read .ann
108 fp = xopen(fname = ann_filename, "r");
109 scanres = fscanf(fp, "%lld%d%u", &xx, &bns->n_seqs, &bns->seed);
110 if (scanres != 3) goto badread;
111 bns->l_pac = xx;
112 bns->anns = (bntann1_t*)calloc(bns->n_seqs, sizeof(bntann1_t));
113 for (i = 0; i < bns->n_seqs; ++i) {
114 bntann1_t *p = bns->anns + i;
115 char *q = str;
116 int c;
117 // read gi and sequence name
118 scanres = fscanf(fp, "%u%s", &p->gi, str);
119 if (scanres != 2) goto badread;
120 p->name = strdup(str);
121 // read fasta comments
122 while (q - str < sizeof(str) - 1 && (c = fgetc(fp)) != '\n' && c != EOF) *q++ = c;
123 while (c != '\n' && c != EOF) c = fgetc(fp);
124 if (c == EOF) {
125 scanres = EOF;
126 goto badread;
127 }
128 *q = 0;
129 if (q - str > 1 && strcmp(str, " (null)") != 0) p->anno = strdup(str + 1); // skip leading space
130 else p->anno = strdup("");
131 // read the rest
132 scanres = fscanf(fp, "%lld%d%d", &xx, &p->len, &p->n_ambs);
133 if (scanres != 3) goto badread;
134 p->offset = xx;
135 }
136 err_fclose(fp);
137 }
138 { // read .amb
139 int64_t l_pac;
140 int32_t n_seqs;
141 fp = xopen(fname = amb_filename, "r");
142 scanres = fscanf(fp, "%lld%d%d", &xx, &n_seqs, &bns->n_holes);
143 if (scanres != 3) goto badread;
144 l_pac = xx;
145 xassert(l_pac == bns->l_pac && n_seqs == bns->n_seqs, "inconsistent .ann and .amb files.");
146 bns->ambs = bns->n_holes? (bntamb1_t*)calloc(bns->n_holes, sizeof(bntamb1_t)) : 0;
147 for (i = 0; i < bns->n_holes; ++i) {
148 bntamb1_t *p = bns->ambs + i;
149 scanres = fscanf(fp, "%lld%d%s", &xx, &p->len, str);
150 if (scanres != 3) goto badread;
151 p->offset = xx;
152 p->amb = str[0];
153 }
154 err_fclose(fp);
155 }
156 { // open .pac
157 bns->fp_pac = xopen(pac_filename, "rb");
158 }
159 return bns;
160
161 badread:
162 if (EOF == scanres) {
163 err_fatal(__func__, "Error reading %s : %s\n", fname, ferror(fp) ? strerror(errno) : "Unexpected end of file");
164 }
165 err_fatal(__func__, "Parse error reading %s\n", fname);
166 }
167
168 bntseq_t *bns_restore(const char *prefix)
169 {
170 char ann_filename[1024], amb_filename[1024], pac_filename[1024], alt_filename[1024];
171 FILE *fp;
172 bntseq_t *bns;
173 strcat(strcpy(ann_filename, prefix), ".ann");
174 strcat(strcpy(amb_filename, prefix), ".amb");
175 strcat(strcpy(pac_filename, prefix), ".pac");
176 bns = bns_restore_core(ann_filename, amb_filename, pac_filename);
177 if (bns == 0) return 0;
178 if ((fp = fopen(strcat(strcpy(alt_filename, prefix), ".alt"), "r")) != 0) { // read .alt file if present
179 char str[1024];
180 khash_t(str) *h;
181 int c, i, absent;
182 khint_t k;
183 h = kh_init(str);
184 for (i = 0; i < bns->n_seqs; ++i) {
185 k = kh_put(str, h, bns->anns[i].name, &absent);
186 kh_val(h, k) = i;
187 }
188 i = 0;
189 while ((c = fgetc(fp)) != EOF) {
190 if (c == '\t' || c == '\n' || c == '\r') {
191 str[i] = 0;
192 if (str[0] != '@') {
193 k = kh_get(str, h, str);
194 if (k != kh_end(h))
195 bns->anns[kh_val(h, k)].is_alt = 1;
196 }
197 while (c != '\n' && c != EOF) c = fgetc(fp);
198 i = 0;
199 } else {
200 if (i >= 1022) {
201 fprintf(stderr, "[E::%s] sequence name longer than 1023 characters. Abort!\n", __func__);
202 exit(1);
203 }
204 str[i++] = c;
205 }
206 }
207 kh_destroy(str, h);
208 fclose(fp);
209 }
210 return bns;
211 }
212
213 void bns_destroy(bntseq_t *bns)
214 {
215 if (bns == 0) return;
216 else {
217 int i;
218 if (bns->fp_pac) err_fclose(bns->fp_pac);
219 free(bns->ambs);
220 for (i = 0; i < bns->n_seqs; ++i) {
221 free(bns->anns[i].name);
222 free(bns->anns[i].anno);
223 }
224 free(bns->anns);
225 free(bns);
226 }
227 }
228
229 #define _set_pac(pac, l, c) ((pac)[(l)>>2] |= (c)<<((~(l)&3)<<1))
230 #define _get_pac(pac, l) ((pac)[(l)>>2]>>((~(l)&3)<<1)&3)
231
232 static uint8_t *add1(const kseq_t *seq, bntseq_t *bns, uint8_t *pac, int64_t *m_pac, int *m_seqs, int *m_holes, bntamb1_t **q)
233 {
234 bntann1_t *p;
235 int i, lasts;
236 if (bns->n_seqs == *m_seqs) {
237 *m_seqs <<= 1;
238 bns->anns = (bntann1_t*)realloc(bns->anns, *m_seqs * sizeof(bntann1_t));
239 }
240 p = bns->anns + bns->n_seqs;
241 p->name = strdup((char*)seq->name.s);
242 p->anno = seq->comment.l > 0? strdup((char*)seq->comment.s) : strdup("(null)");
243 p->gi = 0; p->len = seq->seq.l;
244 p->offset = (bns->n_seqs == 0)? 0 : (p-1)->offset + (p-1)->len;
245 p->n_ambs = 0;
246 for (i = lasts = 0; i < seq->seq.l; ++i) {
247 int c = nst_nt4_table[(int)seq->seq.s[i]];
248 if (c >= 4) { // N
249 if (lasts == seq->seq.s[i]) { // contiguous N
250 ++(*q)->len;
251 } else {
252 if (bns->n_holes == *m_holes) {
253 (*m_holes) <<= 1;
254 bns->ambs = (bntamb1_t*)realloc(bns->ambs, (*m_holes) * sizeof(bntamb1_t));
255 }
256 *q = bns->ambs + bns->n_holes;
257 (*q)->len = 1;
258 (*q)->offset = p->offset + i;
259 (*q)->amb = seq->seq.s[i];
260 ++p->n_ambs;
261 ++bns->n_holes;
262 }
263 }
264 lasts = seq->seq.s[i];
265 { // fill buffer
266 if (c >= 4) c = lrand48()&3;
267 if (bns->l_pac == *m_pac) { // double the pac size
268 *m_pac <<= 1;
269 pac = realloc(pac, *m_pac/4);
270 memset(pac + bns->l_pac/4, 0, (*m_pac - bns->l_pac)/4);
271 }
272 _set_pac(pac, bns->l_pac, c);
273 ++bns->l_pac;
274 }
275 }
276 ++bns->n_seqs;
277 return pac;
278 }
279
280 int64_t bns_fasta2bntseq(gzFile fp_fa, const char *prefix, int for_only)
281 {
282 extern void seq_reverse(int len, ubyte_t *seq, int is_comp); // in bwaseqio.c
283 kseq_t *seq;
284 char name[1024];
285 bntseq_t *bns;
286 uint8_t *pac = 0;
287 int32_t m_seqs, m_holes;
288 int64_t ret = -1, m_pac, l;
289 bntamb1_t *q;
290 FILE *fp;
291
292 // initialization
293 seq = kseq_init(fp_fa);
294 bns = (bntseq_t*)calloc(1, sizeof(bntseq_t));
295 bns->seed = 11; // fixed seed for random generator
296 srand48(bns->seed);
297 m_seqs = m_holes = 8; m_pac = 0x10000;
298 bns->anns = (bntann1_t*)calloc(m_seqs, sizeof(bntann1_t));
299 bns->ambs = (bntamb1_t*)calloc(m_holes, sizeof(bntamb1_t));
300 pac = calloc(m_pac/4, 1);
301 q = bns->ambs;
302 strcpy(name, prefix); strcat(name, ".pac");
303 fp = xopen(name, "wb");
304 // read sequences
305 while (kseq_read(seq) >= 0) pac = add1(seq, bns, pac, &m_pac, &m_seqs, &m_holes, &q);
306 if (!for_only) { // add the reverse complemented sequence
307 int64_t ll_pac = (bns->l_pac * 2 + 3) / 4 * 4;
308 if (ll_pac > m_pac) pac = realloc(pac, ll_pac/4);
309 memset(pac + (bns->l_pac+3)/4, 0, (ll_pac - (bns->l_pac+3)/4*4) / 4);
310 for (l = bns->l_pac - 1; l >= 0; --l, ++bns->l_pac)
311 _set_pac(pac, bns->l_pac, 3-_get_pac(pac, l));
312 }
313 ret = bns->l_pac;
314 { // finalize .pac file
315 ubyte_t ct;
316 err_fwrite(pac, 1, (bns->l_pac>>2) + ((bns->l_pac&3) == 0? 0 : 1), fp);
317 // the following codes make the pac file size always (l_pac/4+1+1)
318 if (bns->l_pac % 4 == 0) {
319 ct = 0;
320 err_fwrite(&ct, 1, 1, fp);
321 }
322 ct = bns->l_pac % 4;
323 err_fwrite(&ct, 1, 1, fp);
324 // close .pac file
325 err_fflush(fp);
326 err_fclose(fp);
327 }
328 bns_dump(bns, prefix);
329 bns_destroy(bns);
330 kseq_destroy(seq);
331 free(pac);
332 return ret;
333 }
334
335 int bwa_fa2pac(int argc, char *argv[])
336 {
337 int c, for_only = 0;
338 gzFile fp;
339 while ((c = getopt(argc, argv, "f")) >= 0) {
340 switch (c) {
341 case 'f': for_only = 1; break;
342 }
343 }
344 if (argc == optind) {
345 fprintf(stderr, "Usage: bwa fa2pac [-f] <in.fasta> [<out.prefix>]\n");
346 return 1;
347 }
348 fp = xzopen(argv[optind], "r");
349 bns_fasta2bntseq(fp, (optind+1 < argc)? argv[optind+1] : argv[optind], for_only);
350 err_gzclose(fp);
351 return 0;
352 }
353
354 int bns_pos2rid(const bntseq_t *bns, int64_t pos_f)
355 {
356 int left, mid, right;
357 if (pos_f >= bns->l_pac) return -1;
358 left = 0; mid = 0; right = bns->n_seqs;
359 while (left < right) { // binary search
360 mid = (left + right) >> 1;
361 if (pos_f >= bns->anns[mid].offset) {
362 if (mid == bns->n_seqs - 1) break;
363 if (pos_f < bns->anns[mid+1].offset) break; // bracketed
364 left = mid + 1;
365 } else right = mid;
366 }
367 return mid;
368 }
369
370 int bns_intv2rid(const bntseq_t *bns, int64_t rb, int64_t re)
371 {
372 int is_rev, rid_b, rid_e;
373 if (rb < bns->l_pac && re > bns->l_pac) return -2;
374 assert(rb <= re);
375 rid_b = bns_pos2rid(bns, bns_depos(bns, rb, &is_rev));
376 rid_e = rb < re? bns_pos2rid(bns, bns_depos(bns, re - 1, &is_rev)) : rid_b;
377 return rid_b == rid_e? rid_b : -1;
378 }
379
380 int bns_cnt_ambi(const bntseq_t *bns, int64_t pos_f, int len, int *ref_id)
381 {
382 int left, mid, right, nn;
383 if (ref_id) *ref_id = bns_pos2rid(bns, pos_f);
384 left = 0; right = bns->n_holes; nn = 0;
385 while (left < right) {
386 mid = (left + right) >> 1;
387 if (pos_f >= bns->ambs[mid].offset + bns->ambs[mid].len) left = mid + 1;
388 else if (pos_f + len <= bns->ambs[mid].offset) right = mid;
389 else { // overlap
390 if (pos_f >= bns->ambs[mid].offset) {
391 nn += bns->ambs[mid].offset + bns->ambs[mid].len < pos_f + len?
392 bns->ambs[mid].offset + bns->ambs[mid].len - pos_f : len;
393 } else {
394 nn += bns->ambs[mid].offset + bns->ambs[mid].len < pos_f + len?
395 bns->ambs[mid].len : len - (bns->ambs[mid].offset - pos_f);
396 }
397 break;
398 }
399 }
400 return nn;
401 }
402
403 uint8_t *bns_get_seq(int64_t l_pac, const uint8_t *pac, int64_t beg, int64_t end, int64_t *len)
404 {
405 uint8_t *seq = 0;
406 if (end < beg) end ^= beg, beg ^= end, end ^= beg; // if end is smaller, swap
407 if (end > l_pac<<1) end = l_pac<<1;
408 if (beg < 0) beg = 0;
409 if (beg >= l_pac || end <= l_pac) {
410 int64_t k, l = 0;
411 *len = end - beg;
412 seq = malloc(end - beg);
413 if (beg >= l_pac) { // reverse strand
414 int64_t beg_f = (l_pac<<1) - 1 - end;
415 int64_t end_f = (l_pac<<1) - 1 - beg;
416 for (k = end_f; k > beg_f; --k)
417 seq[l++] = 3 - _get_pac(pac, k);
418 } else { // forward strand
419 for (k = beg; k < end; ++k)
420 seq[l++] = _get_pac(pac, k);
421 }
422 } else *len = 0; // if bridging the forward-reverse boundary, return nothing
423 return seq;
424 }
425
426 uint8_t *bns_fetch_seq(const bntseq_t *bns, const uint8_t *pac, int64_t *beg, int64_t mid, int64_t *end, int *rid)
427 {
428 int64_t far_beg, far_end, len;
429 int is_rev;
430 uint8_t *seq;
431
432 if (*end < *beg) *end ^= *beg, *beg ^= *end, *end ^= *beg; // if end is smaller, swap
433 assert(*beg <= mid && mid < *end);
434 *rid = bns_pos2rid(bns, bns_depos(bns, mid, &is_rev));
435 far_beg = bns->anns[*rid].offset;
436 far_end = far_beg + bns->anns[*rid].len;
437 if (is_rev) { // flip to the reverse strand
438 int64_t tmp = far_beg;
439 far_beg = (bns->l_pac<<1) - far_end;
440 far_end = (bns->l_pac<<1) - tmp;
441 }
442 *beg = *beg > far_beg? *beg : far_beg;
443 *end = *end < far_end? *end : far_end;
444 seq = bns_get_seq(bns->l_pac, pac, *beg, *end, &len);
445 if (seq == 0 || *end - *beg != len) {
446 fprintf(stderr, "[E::%s] begin=%ld, mid=%ld, end=%ld, len=%ld, seq=%p, rid=%d, far_beg=%ld, far_end=%ld\n",
447 __func__, (long)*beg, (long)mid, (long)*end, (long)len, seq, *rid, (long)far_beg, (long)far_end);
448 }
449 assert(seq && *end - *beg == len); // assertion failure should never happen
450 return seq;
451 }