| 1 |
#include <stdio.h> |
| 2 |
#include <stdlib.h> |
| 3 |
#include <string.h> |
| 4 |
#include "bwtgap.h" |
| 5 |
#include "bwtaln.h" |
| 6 |
|
| 7 |
#ifdef USE_MALLOC_WRAPPERS |
| 8 |
# include "malloc_wrap.h" |
| 9 |
#endif |
| 10 |
|
| 11 |
#define STATE_M 0 |
| 12 |
#define STATE_I 1 |
| 13 |
#define STATE_D 2 |
| 14 |
|
| 15 |
#define aln_score(m,o,e,p) ((m)*(p)->s_mm + (o)*(p)->s_gapo + (e)*(p)->s_gape) |
| 16 |
|
| 17 |
gap_stack_t *gap_init_stack2(int max_score) |
| 18 |
{ |
| 19 |
gap_stack_t *stack; |
| 20 |
stack = (gap_stack_t*)calloc(1, sizeof(gap_stack_t)); |
| 21 |
stack->n_stacks = max_score; |
| 22 |
stack->stacks = (gap_stack1_t*)calloc(stack->n_stacks, sizeof(gap_stack1_t)); |
| 23 |
return stack; |
| 24 |
} |
| 25 |
|
| 26 |
gap_stack_t *gap_init_stack(int max_mm, int max_gapo, int max_gape, const gap_opt_t *opt) |
| 27 |
{ |
| 28 |
return gap_init_stack2(aln_score(max_mm+1, max_gapo+1, max_gape+1, opt)); |
| 29 |
} |
| 30 |
|
| 31 |
void gap_destroy_stack(gap_stack_t *stack) |
| 32 |
{ |
| 33 |
int i; |
| 34 |
for (i = 0; i != stack->n_stacks; ++i) free(stack->stacks[i].stack); |
| 35 |
free(stack->stacks); |
| 36 |
free(stack); |
| 37 |
} |
| 38 |
|
| 39 |
static void gap_reset_stack(gap_stack_t *stack) |
| 40 |
{ |
| 41 |
int i; |
| 42 |
for (i = 0; i != stack->n_stacks; ++i) |
| 43 |
stack->stacks[i].n_entries = 0; |
| 44 |
stack->best = stack->n_stacks; |
| 45 |
stack->n_entries = 0; |
| 46 |
} |
| 47 |
|
| 48 |
static inline void gap_push(gap_stack_t *stack, int i, bwtint_t k, bwtint_t l, int n_mm, int n_gapo, int n_gape, int n_ins, int n_del, |
| 49 |
int state, int is_diff, const gap_opt_t *opt) |
| 50 |
{ |
| 51 |
int score; |
| 52 |
gap_entry_t *p; |
| 53 |
gap_stack1_t *q; |
| 54 |
score = aln_score(n_mm, n_gapo, n_gape, opt); |
| 55 |
q = stack->stacks + score; |
| 56 |
if (q->n_entries == q->m_entries) { |
| 57 |
q->m_entries = q->m_entries? q->m_entries<<1 : 4; |
| 58 |
q->stack = (gap_entry_t*)realloc(q->stack, sizeof(gap_entry_t) * q->m_entries); |
| 59 |
} |
| 60 |
p = q->stack + q->n_entries; |
| 61 |
p->info = (uint32_t)score<<21 | i; p->k = k; p->l = l; |
| 62 |
p->n_mm = n_mm; p->n_gapo = n_gapo; p->n_gape = n_gape; |
| 63 |
p->n_ins = n_ins; p->n_del = n_del; |
| 64 |
p->state = state; |
| 65 |
p->last_diff_pos = is_diff? i : 0; |
| 66 |
++(q->n_entries); |
| 67 |
++(stack->n_entries); |
| 68 |
if (stack->best > score) stack->best = score; |
| 69 |
} |
| 70 |
|
| 71 |
static inline void gap_pop(gap_stack_t *stack, gap_entry_t *e) |
| 72 |
{ |
| 73 |
gap_stack1_t *q; |
| 74 |
q = stack->stacks + stack->best; |
| 75 |
*e = q->stack[q->n_entries - 1]; |
| 76 |
--(q->n_entries); |
| 77 |
--(stack->n_entries); |
| 78 |
if (q->n_entries == 0 && stack->n_entries) { // reset best |
| 79 |
int i; |
| 80 |
for (i = stack->best + 1; i < stack->n_stacks; ++i) |
| 81 |
if (stack->stacks[i].n_entries != 0) break; |
| 82 |
stack->best = i; |
| 83 |
} else if (stack->n_entries == 0) stack->best = stack->n_stacks; |
| 84 |
} |
| 85 |
|
| 86 |
static inline void gap_shadow(int x, int len, bwtint_t max, int last_diff_pos, bwt_width_t *w) |
| 87 |
{ |
| 88 |
int i, j; |
| 89 |
for (i = j = 0; i < last_diff_pos; ++i) { |
| 90 |
if (w[i].w > x) w[i].w -= x; |
| 91 |
else if (w[i].w == x) { |
| 92 |
w[i].bid = 1; |
| 93 |
w[i].w = max - (++j); |
| 94 |
} // else should not happen |
| 95 |
} |
| 96 |
} |
| 97 |
|
| 98 |
static inline int int_log2(uint32_t v) |
| 99 |
{ |
| 100 |
int c = 0; |
| 101 |
if (v & 0xffff0000u) { v >>= 16; c |= 16; } |
| 102 |
if (v & 0xff00) { v >>= 8; c |= 8; } |
| 103 |
if (v & 0xf0) { v >>= 4; c |= 4; } |
| 104 |
if (v & 0xc) { v >>= 2; c |= 2; } |
| 105 |
if (v & 0x2) c |= 1; |
| 106 |
return c; |
| 107 |
} |
| 108 |
|
| 109 |
bwt_aln1_t *bwt_match_gap(bwt_t *const bwt, int len, const ubyte_t *seq, bwt_width_t *width, |
| 110 |
bwt_width_t *seed_width, const gap_opt_t *opt, int *_n_aln, gap_stack_t *stack) |
| 111 |
{ // $seq is the reverse complement of the input read |
| 112 |
int best_score = aln_score(opt->max_diff+1, opt->max_gapo+1, opt->max_gape+1, opt); |
| 113 |
int best_diff = opt->max_diff + 1, max_diff = opt->max_diff; |
| 114 |
int best_cnt = 0; |
| 115 |
int max_entries = 0, j, _j, n_aln, m_aln; |
| 116 |
bwt_aln1_t *aln; |
| 117 |
|
| 118 |
m_aln = 4; n_aln = 0; |
| 119 |
aln = (bwt_aln1_t*)calloc(m_aln, sizeof(bwt_aln1_t)); |
| 120 |
|
| 121 |
// check whether there are too many N |
| 122 |
for (j = _j = 0; j < len; ++j) |
| 123 |
if (seq[j] > 3) ++_j; |
| 124 |
if (_j > max_diff) { |
| 125 |
*_n_aln = n_aln; |
| 126 |
return aln; |
| 127 |
} |
| 128 |
|
| 129 |
//for (j = 0; j != len; ++j) printf("#0 %d: [%d,%u]\t[%d,%u]\n", j, w[0][j].bid, w[0][j].w, w[1][j].bid, w[1][j].w); |
| 130 |
gap_reset_stack(stack); // reset stack |
| 131 |
gap_push(stack, len, 0, bwt->seq_len, 0, 0, 0, 0, 0, 0, 0, opt); |
| 132 |
|
| 133 |
while (stack->n_entries) { |
| 134 |
gap_entry_t e; |
| 135 |
int i, m, m_seed = 0, hit_found, allow_diff, allow_M, tmp; |
| 136 |
bwtint_t k, l, cnt_k[4], cnt_l[4], occ; |
| 137 |
|
| 138 |
if (max_entries < stack->n_entries) max_entries = stack->n_entries; |
| 139 |
if (stack->n_entries > opt->max_entries) break; |
| 140 |
gap_pop(stack, &e); // get the best entry |
| 141 |
k = e.k; l = e.l; // SA interval |
| 142 |
i = e.info&0xffff; // length |
| 143 |
if (!(opt->mode & BWA_MODE_NONSTOP) && e.info>>21 > best_score + opt->s_mm) break; // no need to proceed |
| 144 |
|
| 145 |
m = max_diff - (e.n_mm + e.n_gapo); |
| 146 |
if (opt->mode & BWA_MODE_GAPE) m -= e.n_gape; |
| 147 |
if (m < 0) continue; |
| 148 |
if (seed_width) { // apply seeding |
| 149 |
m_seed = opt->max_seed_diff - (e.n_mm + e.n_gapo); |
| 150 |
if (opt->mode & BWA_MODE_GAPE) m_seed -= e.n_gape; |
| 151 |
} |
| 152 |
//printf("#1\t[%d,%d,%d,%c]\t[%d,%d,%d]\t[%u,%u]\t[%u,%u]\t%d\n", stack->n_entries, a, i, "MID"[e.state], e.n_mm, e.n_gapo, e.n_gape, width[i-1].bid, width[i-1].w, k, l, e.last_diff_pos); |
| 153 |
if (i > 0 && m < width[i-1].bid) continue; |
| 154 |
|
| 155 |
// check whether a hit is found |
| 156 |
hit_found = 0; |
| 157 |
if (i == 0) hit_found = 1; |
| 158 |
else if (m == 0 && (e.state == STATE_M || (opt->mode&BWA_MODE_GAPE) || e.n_gape == opt->max_gape)) { // no diff allowed |
| 159 |
if (bwt_match_exact_alt(bwt, i, seq, &k, &l)) hit_found = 1; |
| 160 |
else continue; // no hit, skip |
| 161 |
} |
| 162 |
|
| 163 |
if (hit_found) { // action for found hits |
| 164 |
int score = aln_score(e.n_mm, e.n_gapo, e.n_gape, opt); |
| 165 |
int do_add = 1; |
| 166 |
//printf("#2 hits found: %d:(%u,%u)\n", e.n_mm+e.n_gapo, k, l); |
| 167 |
if (n_aln == 0) { |
| 168 |
best_score = score; |
| 169 |
best_diff = e.n_mm + e.n_gapo; |
| 170 |
if (opt->mode & BWA_MODE_GAPE) best_diff += e.n_gape; |
| 171 |
if (!(opt->mode & BWA_MODE_NONSTOP)) |
| 172 |
max_diff = (best_diff + 1 > opt->max_diff)? opt->max_diff : best_diff + 1; // top2 behaviour |
| 173 |
} |
| 174 |
if (score == best_score) best_cnt += l - k + 1; |
| 175 |
else if (best_cnt > opt->max_top2) break; // top2b behaviour |
| 176 |
if (e.n_gapo) { // check whether the hit has been found. this may happen when a gap occurs in a tandem repeat |
| 177 |
for (j = 0; j != n_aln; ++j) |
| 178 |
if (aln[j].k == k && aln[j].l == l) break; |
| 179 |
if (j < n_aln) do_add = 0; |
| 180 |
} |
| 181 |
if (do_add) { // append |
| 182 |
bwt_aln1_t *p; |
| 183 |
gap_shadow(l - k + 1, len, bwt->seq_len, e.last_diff_pos, width); |
| 184 |
if (n_aln == m_aln) { |
| 185 |
m_aln <<= 1; |
| 186 |
aln = (bwt_aln1_t*)realloc(aln, m_aln * sizeof(bwt_aln1_t)); |
| 187 |
memset(aln + m_aln/2, 0, m_aln/2*sizeof(bwt_aln1_t)); |
| 188 |
} |
| 189 |
p = aln + n_aln; |
| 190 |
p->n_mm = e.n_mm; p->n_gapo = e.n_gapo; p->n_gape = e.n_gape; |
| 191 |
p->n_ins = e.n_ins; p->n_del = e.n_del; |
| 192 |
p->k = k; p->l = l; |
| 193 |
p->score = score; |
| 194 |
//fprintf(stderr, "*** n_mm=%d,n_gapo=%d,n_gape=%d,n_ins=%d,n_del=%d\n", e.n_mm, e.n_gapo, e.n_gape, e.n_ins, e.n_del); |
| 195 |
++n_aln; |
| 196 |
} |
| 197 |
continue; |
| 198 |
} |
| 199 |
|
| 200 |
--i; |
| 201 |
bwt_2occ4(bwt, k - 1, l, cnt_k, cnt_l); // retrieve Occ values |
| 202 |
occ = l - k + 1; |
| 203 |
// test whether diff is allowed |
| 204 |
allow_diff = allow_M = 1; |
| 205 |
if (i > 0) { |
| 206 |
int ii = i - (len - opt->seed_len); |
| 207 |
if (width[i-1].bid > m-1) allow_diff = 0; |
| 208 |
else if (width[i-1].bid == m-1 && width[i].bid == m-1 && width[i-1].w == width[i].w) allow_M = 0; |
| 209 |
if (seed_width && ii > 0) { |
| 210 |
if (seed_width[ii-1].bid > m_seed-1) allow_diff = 0; |
| 211 |
else if (seed_width[ii-1].bid == m_seed-1 && seed_width[ii].bid == m_seed-1 |
| 212 |
&& seed_width[ii-1].w == seed_width[ii].w) allow_M = 0; |
| 213 |
} |
| 214 |
} |
| 215 |
// indels |
| 216 |
tmp = (opt->mode & BWA_MODE_LOGGAP)? int_log2(e.n_gape + e.n_gapo)/2+1 : e.n_gapo + e.n_gape; |
| 217 |
if (allow_diff && i >= opt->indel_end_skip + tmp && len - i >= opt->indel_end_skip + tmp) { |
| 218 |
if (e.state == STATE_M) { // gap open |
| 219 |
if (e.n_gapo < opt->max_gapo) { // gap open is allowed |
| 220 |
// insertion |
| 221 |
gap_push(stack, i, k, l, e.n_mm, e.n_gapo + 1, e.n_gape, e.n_ins + 1, e.n_del, STATE_I, 1, opt); |
| 222 |
// deletion |
| 223 |
for (j = 0; j != 4; ++j) { |
| 224 |
k = bwt->L2[j] + cnt_k[j] + 1; |
| 225 |
l = bwt->L2[j] + cnt_l[j]; |
| 226 |
if (k <= l) gap_push(stack, i + 1, k, l, e.n_mm, e.n_gapo + 1, e.n_gape, e.n_ins, e.n_del + 1, STATE_D, 1, opt); |
| 227 |
} |
| 228 |
} |
| 229 |
} else if (e.state == STATE_I) { // extention of an insertion |
| 230 |
if (e.n_gape < opt->max_gape) // gap extention is allowed |
| 231 |
gap_push(stack, i, k, l, e.n_mm, e.n_gapo, e.n_gape + 1, e.n_ins + 1, e.n_del, STATE_I, 1, opt); |
| 232 |
} else if (e.state == STATE_D) { // extention of a deletion |
| 233 |
if (e.n_gape < opt->max_gape) { // gap extention is allowed |
| 234 |
if (e.n_gape + e.n_gapo < max_diff || occ < opt->max_del_occ) { |
| 235 |
for (j = 0; j != 4; ++j) { |
| 236 |
k = bwt->L2[j] + cnt_k[j] + 1; |
| 237 |
l = bwt->L2[j] + cnt_l[j]; |
| 238 |
if (k <= l) gap_push(stack, i + 1, k, l, e.n_mm, e.n_gapo, e.n_gape + 1, e.n_ins, e.n_del + 1, STATE_D, 1, opt); |
| 239 |
} |
| 240 |
} |
| 241 |
} |
| 242 |
} |
| 243 |
} |
| 244 |
// mismatches |
| 245 |
if (allow_diff && allow_M) { // mismatch is allowed |
| 246 |
for (j = 1; j <= 4; ++j) { |
| 247 |
int c = (seq[i] + j) & 3; |
| 248 |
int is_mm = (j != 4 || seq[i] > 3); |
| 249 |
k = bwt->L2[c] + cnt_k[c] + 1; |
| 250 |
l = bwt->L2[c] + cnt_l[c]; |
| 251 |
if (k <= l) gap_push(stack, i, k, l, e.n_mm + is_mm, e.n_gapo, e.n_gape, e.n_ins, e.n_del, STATE_M, is_mm, opt); |
| 252 |
} |
| 253 |
} else if (seq[i] < 4) { // try exact match only |
| 254 |
int c = seq[i] & 3; |
| 255 |
k = bwt->L2[c] + cnt_k[c] + 1; |
| 256 |
l = bwt->L2[c] + cnt_l[c]; |
| 257 |
if (k <= l) gap_push(stack, i, k, l, e.n_mm, e.n_gapo, e.n_gape, e.n_ins, e.n_del, STATE_M, 0, opt); |
| 258 |
} |
| 259 |
} |
| 260 |
|
| 261 |
*_n_aln = n_aln; |
| 262 |
//fprintf(stderr, "max_entries = %d\n", max_entries); |
| 263 |
return aln; |
| 264 |
} |