Debian Codegraph @

contrib/SeqLib/bwa/bwt.h

raw
1 /* The MIT License
2
3 Copyright (c) 2008 Genome Research Ltd (GRL).
4
5 Permission is hereby granted, free of charge, to any person obtaining
6 a copy of this software and associated documentation files (the
7 "Software"), to deal in the Software without restriction, including
8 without limitation the rights to use, copy, modify, merge, publish,
9 distribute, sublicense, and/or sell copies of the Software, and to
10 permit persons to whom the Software is furnished to do so, subject to
11 the following conditions:
12
13 The above copyright notice and this permission notice shall be
14 included in all copies or substantial portions of the Software.
15
16 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
17 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
18 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
19 NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
20 BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
21 ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
22 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
23 SOFTWARE.
24 */
25
26 /* Contact: Heng Li <[email protected]> */
27
28 #ifndef BWA_BWT_H
29 #define BWA_BWT_H
30
31 #include <stdint.h>
32 #include <stddef.h>
33
34 // requirement: (OCC_INTERVAL%16 == 0); please DO NOT change this line because some part of the code assume OCC_INTERVAL=0x80
35 #define OCC_INTV_SHIFT 7
36 #define OCC_INTERVAL (1LL<<OCC_INTV_SHIFT)
37 #define OCC_INTV_MASK (OCC_INTERVAL - 1)
38
39 #ifndef BWA_UBYTE
40 #define BWA_UBYTE
41 typedef unsigned char ubyte_t;
42 #endif
43
44 typedef uint64_t bwtint_t;
45
46 typedef struct {
47 bwtint_t primary; // S^{-1}(0), or the primary index of BWT
48 bwtint_t L2[5]; // C(), cumulative count
49 bwtint_t seq_len; // sequence length
50 bwtint_t bwt_size; // size of bwt, about seq_len/4
51 uint32_t *bwt; // BWT
52 // occurance array, separated to two parts
53 uint32_t cnt_table[256];
54 // suffix array
55 int sa_intv;
56 bwtint_t n_sa;
57 bwtint_t *sa;
58 } bwt_t;
59
60 typedef struct {
61 bwtint_t x[3], info;
62 } bwtintv_t;
63
64 typedef struct { size_t n, m; bwtintv_t *a; } bwtintv_v;
65
66 /* For general OCC_INTERVAL, the following is correct:
67 #define bwt_bwt(b, k) ((b)->bwt[(k)/OCC_INTERVAL * (OCC_INTERVAL/(sizeof(uint32_t)*8/2) + sizeof(bwtint_t)/4*4) + sizeof(bwtint_t)/4*4 + (k)%OCC_INTERVAL/16])
68 #define bwt_occ_intv(b, k) ((b)->bwt + (k)/OCC_INTERVAL * (OCC_INTERVAL/(sizeof(uint32_t)*8/2) + sizeof(bwtint_t)/4*4)
69 */
70
71 // The following two lines are ONLY correct when OCC_INTERVAL==0x80
72 #define bwt_bwt(b, k) ((b)->bwt[((k)>>7<<4) + sizeof(bwtint_t) + (((k)&0x7f)>>4)])
73 #define bwt_occ_intv(b, k) ((b)->bwt + ((k)>>7<<4))
74
75 /* retrieve a character from the $-removed BWT string. Note that
76 * bwt_t::bwt is not exactly the BWT string and therefore this macro is
77 * called bwt_B0 instead of bwt_B */
78 #define bwt_B0(b, k) (bwt_bwt(b, k)>>((~(k)&0xf)<<1)&3)
79
80 #define bwt_set_intv(bwt, c, ik) ((ik).x[0] = (bwt)->L2[(int)(c)]+1, (ik).x[2] = (bwt)->L2[(int)(c)+1]-(bwt)->L2[(int)(c)], (ik).x[1] = (bwt)->L2[3-(c)]+1, (ik).info = 0)
81
82 #ifdef __cplusplus
83 extern "C" {
84 #endif
85
86 void bwt_dump_bwt(const char *fn, const bwt_t *bwt);
87 void bwt_dump_sa(const char *fn, const bwt_t *bwt);
88
89 bwt_t *bwt_restore_bwt(const char *fn);
90 void bwt_restore_sa(const char *fn, bwt_t *bwt);
91
92 void bwt_destroy(bwt_t *bwt);
93
94 void bwt_bwtgen(const char *fn_pac, const char *fn_bwt); // from BWT-SW
95 void bwt_bwtgen2(const char *fn_pac, const char *fn_bwt, int block_size); // from BWT-SW
96 void bwt_cal_sa(bwt_t *bwt, int intv);
97
98 void bwt_bwtupdate_core(bwt_t *bwt);
99
100 bwtint_t bwt_occ(const bwt_t *bwt, bwtint_t k, ubyte_t c);
101 void bwt_occ4(const bwt_t *bwt, bwtint_t k, bwtint_t cnt[4]);
102 bwtint_t bwt_sa(const bwt_t *bwt, bwtint_t k);
103
104 // more efficient version of bwt_occ/bwt_occ4 for retrieving two close Occ values
105 void bwt_gen_cnt_table(bwt_t *bwt);
106 void bwt_2occ(const bwt_t *bwt, bwtint_t k, bwtint_t l, ubyte_t c, bwtint_t *ok, bwtint_t *ol);
107 void bwt_2occ4(const bwt_t *bwt, bwtint_t k, bwtint_t l, bwtint_t cntk[4], bwtint_t cntl[4]);
108
109 int bwt_match_exact(const bwt_t *bwt, int len, const ubyte_t *str, bwtint_t *sa_begin, bwtint_t *sa_end);
110 int bwt_match_exact_alt(const bwt_t *bwt, int len, const ubyte_t *str, bwtint_t *k0, bwtint_t *l0);
111
112 /**
113 * Extend bi-SA-interval _ik_
114 */
115 void bwt_extend(const bwt_t *bwt, const bwtintv_t *ik, bwtintv_t ok[4], int is_back);
116
117 /**
118 * Given a query _q_, collect potential SMEMs covering position _x_ and store them in _mem_.
119 * Return the end of the longest exact match starting from _x_.
120 */
121 int bwt_smem1(const bwt_t *bwt, int len, const uint8_t *q, int x, int min_intv, bwtintv_v *mem, bwtintv_v *tmpvec[2]);
122 int bwt_smem1a(const bwt_t *bwt, int len, const uint8_t *q, int x, int min_intv, uint64_t max_intv, bwtintv_v *mem, bwtintv_v *tmpvec[2]);
123
124 int bwt_seed_strategy1(const bwt_t *bwt, int len, const uint8_t *q, int x, int min_len, int max_intv, bwtintv_t *mem);
125
126 #ifdef __cplusplus
127 }
128 #endif
129
130 #endif