| 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 <stdlib.h> |
| 28 |
#include <string.h> |
| 29 |
#include <stdio.h> |
| 30 |
#include <math.h> |
| 31 |
#include "kstring.h" |
| 32 |
#include "bwamem.h" |
| 33 |
#include "kvec.h" |
| 34 |
#include "utils.h" |
| 35 |
#include "ksw.h" |
| 36 |
|
| 37 |
#ifdef USE_MALLOC_WRAPPERS |
| 38 |
# include "malloc_wrap.h" |
| 39 |
#endif |
| 40 |
|
| 41 |
|
| 42 |
#define MIN_RATIO 0.8 |
| 43 |
#define MIN_DIR_CNT 10 |
| 44 |
#define MIN_DIR_RATIO 0.05 |
| 45 |
#define OUTLIER_BOUND 2.0 |
| 46 |
#define MAPPING_BOUND 3.0 |
| 47 |
#define MAX_STDDEV 4.0 |
| 48 |
|
| 49 |
static inline int mem_infer_dir(int64_t l_pac, int64_t b1, int64_t b2, int64_t *dist) |
| 50 |
{ |
| 51 |
int64_t p2; |
| 52 |
int r1 = (b1 >= l_pac), r2 = (b2 >= l_pac); |
| 53 |
p2 = r1 == r2? b2 : (l_pac<<1) - 1 - b2; // p2 is the coordinate of read 2 on the read 1 strand |
| 54 |
*dist = p2 > b1? p2 - b1 : b1 - p2; |
| 55 |
return (r1 == r2? 0 : 1) ^ (p2 > b1? 0 : 3); |
| 56 |
} |
| 57 |
|
| 58 |
static int cal_sub(const mem_opt_t *opt, mem_alnreg_v *r) |
| 59 |
{ |
| 60 |
int j; |
| 61 |
for (j = 1; j < r->n; ++j) { // choose unique alignment |
| 62 |
int b_max = r->a[j].qb > r->a[0].qb? r->a[j].qb : r->a[0].qb; |
| 63 |
int e_min = r->a[j].qe < r->a[0].qe? r->a[j].qe : r->a[0].qe; |
| 64 |
if (e_min > b_max) { // have overlap |
| 65 |
int min_l = r->a[j].qe - r->a[j].qb < r->a[0].qe - r->a[0].qb? r->a[j].qe - r->a[j].qb : r->a[0].qe - r->a[0].qb; |
| 66 |
if (e_min - b_max >= min_l * opt->mask_level) break; // significant overlap |
| 67 |
} |
| 68 |
} |
| 69 |
return j < r->n? r->a[j].score : opt->min_seed_len * opt->a; |
| 70 |
} |
| 71 |
|
| 72 |
void mem_pestat(const mem_opt_t *opt, int64_t l_pac, int n, const mem_alnreg_v *regs, mem_pestat_t pes[4]) |
| 73 |
{ |
| 74 |
int i, d, max; |
| 75 |
uint64_v isize[4]; |
| 76 |
memset(pes, 0, 4 * sizeof(mem_pestat_t)); |
| 77 |
memset(isize, 0, sizeof(kvec_t(int)) * 4); |
| 78 |
for (i = 0; i < n>>1; ++i) { |
| 79 |
int dir; |
| 80 |
int64_t is; |
| 81 |
mem_alnreg_v *r[2]; |
| 82 |
r[0] = (mem_alnreg_v*)®s[i<<1|0]; |
| 83 |
r[1] = (mem_alnreg_v*)®s[i<<1|1]; |
| 84 |
if (r[0]->n == 0 || r[1]->n == 0) continue; |
| 85 |
if (cal_sub(opt, r[0]) > MIN_RATIO * r[0]->a[0].score) continue; |
| 86 |
if (cal_sub(opt, r[1]) > MIN_RATIO * r[1]->a[0].score) continue; |
| 87 |
if (r[0]->a[0].rid != r[1]->a[0].rid) continue; // not on the same chr |
| 88 |
dir = mem_infer_dir(l_pac, r[0]->a[0].rb, r[1]->a[0].rb, &is); |
| 89 |
if (is && is <= opt->max_ins) kv_push(uint64_t, isize[dir], is); |
| 90 |
} |
| 91 |
if (bwa_verbose >= 3) fprintf(stderr, "[M::%s] # candidate unique pairs for (FF, FR, RF, RR): (%ld, %ld, %ld, %ld)\n", __func__, isize[0].n, isize[1].n, isize[2].n, isize[3].n); |
| 92 |
for (d = 0; d < 4; ++d) { // TODO: this block is nearly identical to the one in bwtsw2_pair.c. It would be better to merge these two. |
| 93 |
mem_pestat_t *r = &pes[d]; |
| 94 |
uint64_v *q = &isize[d]; |
| 95 |
int p25, p50, p75, x; |
| 96 |
if (q->n < MIN_DIR_CNT) { |
| 97 |
fprintf(stderr, "[M::%s] skip orientation %c%c as there are not enough pairs\n", __func__, "FR"[d>>1&1], "FR"[d&1]); |
| 98 |
r->failed = 1; |
| 99 |
free(q->a); |
| 100 |
continue; |
| 101 |
} else fprintf(stderr, "[M::%s] analyzing insert size distribution for orientation %c%c...\n", __func__, "FR"[d>>1&1], "FR"[d&1]); |
| 102 |
ks_introsort_64(q->n, q->a); |
| 103 |
p25 = q->a[(int)(.25 * q->n + .499)]; |
| 104 |
p50 = q->a[(int)(.50 * q->n + .499)]; |
| 105 |
p75 = q->a[(int)(.75 * q->n + .499)]; |
| 106 |
r->low = (int)(p25 - OUTLIER_BOUND * (p75 - p25) + .499); |
| 107 |
if (r->low < 1) r->low = 1; |
| 108 |
r->high = (int)(p75 + OUTLIER_BOUND * (p75 - p25) + .499); |
| 109 |
fprintf(stderr, "[M::%s] (25, 50, 75) percentile: (%d, %d, %d)\n", __func__, p25, p50, p75); |
| 110 |
fprintf(stderr, "[M::%s] low and high boundaries for computing mean and std.dev: (%d, %d)\n", __func__, r->low, r->high); |
| 111 |
for (i = x = 0, r->avg = 0; i < q->n; ++i) |
| 112 |
if (q->a[i] >= r->low && q->a[i] <= r->high) |
| 113 |
r->avg += q->a[i], ++x; |
| 114 |
r->avg /= x; |
| 115 |
for (i = 0, r->std = 0; i < q->n; ++i) |
| 116 |
if (q->a[i] >= r->low && q->a[i] <= r->high) |
| 117 |
r->std += (q->a[i] - r->avg) * (q->a[i] - r->avg); |
| 118 |
r->std = sqrt(r->std / x); |
| 119 |
fprintf(stderr, "[M::%s] mean and std.dev: (%.2f, %.2f)\n", __func__, r->avg, r->std); |
| 120 |
r->low = (int)(p25 - MAPPING_BOUND * (p75 - p25) + .499); |
| 121 |
r->high = (int)(p75 + MAPPING_BOUND * (p75 - p25) + .499); |
| 122 |
if (r->low > r->avg - MAX_STDDEV * r->std) r->low = (int)(r->avg - MAX_STDDEV * r->std + .499); |
| 123 |
if (r->high < r->avg + MAX_STDDEV * r->std) r->high = (int)(r->avg + MAX_STDDEV * r->std + .499); |
| 124 |
if (r->low < 1) r->low = 1; |
| 125 |
fprintf(stderr, "[M::%s] low and high boundaries for proper pairs: (%d, %d)\n", __func__, r->low, r->high); |
| 126 |
free(q->a); |
| 127 |
} |
| 128 |
for (d = 0, max = 0; d < 4; ++d) |
| 129 |
max = max > isize[d].n? max : isize[d].n; |
| 130 |
for (d = 0; d < 4; ++d) |
| 131 |
if (pes[d].failed == 0 && isize[d].n < max * MIN_DIR_RATIO) { |
| 132 |
pes[d].failed = 1; |
| 133 |
fprintf(stderr, "[M::%s] skip orientation %c%c\n", __func__, "FR"[d>>1&1], "FR"[d&1]); |
| 134 |
} |
| 135 |
} |
| 136 |
|
| 137 |
int mem_matesw(const mem_opt_t *opt, const bntseq_t *bns, const uint8_t *pac, const mem_pestat_t pes[4], const mem_alnreg_t *a, int l_ms, const uint8_t *ms, mem_alnreg_v *ma) |
| 138 |
{ |
| 139 |
extern int mem_sort_dedup_patch(const mem_opt_t *opt, const bntseq_t *bns, const uint8_t *pac, uint8_t *query, int n, mem_alnreg_t *a); |
| 140 |
int64_t l_pac = bns->l_pac; |
| 141 |
int i, r, skip[4], n = 0, rid; |
| 142 |
for (r = 0; r < 4; ++r) |
| 143 |
skip[r] = pes[r].failed? 1 : 0; |
| 144 |
for (i = 0; i < ma->n; ++i) { // check which orinentation has been found |
| 145 |
int64_t dist; |
| 146 |
r = mem_infer_dir(l_pac, a->rb, ma->a[i].rb, &dist); |
| 147 |
if (dist >= pes[r].low && dist <= pes[r].high) |
| 148 |
skip[r] = 1; |
| 149 |
} |
| 150 |
if (skip[0] + skip[1] + skip[2] + skip[3] == 4) return 0; // consistent pair exist; no need to perform SW |
| 151 |
for (r = 0; r < 4; ++r) { |
| 152 |
int is_rev, is_larger; |
| 153 |
uint8_t *seq, *rev = 0, *ref = 0; |
| 154 |
int64_t rb, re; |
| 155 |
if (skip[r]) continue; |
| 156 |
is_rev = (r>>1 != (r&1)); // whether to reverse complement the mate |
| 157 |
is_larger = !(r>>1); // whether the mate has larger coordinate |
| 158 |
if (is_rev) { |
| 159 |
rev = malloc(l_ms); // this is the reverse complement of $ms |
| 160 |
for (i = 0; i < l_ms; ++i) rev[l_ms - 1 - i] = ms[i] < 4? 3 - ms[i] : 4; |
| 161 |
seq = rev; |
| 162 |
} else seq = (uint8_t*)ms; |
| 163 |
if (!is_rev) { |
| 164 |
rb = is_larger? a->rb + pes[r].low : a->rb - pes[r].high; |
| 165 |
re = (is_larger? a->rb + pes[r].high: a->rb - pes[r].low) + l_ms; // if on the same strand, end position should be larger to make room for the seq length |
| 166 |
} else { |
| 167 |
rb = (is_larger? a->rb + pes[r].low : a->rb - pes[r].high) - l_ms; // similarly on opposite strands |
| 168 |
re = is_larger? a->rb + pes[r].high: a->rb - pes[r].low; |
| 169 |
} |
| 170 |
if (rb < 0) rb = 0; |
| 171 |
if (re > l_pac<<1) re = l_pac<<1; |
| 172 |
if (rb < re) ref = bns_fetch_seq(bns, pac, &rb, (rb+re)>>1, &re, &rid); |
| 173 |
if (a->rid == rid && re - rb >= opt->min_seed_len) { // no funny things happening |
| 174 |
kswr_t aln; |
| 175 |
mem_alnreg_t b; |
| 176 |
int tmp, xtra = KSW_XSUBO | KSW_XSTART | (l_ms * opt->a < 250? KSW_XBYTE : 0) | (opt->min_seed_len * opt->a); |
| 177 |
aln = ksw_align2(l_ms, seq, re - rb, ref, 5, opt->mat, opt->o_del, opt->e_del, opt->o_ins, opt->e_ins, xtra, 0); |
| 178 |
memset(&b, 0, sizeof(mem_alnreg_t)); |
| 179 |
if (aln.score >= opt->min_seed_len && aln.qb >= 0) { // something goes wrong if aln.qb < 0 |
| 180 |
b.rid = a->rid; |
| 181 |
b.is_alt = a->is_alt; |
| 182 |
b.qb = is_rev? l_ms - (aln.qe + 1) : aln.qb; |
| 183 |
b.qe = is_rev? l_ms - aln.qb : aln.qe + 1; |
| 184 |
b.rb = is_rev? (l_pac<<1) - (rb + aln.te + 1) : rb + aln.tb; |
| 185 |
b.re = is_rev? (l_pac<<1) - (rb + aln.tb) : rb + aln.te + 1; |
| 186 |
b.score = aln.score; |
| 187 |
b.csub = aln.score2; |
| 188 |
b.secondary = -1; |
| 189 |
b.seedcov = (b.re - b.rb < b.qe - b.qb? b.re - b.rb : b.qe - b.qb) >> 1; |
| 190 |
// printf("*** %d, [%lld,%lld], %d:%d, (%lld,%lld), (%lld,%lld) == (%lld,%lld)\n", aln.score, rb, re, is_rev, is_larger, a->rb, a->re, ma->a[0].rb, ma->a[0].re, b.rb, b.re); |
| 191 |
kv_push(mem_alnreg_t, *ma, b); // make room for a new element |
| 192 |
// move b s.t. ma is sorted |
| 193 |
for (i = 0; i < ma->n - 1; ++i) // find the insertion point |
| 194 |
if (ma->a[i].score < b.score) break; |
| 195 |
tmp = i; |
| 196 |
for (i = ma->n - 1; i > tmp; --i) ma->a[i] = ma->a[i-1]; |
| 197 |
ma->a[i] = b; |
| 198 |
} |
| 199 |
++n; |
| 200 |
} |
| 201 |
if (n) ma->n = mem_sort_dedup_patch(opt, 0, 0, 0, ma->n, ma->a); |
| 202 |
if (rev) free(rev); |
| 203 |
free(ref); |
| 204 |
} |
| 205 |
return n; |
| 206 |
} |
| 207 |
|
| 208 |
int mem_pair(const mem_opt_t *opt, const bntseq_t *bns, const uint8_t *pac, const mem_pestat_t pes[4], bseq1_t s[2], mem_alnreg_v a[2], int id, int *sub, int *n_sub, int z[2], int n_pri[2]) |
| 209 |
{ |
| 210 |
pair64_v v, u; |
| 211 |
int r, i, k, y[4], ret; // y[] keeps the last hit |
| 212 |
int64_t l_pac = bns->l_pac; |
| 213 |
kv_init(v); kv_init(u); |
| 214 |
for (r = 0; r < 2; ++r) { // loop through read number |
| 215 |
for (i = 0; i < n_pri[r]; ++i) { |
| 216 |
pair64_t key; |
| 217 |
mem_alnreg_t *e = &a[r].a[i]; |
| 218 |
key.x = e->rb < l_pac? e->rb : (l_pac<<1) - 1 - e->rb; // forward position |
| 219 |
key.x = (uint64_t)e->rid<<32 | (key.x - bns->anns[e->rid].offset); |
| 220 |
key.y = (uint64_t)e->score << 32 | i << 2 | (e->rb >= l_pac)<<1 | r; |
| 221 |
kv_push(pair64_t, v, key); |
| 222 |
} |
| 223 |
} |
| 224 |
ks_introsort_128(v.n, v.a); |
| 225 |
y[0] = y[1] = y[2] = y[3] = -1; |
| 226 |
//for (i = 0; i < v.n; ++i) printf("[%d]\t%d\t%c%ld\n", i, (int)(v.a[i].y&1)+1, "+-"[v.a[i].y>>1&1], (long)v.a[i].x); |
| 227 |
for (i = 0; i < v.n; ++i) { |
| 228 |
for (r = 0; r < 2; ++r) { // loop through direction |
| 229 |
int dir = r<<1 | (v.a[i].y>>1&1), which; |
| 230 |
if (pes[dir].failed) continue; // invalid orientation |
| 231 |
which = r<<1 | ((v.a[i].y&1)^1); |
| 232 |
if (y[which] < 0) continue; // no previous hits |
| 233 |
for (k = y[which]; k >= 0; --k) { // TODO: this is a O(n^2) solution in the worst case; remember to check if this loop takes a lot of time (I doubt) |
| 234 |
int64_t dist; |
| 235 |
int q; |
| 236 |
double ns; |
| 237 |
pair64_t *p; |
| 238 |
if ((v.a[k].y&3) != which) continue; |
| 239 |
dist = (int64_t)v.a[i].x - v.a[k].x; |
| 240 |
//printf("%d: %lld\n", k, dist); |
| 241 |
if (dist > pes[dir].high) break; |
| 242 |
if (dist < pes[dir].low) continue; |
| 243 |
ns = (dist - pes[dir].avg) / pes[dir].std; |
| 244 |
q = (int)((v.a[i].y>>32) + (v.a[k].y>>32) + .721 * log(2. * erfc(fabs(ns) * M_SQRT1_2)) * opt->a + .499); // .721 = 1/log(4) |
| 245 |
if (q < 0) q = 0; |
| 246 |
p = kv_pushp(pair64_t, u); |
| 247 |
p->y = (uint64_t)k<<32 | i; |
| 248 |
p->x = (uint64_t)q<<32 | (hash_64(p->y ^ id<<8) & 0xffffffffU); |
| 249 |
//printf("[%lld,%lld]\t%d\tdist=%ld\n", v.a[k].x, v.a[i].x, q, (long)dist); |
| 250 |
} |
| 251 |
} |
| 252 |
y[v.a[i].y&3] = i; |
| 253 |
} |
| 254 |
if (u.n) { // found at least one proper pair |
| 255 |
int tmp = opt->a + opt->b; |
| 256 |
tmp = tmp > opt->o_del + opt->e_del? tmp : opt->o_del + opt->e_del; |
| 257 |
tmp = tmp > opt->o_ins + opt->e_ins? tmp : opt->o_ins + opt->e_ins; |
| 258 |
ks_introsort_128(u.n, u.a); |
| 259 |
i = u.a[u.n-1].y >> 32; k = u.a[u.n-1].y << 32 >> 32; |
| 260 |
z[v.a[i].y&1] = v.a[i].y<<32>>34; // index of the best pair |
| 261 |
z[v.a[k].y&1] = v.a[k].y<<32>>34; |
| 262 |
ret = u.a[u.n-1].x >> 32; |
| 263 |
*sub = u.n > 1? u.a[u.n-2].x>>32 : 0; |
| 264 |
for (i = (long)u.n - 2, *n_sub = 0; i >= 0; --i) |
| 265 |
if (*sub - (int)(u.a[i].x>>32) <= tmp) ++*n_sub; |
| 266 |
} else ret = 0, *sub = 0, *n_sub = 0; |
| 267 |
free(u.a); free(v.a); |
| 268 |
return ret; |
| 269 |
} |
| 270 |
|
| 271 |
void mem_aln2sam(const mem_opt_t *opt, const bntseq_t *bns, kstring_t *str, bseq1_t *s, int n, const mem_aln_t *list, int which, const mem_aln_t *m); |
| 272 |
void mem_reorder_primary5(int T, mem_alnreg_v *a); |
| 273 |
|
| 274 |
#define raw_mapq(diff, a) ((int)(6.02 * (diff) / (a) + .499)) |
| 275 |
|
| 276 |
int mem_sam_pe(const mem_opt_t *opt, const bntseq_t *bns, const uint8_t *pac, const mem_pestat_t pes[4], uint64_t id, bseq1_t s[2], mem_alnreg_v a[2]) |
| 277 |
{ |
| 278 |
extern int mem_mark_primary_se(const mem_opt_t *opt, int n, mem_alnreg_t *a, int64_t id); |
| 279 |
extern int mem_approx_mapq_se(const mem_opt_t *opt, const mem_alnreg_t *a); |
| 280 |
extern void mem_reg2sam(const mem_opt_t *opt, const bntseq_t *bns, const uint8_t *pac, bseq1_t *s, mem_alnreg_v *a, int extra_flag, const mem_aln_t *m); |
| 281 |
extern 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); |
| 282 |
|
| 283 |
int n = 0, i, j, z[2], o, subo, n_sub, extra_flag = 1, n_pri[2], n_aa[2]; |
| 284 |
kstring_t str; |
| 285 |
mem_aln_t h[2], g[2], aa[2][2]; |
| 286 |
|
| 287 |
str.l = str.m = 0; str.s = 0; |
| 288 |
memset(h, 0, sizeof(mem_aln_t) * 2); |
| 289 |
memset(g, 0, sizeof(mem_aln_t) * 2); |
| 290 |
n_aa[0] = n_aa[1] = 0; |
| 291 |
if (!(opt->flag & MEM_F_NO_RESCUE)) { // then perform SW for the best alignment |
| 292 |
mem_alnreg_v b[2]; |
| 293 |
kv_init(b[0]); kv_init(b[1]); |
| 294 |
for (i = 0; i < 2; ++i) |
| 295 |
for (j = 0; j < a[i].n; ++j) |
| 296 |
if (a[i].a[j].score >= a[i].a[0].score - opt->pen_unpaired) |
| 297 |
kv_push(mem_alnreg_t, b[i], a[i].a[j]); |
| 298 |
for (i = 0; i < 2; ++i) |
| 299 |
for (j = 0; j < b[i].n && j < opt->max_matesw; ++j) |
| 300 |
n += mem_matesw(opt, bns, pac, pes, &b[i].a[j], s[!i].l_seq, (uint8_t*)s[!i].seq, &a[!i]); |
| 301 |
free(b[0].a); free(b[1].a); |
| 302 |
} |
| 303 |
n_pri[0] = mem_mark_primary_se(opt, a[0].n, a[0].a, id<<1|0); |
| 304 |
n_pri[1] = mem_mark_primary_se(opt, a[1].n, a[1].a, id<<1|1); |
| 305 |
if (opt->flag & MEM_F_PRIMARY5) { |
| 306 |
mem_reorder_primary5(opt->T, &a[0]); |
| 307 |
mem_reorder_primary5(opt->T, &a[1]); |
| 308 |
} |
| 309 |
if (opt->flag&MEM_F_NOPAIRING) goto no_pairing; |
| 310 |
// pairing single-end hits |
| 311 |
if (n_pri[0] && n_pri[1] && (o = mem_pair(opt, bns, pac, pes, s, a, id, &subo, &n_sub, z, n_pri)) > 0) { |
| 312 |
int is_multi[2], q_pe, score_un, q_se[2]; |
| 313 |
char **XA[2]; |
| 314 |
// check if an end has multiple hits even after mate-SW |
| 315 |
for (i = 0; i < 2; ++i) { |
| 316 |
for (j = 1; j < n_pri[i]; ++j) |
| 317 |
if (a[i].a[j].secondary < 0 && a[i].a[j].score >= opt->T) break; |
| 318 |
is_multi[i] = j < n_pri[i]? 1 : 0; |
| 319 |
} |
| 320 |
if (is_multi[0] || is_multi[1]) goto no_pairing; // TODO: in rare cases, the true hit may be long but with low score |
| 321 |
// compute mapQ for the best SE hit |
| 322 |
score_un = a[0].a[0].score + a[1].a[0].score - opt->pen_unpaired; |
| 323 |
//q_pe = o && subo < o? (int)(MEM_MAPQ_COEF * (1. - (double)subo / o) * log(a[0].a[z[0]].seedcov + a[1].a[z[1]].seedcov) + .499) : 0; |
| 324 |
subo = subo > score_un? subo : score_un; |
| 325 |
q_pe = raw_mapq(o - subo, opt->a); |
| 326 |
if (n_sub > 0) q_pe -= (int)(4.343 * log(n_sub+1) + .499); |
| 327 |
if (q_pe < 0) q_pe = 0; |
| 328 |
if (q_pe > 60) q_pe = 60; |
| 329 |
q_pe = (int)(q_pe * (1. - .5 * (a[0].a[0].frac_rep + a[1].a[0].frac_rep)) + .499); |
| 330 |
// the following assumes no split hits |
| 331 |
if (o > score_un) { // paired alignment is preferred |
| 332 |
mem_alnreg_t *c[2]; |
| 333 |
c[0] = &a[0].a[z[0]]; c[1] = &a[1].a[z[1]]; |
| 334 |
for (i = 0; i < 2; ++i) { |
| 335 |
if (c[i]->secondary >= 0) |
| 336 |
c[i]->sub = a[i].a[c[i]->secondary].score, c[i]->secondary = -2; |
| 337 |
q_se[i] = mem_approx_mapq_se(opt, c[i]); |
| 338 |
} |
| 339 |
q_se[0] = q_se[0] > q_pe? q_se[0] : q_pe < q_se[0] + 40? q_pe : q_se[0] + 40; |
| 340 |
q_se[1] = q_se[1] > q_pe? q_se[1] : q_pe < q_se[1] + 40? q_pe : q_se[1] + 40; |
| 341 |
extra_flag |= 2; |
| 342 |
// cap at the tandem repeat score |
| 343 |
q_se[0] = q_se[0] < raw_mapq(c[0]->score - c[0]->csub, opt->a)? q_se[0] : raw_mapq(c[0]->score - c[0]->csub, opt->a); |
| 344 |
q_se[1] = q_se[1] < raw_mapq(c[1]->score - c[1]->csub, opt->a)? q_se[1] : raw_mapq(c[1]->score - c[1]->csub, opt->a); |
| 345 |
} else { // the unpaired alignment is preferred |
| 346 |
z[0] = z[1] = 0; |
| 347 |
q_se[0] = mem_approx_mapq_se(opt, &a[0].a[0]); |
| 348 |
q_se[1] = mem_approx_mapq_se(opt, &a[1].a[0]); |
| 349 |
} |
| 350 |
for (i = 0; i < 2; ++i) { |
| 351 |
int k = a[i].a[z[i]].secondary_all; |
| 352 |
if (k >= 0 && k < n_pri[i]) { // switch secondary and primary if both of them are non-ALT |
| 353 |
assert(a[i].a[k].secondary_all < 0); |
| 354 |
for (j = 0; j < a[i].n; ++j) |
| 355 |
if (a[i].a[j].secondary_all == k || j == k) |
| 356 |
a[i].a[j].secondary_all = z[i]; |
| 357 |
a[i].a[z[i]].secondary_all = -1; |
| 358 |
} |
| 359 |
} |
| 360 |
if (!(opt->flag & MEM_F_ALL)) { |
| 361 |
for (i = 0; i < 2; ++i) |
| 362 |
XA[i] = mem_gen_alt(opt, bns, pac, &a[i], s[i].l_seq, s[i].seq); |
| 363 |
} else XA[0] = XA[1] = 0; |
| 364 |
// write SAM |
| 365 |
for (i = 0; i < 2; ++i) { |
| 366 |
h[i] = mem_reg2aln(opt, bns, pac, s[i].l_seq, s[i].seq, &a[i].a[z[i]]); |
| 367 |
h[i].mapq = q_se[i]; |
| 368 |
h[i].flag |= 0x40<<i | extra_flag; |
| 369 |
h[i].XA = XA[i]? XA[i][z[i]] : 0; |
| 370 |
aa[i][n_aa[i]++] = h[i]; |
| 371 |
if (n_pri[i] < a[i].n) { // the read has ALT hits |
| 372 |
mem_alnreg_t *p = &a[i].a[n_pri[i]]; |
| 373 |
if (p->score < opt->T || p->secondary >= 0 || !p->is_alt) continue; |
| 374 |
g[i] = mem_reg2aln(opt, bns, pac, s[i].l_seq, s[i].seq, p); |
| 375 |
g[i].flag |= 0x800 | 0x40<<i | extra_flag; |
| 376 |
g[i].XA = XA[i]? XA[i][n_pri[i]] : 0; |
| 377 |
aa[i][n_aa[i]++] = g[i]; |
| 378 |
} |
| 379 |
} |
| 380 |
for (i = 0; i < n_aa[0]; ++i) |
| 381 |
mem_aln2sam(opt, bns, &str, &s[0], n_aa[0], aa[0], i, &h[1]); // write read1 hits |
| 382 |
s[0].sam = str.s; str.m = str.l = 0; str.s = 0; |
| 383 |
for (i = 0; i < n_aa[1]; ++i) |
| 384 |
mem_aln2sam(opt, bns, &str, &s[1], n_aa[1], aa[1], i, &h[0]); // write read2 hits |
| 385 |
s[1].sam = str.s; |
| 386 |
if (strcmp(s[0].name, s[1].name) != 0) err_fatal(__func__, "paired reads have different names: \"%s\", \"%s\"\n", s[0].name, s[1].name); |
| 387 |
// free |
| 388 |
for (i = 0; i < 2; ++i) { |
| 389 |
free(h[i].cigar); free(g[i].cigar); |
| 390 |
if (XA[i] == 0) continue; |
| 391 |
for (j = 0; j < a[i].n; ++j) free(XA[i][j]); |
| 392 |
free(XA[i]); |
| 393 |
} |
| 394 |
} else goto no_pairing; |
| 395 |
return n; |
| 396 |
|
| 397 |
no_pairing: |
| 398 |
for (i = 0; i < 2; ++i) { |
| 399 |
int which = -1; |
| 400 |
if (a[i].n) { |
| 401 |
if (a[i].a[0].score >= opt->T) which = 0; |
| 402 |
else if (n_pri[i] < a[i].n && a[i].a[n_pri[i]].score >= opt->T) |
| 403 |
which = n_pri[i]; |
| 404 |
} |
| 405 |
if (which >= 0) h[i] = mem_reg2aln(opt, bns, pac, s[i].l_seq, s[i].seq, &a[i].a[which]); |
| 406 |
else h[i] = mem_reg2aln(opt, bns, pac, s[i].l_seq, s[i].seq, 0); |
| 407 |
} |
| 408 |
if (!(opt->flag & MEM_F_NOPAIRING) && h[0].rid == h[1].rid && h[0].rid >= 0) { // if the top hits from the two ends constitute a proper pair, flag it. |
| 409 |
int64_t dist; |
| 410 |
int d; |
| 411 |
d = mem_infer_dir(bns->l_pac, a[0].a[0].rb, a[1].a[0].rb, &dist); |
| 412 |
if (!pes[d].failed && dist >= pes[d].low && dist <= pes[d].high) extra_flag |= 2; |
| 413 |
} |
| 414 |
mem_reg2sam(opt, bns, pac, &s[0], &a[0], 0x41|extra_flag, &h[1]); |
| 415 |
mem_reg2sam(opt, bns, pac, &s[1], &a[1], 0x81|extra_flag, &h[0]); |
| 416 |
if (strcmp(s[0].name, s[1].name) != 0) err_fatal(__func__, "paired reads have different names: \"%s\", \"%s\"\n", s[0].name, s[1].name); |
| 417 |
free(h[0].cigar); free(h[1].cigar); |
| 418 |
return n; |
| 419 |
} |