| 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 <limits.h> |
| 28 |
#include "bwa.h" |
| 29 |
#include "bwamem.h" |
| 30 |
#include "bntseq.h" |
| 31 |
#include "kstring.h" |
| 32 |
|
| 33 |
/*************************** |
| 34 |
* SMEM iterator interface * |
| 35 |
***************************/ |
| 36 |
|
| 37 |
struct __smem_i { |
| 38 |
const bwt_t *bwt; |
| 39 |
const uint8_t *query; |
| 40 |
int start, len; |
| 41 |
int min_intv, max_len; |
| 42 |
uint64_t max_intv; |
| 43 |
bwtintv_v *matches; // matches; to be returned by smem_next() |
| 44 |
bwtintv_v *sub; // sub-matches inside the longest match; temporary |
| 45 |
bwtintv_v *tmpvec[2]; // temporary arrays |
| 46 |
}; |
| 47 |
|
| 48 |
smem_i *smem_itr_init(const bwt_t *bwt) |
| 49 |
{ |
| 50 |
smem_i *itr; |
| 51 |
itr = calloc(1, sizeof(smem_i)); |
| 52 |
itr->bwt = bwt; |
| 53 |
itr->tmpvec[0] = calloc(1, sizeof(bwtintv_v)); |
| 54 |
itr->tmpvec[1] = calloc(1, sizeof(bwtintv_v)); |
| 55 |
itr->matches = calloc(1, sizeof(bwtintv_v)); |
| 56 |
itr->sub = calloc(1, sizeof(bwtintv_v)); |
| 57 |
itr->min_intv = 1; |
| 58 |
itr->max_len = INT_MAX; |
| 59 |
itr->max_intv = 0; |
| 60 |
return itr; |
| 61 |
} |
| 62 |
|
| 63 |
void smem_itr_destroy(smem_i *itr) |
| 64 |
{ |
| 65 |
free(itr->tmpvec[0]->a); free(itr->tmpvec[0]); |
| 66 |
free(itr->tmpvec[1]->a); free(itr->tmpvec[1]); |
| 67 |
free(itr->matches->a); free(itr->matches); |
| 68 |
free(itr->sub->a); free(itr->sub); |
| 69 |
free(itr); |
| 70 |
} |
| 71 |
|
| 72 |
void smem_set_query(smem_i *itr, int len, const uint8_t *query) |
| 73 |
{ |
| 74 |
itr->query = query; |
| 75 |
itr->start = 0; |
| 76 |
itr->len = len; |
| 77 |
} |
| 78 |
|
| 79 |
void smem_config(smem_i *itr, int min_intv, int max_len, uint64_t max_intv) |
| 80 |
{ |
| 81 |
itr->min_intv = min_intv; |
| 82 |
itr->max_len = max_len; |
| 83 |
itr->max_intv = max_intv; |
| 84 |
} |
| 85 |
|
| 86 |
const bwtintv_v *smem_next(smem_i *itr) |
| 87 |
{ |
| 88 |
int ori_start; |
| 89 |
itr->tmpvec[0]->n = itr->tmpvec[1]->n = itr->matches->n = itr->sub->n = 0; |
| 90 |
if (itr->start >= itr->len || itr->start < 0) return 0; |
| 91 |
while (itr->start < itr->len && itr->query[itr->start] > 3) ++itr->start; // skip ambiguous bases |
| 92 |
if (itr->start == itr->len) return 0; |
| 93 |
ori_start = itr->start; |
| 94 |
itr->start = bwt_smem1a(itr->bwt, itr->len, itr->query, ori_start, itr->min_intv, itr->max_intv, itr->matches, itr->tmpvec); // search for SMEM |
| 95 |
return itr->matches; |
| 96 |
} |
| 97 |
|
| 98 |
/*********************** |
| 99 |
*** Extra functions *** |
| 100 |
***********************/ |
| 101 |
|
| 102 |
mem_alnreg_v mem_align1(const mem_opt_t *opt, const bwt_t *bwt, const bntseq_t *bns, const uint8_t *pac, int l_seq, const char *seq_) |
| 103 |
{ // the difference from mem_align1_core() is that this routine: 1) calls mem_mark_primary_se(); 2) does not modify the input sequence |
| 104 |
extern mem_alnreg_v mem_align1_core(const mem_opt_t *opt, const bwt_t *bwt, const bntseq_t *bns, const uint8_t *pac, int l_seq, char *seq, void *buf); |
| 105 |
extern void mem_mark_primary_se(const mem_opt_t *opt, int n, mem_alnreg_t *a, int64_t id); |
| 106 |
mem_alnreg_v ar; |
| 107 |
char *seq; |
| 108 |
seq = malloc(l_seq); |
| 109 |
memcpy(seq, seq_, l_seq); // makes a copy of seq_ |
| 110 |
ar = mem_align1_core(opt, bwt, bns, pac, l_seq, seq, 0); |
| 111 |
mem_mark_primary_se(opt, ar.n, ar.a, lrand48()); |
| 112 |
free(seq); |
| 113 |
return ar; |
| 114 |
} |
| 115 |
|
| 116 |
static inline int get_pri_idx(double XA_drop_ratio, const mem_alnreg_t *a, int i) |
| 117 |
{ |
| 118 |
int k = a[i].secondary_all; |
| 119 |
if (k >= 0 && a[i].score >= a[k].score * XA_drop_ratio) return k; |
| 120 |
return -1; |
| 121 |
} |
| 122 |
|
| 123 |
// Okay, returning strings is bad, but this has happened a lot elsewhere. If I have time, I need serious code cleanup. |
| 124 |
char **mem_gen_alt(const mem_opt_t *opt, const bntseq_t *bns, const uint8_t *pac, const mem_alnreg_v *a, int l_query, const char *query) // ONLY work after mem_mark_primary_se() |
| 125 |
{ |
| 126 |
int i, k, r, *cnt, tot; |
| 127 |
kstring_t *aln = 0, str = {0,0,0}; |
| 128 |
char **XA = 0, *has_alt; |
| 129 |
|
| 130 |
cnt = calloc(a->n, sizeof(int)); |
| 131 |
has_alt = calloc(a->n, 1); |
| 132 |
for (i = 0, tot = 0; i < a->n; ++i) { |
| 133 |
r = get_pri_idx(opt->XA_drop_ratio, a->a, i); |
| 134 |
if (r >= 0) { |
| 135 |
++cnt[r], ++tot; |
| 136 |
if (a->a[i].is_alt) has_alt[r] = 1; |
| 137 |
} |
| 138 |
} |
| 139 |
if (tot == 0) goto end_gen_alt; |
| 140 |
aln = calloc(a->n, sizeof(kstring_t)); |
| 141 |
for (i = 0; i < a->n; ++i) { |
| 142 |
mem_aln_t t; |
| 143 |
if ((r = get_pri_idx(opt->XA_drop_ratio, a->a, i)) < 0) continue; |
| 144 |
if (cnt[r] > opt->max_XA_hits_alt || (!has_alt[r] && cnt[r] > opt->max_XA_hits)) continue; |
| 145 |
t = mem_reg2aln(opt, bns, pac, l_query, query, &a->a[i]); |
| 146 |
str.l = 0; |
| 147 |
kputs(bns->anns[t.rid].name, &str); |
| 148 |
kputc(',', &str); kputc("+-"[t.is_rev], &str); kputl(t.pos + 1, &str); |
| 149 |
kputc(',', &str); |
| 150 |
for (k = 0; k < t.n_cigar; ++k) { |
| 151 |
kputw(t.cigar[k]>>4, &str); |
| 152 |
kputc("MIDSHN"[t.cigar[k]&0xf], &str); |
| 153 |
} |
| 154 |
kputc(',', &str); kputw(t.NM, &str); |
| 155 |
if (opt->flag & MEM_F_XB) { |
| 156 |
kputc(',', &str); |
| 157 |
kputw(t.score, &str); |
| 158 |
kputc(',', &str); |
| 159 |
kputw(t.mapq, &str); |
| 160 |
} |
| 161 |
kputc(';', &str); |
| 162 |
free(t.cigar); |
| 163 |
kputsn(str.s, str.l, &aln[r]); |
| 164 |
} |
| 165 |
XA = calloc(a->n, sizeof(char*)); |
| 166 |
for (k = 0; k < a->n; ++k) |
| 167 |
XA[k] = aln[k].s; |
| 168 |
|
| 169 |
end_gen_alt: |
| 170 |
free(has_alt); free(cnt); free(aln); free(str.s); |
| 171 |
return XA; |
| 172 |
} |