Debian Codegraph @

bwa-apache2/bwamem_pair.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 <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*)&regs[i<<1|0];
83 r[1] = (mem_alnreg_v*)&regs[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 }