Debian Codegraph @

bwa-apache2/bwtindex.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 <unistd.h>
31 #include <time.h>
32 #include <zlib.h>
33 #include "bntseq.h"
34 #include "bwa.h"
35 #include "bwt.h"
36 #include "utils.h"
37 #include "rle.h"
38 #include "rope.h"
39
40 #ifdef _DIVBWT
41 #include "divsufsort.h"
42 #endif
43
44 #ifdef USE_MALLOC_WRAPPERS
45 # include "malloc_wrap.h"
46 #endif
47
48
49 int is_bwt(ubyte_t *T, int n);
50
51 int64_t bwa_seq_len(const char *fn_pac)
52 {
53 FILE *fp;
54 int64_t pac_len;
55 ubyte_t c;
56 fp = xopen(fn_pac, "rb");
57 err_fseek(fp, -1, SEEK_END);
58 pac_len = err_ftell(fp);
59 err_fread_noeof(&c, 1, 1, fp);
60 err_fclose(fp);
61 return (pac_len - 1) * 4 + (int)c;
62 }
63
64 bwt_t *bwt_pac2bwt(const char *fn_pac, int use_is)
65 {
66 bwt_t *bwt;
67 ubyte_t *buf, *buf2;
68 int64_t i, pac_size;
69 FILE *fp;
70
71 // initialization
72 bwt = (bwt_t*)calloc(1, sizeof(bwt_t));
73 bwt->seq_len = bwa_seq_len(fn_pac);
74 bwt->bwt_size = (bwt->seq_len + 15) >> 4;
75 fp = xopen(fn_pac, "rb");
76
77 // prepare sequence
78 pac_size = (bwt->seq_len>>2) + ((bwt->seq_len&3) == 0? 0 : 1);
79 buf2 = (ubyte_t*)calloc(pac_size, 1);
80 err_fread_noeof(buf2, 1, pac_size, fp);
81 err_fclose(fp);
82 memset(bwt->L2, 0, 5 * 4);
83 buf = (ubyte_t*)calloc(bwt->seq_len + 1, 1);
84 for (i = 0; i < bwt->seq_len; ++i) {
85 buf[i] = buf2[i>>2] >> ((3 - (i&3)) << 1) & 3;
86 ++bwt->L2[1+buf[i]];
87 }
88 for (i = 2; i <= 4; ++i) bwt->L2[i] += bwt->L2[i-1];
89 free(buf2);
90
91 // Burrows-Wheeler Transform
92 if (use_is) {
93 bwt->primary = is_bwt(buf, bwt->seq_len);
94 } else {
95 rope_t *r;
96 int64_t x;
97 rpitr_t itr;
98 const uint8_t *blk;
99
100 r = rope_init(ROPE_DEF_MAX_NODES, ROPE_DEF_BLOCK_LEN);
101 for (i = bwt->seq_len - 1, x = 0; i >= 0; --i) {
102 int c = buf[i] + 1;
103 x = rope_insert_run(r, x, c, 1, 0) + 1;
104 while (--c >= 0) x += r->c[c];
105 }
106 bwt->primary = x;
107 rope_itr_first(r, &itr);
108 x = 0;
109 while ((blk = rope_itr_next_block(&itr)) != 0) {
110 const uint8_t *q = blk + 2, *end = blk + 2 + *rle_nptr(blk);
111 while (q < end) {
112 int c = 0;
113 int64_t l;
114 rle_dec1(q, c, l);
115 for (i = 0; i < l; ++i)
116 buf[x++] = c - 1;
117 }
118 }
119 rope_destroy(r);
120 }
121 bwt->bwt = (uint32_t*)calloc(bwt->bwt_size, 4);
122 for (i = 0; i < bwt->seq_len; ++i)
123 bwt->bwt[i>>4] |= buf[i] << ((15 - (i&15)) << 1);
124 free(buf);
125 return bwt;
126 }
127
128 int bwa_pac2bwt(int argc, char *argv[]) // the "pac2bwt" command; IMPORTANT: bwt generated at this step CANNOT be used with BWA. bwtupdate is required!
129 {
130 bwt_t *bwt;
131 int c, use_is = 1;
132 while ((c = getopt(argc, argv, "d")) >= 0) {
133 switch (c) {
134 case 'd': use_is = 0; break;
135 default: return 1;
136 }
137 }
138 if (optind + 2 > argc) {
139 fprintf(stderr, "Usage: bwa pac2bwt [-d] <in.pac> <out.bwt>\n");
140 return 1;
141 }
142 bwt = bwt_pac2bwt(argv[optind], use_is);
143 bwt_dump_bwt(argv[optind+1], bwt);
144 bwt_destroy(bwt);
145 return 0;
146 }
147
148 #define bwt_B00(b, k) ((b)->bwt[(k)>>4]>>((~(k)&0xf)<<1)&3)
149
150 void bwt_bwtupdate_core(bwt_t *bwt)
151 {
152 bwtint_t i, k, c[4], n_occ;
153 uint32_t *buf;
154
155 n_occ = (bwt->seq_len + OCC_INTERVAL - 1) / OCC_INTERVAL + 1;
156 bwt->bwt_size += n_occ * sizeof(bwtint_t); // the new size
157 buf = (uint32_t*)calloc(bwt->bwt_size, 4); // will be the new bwt
158 c[0] = c[1] = c[2] = c[3] = 0;
159 for (i = k = 0; i < bwt->seq_len; ++i) {
160 if (i % OCC_INTERVAL == 0) {
161 memcpy(buf + k, c, sizeof(bwtint_t) * 4);
162 k += sizeof(bwtint_t); // in fact: sizeof(bwtint_t)=4*(sizeof(bwtint_t)/4)
163 }
164 if (i % 16 == 0) buf[k++] = bwt->bwt[i/16]; // 16 == sizeof(uint32_t)/2
165 ++c[bwt_B00(bwt, i)];
166 }
167 // the last element
168 memcpy(buf + k, c, sizeof(bwtint_t) * 4);
169 xassert(k + sizeof(bwtint_t) == bwt->bwt_size, "inconsistent bwt_size");
170 // update bwt
171 free(bwt->bwt); bwt->bwt = buf;
172 }
173
174 int bwa_bwtupdate(int argc, char *argv[]) // the "bwtupdate" command
175 {
176 bwt_t *bwt;
177 if (argc != 2) {
178 fprintf(stderr, "Usage: bwa bwtupdate <the.bwt>\n");
179 return 1;
180 }
181 bwt = bwt_restore_bwt(argv[1]);
182 bwt_bwtupdate_core(bwt);
183 bwt_dump_bwt(argv[1], bwt);
184 bwt_destroy(bwt);
185 return 0;
186 }
187
188 int bwa_bwt2sa(int argc, char *argv[]) // the "bwt2sa" command
189 {
190 bwt_t *bwt;
191 int c, sa_intv = 32;
192 while ((c = getopt(argc, argv, "i:")) >= 0) {
193 switch (c) {
194 case 'i': sa_intv = atoi(optarg); break;
195 default: return 1;
196 }
197 }
198 if (optind + 2 > argc) {
199 fprintf(stderr, "Usage: bwa bwt2sa [-i %d] <in.bwt> <out.sa>\n", sa_intv);
200 return 1;
201 }
202 bwt = bwt_restore_bwt(argv[optind]);
203 bwt_cal_sa(bwt, sa_intv);
204 bwt_dump_sa(argv[optind+1], bwt);
205 bwt_destroy(bwt);
206 return 0;
207 }
208
209 int bwa_index(int argc, char *argv[]) // the "index" command
210 {
211 extern void bwa_pac_rev_core(const char *fn, const char *fn_rev);
212
213 char *prefix = 0;
214 int c, algo_type = 0, is_64 = 0;
215
216 while ((c = getopt(argc, argv, "6a:p:b:")) >= 0) {
217 switch (c) {
218 case 'a': // if -a is not set, algo_type will be determined later
219 if (strcmp(optarg, "rb2") == 0) algo_type = 1;
220 else if (strcmp(optarg, "is") == 0) algo_type = 3;
221 else err_fatal(__func__, "unknown algorithm: '%s'.", optarg);
222 break;
223 case 'p': prefix = strdup(optarg); break;
224 case '6': is_64 = 1; break;
225 default: return 1;
226 }
227 }
228
229 if (optind + 1 > argc) {
230 fprintf(stderr, "\n");
231 fprintf(stderr, "Usage: bwa index [options] <in.fasta>\n\n");
232 fprintf(stderr, "Options: -a STR BWT construction algorithm: is or rb2 [auto]\n");
233 fprintf(stderr, " -p STR prefix of the index [same as fasta name]\n");
234 fprintf(stderr, " -6 index files named as <in.fasta>.64.* instead of <in.fasta>.* \n");
235 fprintf(stderr, "\n");
236 fprintf(stderr, "Warning: `-a bwtsw' does not work for short genomes, while `-a is' and\n");
237 fprintf(stderr, " `-a div' do not work for long genomes.\n\n");
238 return 1;
239 }
240 if (prefix == 0) {
241 prefix = malloc(strlen(argv[optind]) + 4);
242 strcpy(prefix, argv[optind]);
243 if (is_64) strcat(prefix, ".64");
244 }
245 bwa_idx_build(argv[optind], prefix, algo_type, -1);
246 free(prefix);
247 return 0;
248 }
249
250 int bwa_idx_build(const char *fa, const char *prefix, int algo_type, int block_size) // block_size NOT used on the Apache2 branch
251 {
252 extern void bwa_pac_rev_core(const char *fn, const char *fn_rev);
253
254 char *str, *str2, *str3;
255 clock_t t;
256 int64_t l_pac;
257
258 str = (char*)calloc(strlen(prefix) + 10, 1);
259 str2 = (char*)calloc(strlen(prefix) + 10, 1);
260 str3 = (char*)calloc(strlen(prefix) + 10, 1);
261
262 { // nucleotide indexing
263 gzFile fp = xzopen(fa, "r");
264 t = clock();
265 if (bwa_verbose >= 3) fprintf(stderr, "[bwa_index] Pack FASTA... ");
266 l_pac = bns_fasta2bntseq(fp, prefix, 0);
267 if (bwa_verbose >= 3) fprintf(stderr, "%.2f sec\n", (float)(clock() - t) / CLOCKS_PER_SEC);
268 err_gzclose(fp);
269 }
270 if (algo_type == 0) algo_type = l_pac > 50000000? 1 : 3; // set the algorithm for generating BWT
271 {
272 bwt_t *bwt;
273 strcpy(str, prefix); strcat(str, ".pac");
274 strcpy(str2, prefix); strcat(str2, ".bwt");
275 t = clock();
276 if (bwa_verbose >= 3) fprintf(stderr, "[bwa_index] Construct BWT for the packed sequence...\n");
277 bwt = bwt_pac2bwt(str, algo_type == 3);
278 bwt_dump_bwt(str2, bwt);
279 bwt_destroy(bwt);
280 if (bwa_verbose >= 3) fprintf(stderr, "[bwa_index] %.2f seconds elapse.\n", (float)(clock() - t) / CLOCKS_PER_SEC);
281 }
282 {
283 bwt_t *bwt;
284 strcpy(str, prefix); strcat(str, ".bwt");
285 t = clock();
286 if (bwa_verbose >= 3) fprintf(stderr, "[bwa_index] Update BWT... ");
287 bwt = bwt_restore_bwt(str);
288 bwt_bwtupdate_core(bwt);
289 bwt_dump_bwt(str, bwt);
290 bwt_destroy(bwt);
291 if (bwa_verbose >= 3) fprintf(stderr, "%.2f sec\n", (float)(clock() - t) / CLOCKS_PER_SEC);
292 }
293 {
294 gzFile fp = xzopen(fa, "r");
295 t = clock();
296 if (bwa_verbose >= 3) fprintf(stderr, "[bwa_index] Pack forward-only FASTA... ");
297 l_pac = bns_fasta2bntseq(fp, prefix, 1);
298 if (bwa_verbose >= 3) fprintf(stderr, "%.2f sec\n", (float)(clock() - t) / CLOCKS_PER_SEC);
299 err_gzclose(fp);
300 }
301 {
302 bwt_t *bwt;
303 strcpy(str, prefix); strcat(str, ".bwt");
304 strcpy(str3, prefix); strcat(str3, ".sa");
305 t = clock();
306 if (bwa_verbose >= 3) fprintf(stderr, "[bwa_index] Construct SA from BWT and Occ... ");
307 bwt = bwt_restore_bwt(str);
308 bwt_cal_sa(bwt, 32);
309 bwt_dump_sa(str3, bwt);
310 bwt_destroy(bwt);
311 if (bwa_verbose >= 3) fprintf(stderr, "%.2f sec\n", (float)(clock() - t) / CLOCKS_PER_SEC);
312 }
313 free(str3); free(str2); free(str);
314 return 0;
315 }