| 1 |
#include <math.h> |
| 2 |
#include <stdio.h> |
| 3 |
#include <stdlib.h> |
| 4 |
#include <string.h> |
| 5 |
#include "utils.h" |
| 6 |
#include "bwt.h" |
| 7 |
#include "bntseq.h" |
| 8 |
#include "bwtsw2.h" |
| 9 |
#include "kstring.h" |
| 10 |
#include "ksw.h" |
| 11 |
|
| 12 |
#ifdef USE_MALLOC_WRAPPERS |
| 13 |
# include "malloc_wrap.h" |
| 14 |
#endif |
| 15 |
|
| 16 |
#define MIN_RATIO 0.8 |
| 17 |
#define OUTLIER_BOUND 2.0 |
| 18 |
#define MAX_STDDEV 4.0 |
| 19 |
#define EXT_STDDEV 4.0 |
| 20 |
|
| 21 |
typedef struct { |
| 22 |
int low, high, failed; |
| 23 |
double avg, std; |
| 24 |
} bsw2pestat_t; |
| 25 |
|
| 26 |
bsw2pestat_t bsw2_stat(int n, bwtsw2_t **buf, kstring_t *msg, int max_ins) |
| 27 |
{ |
| 28 |
int i, k, x, p25, p50, p75, tmp, max_len = 0; |
| 29 |
uint64_t *isize; |
| 30 |
bsw2pestat_t r; |
| 31 |
|
| 32 |
memset(&r, 0, sizeof(bsw2pestat_t)); |
| 33 |
isize = calloc(n, 8); |
| 34 |
for (i = k = 0; i < n; i += 2) { |
| 35 |
bsw2hit_t *t[2]; |
| 36 |
int l; |
| 37 |
if (buf[i] == 0 || buf[i]->n != 1 || buf[i+1]->n != 1) continue; // more than 1 hits |
| 38 |
t[0] = &buf[i]->hits[0]; t[1] = &buf[i+1]->hits[0]; |
| 39 |
if (t[0]->G2 > 0.8 * t[0]->G) continue; // the best hit is not good enough |
| 40 |
if (t[1]->G2 > 0.8 * t[1]->G) continue; // the best hit is not good enough |
| 41 |
l = t[0]->k > t[1]->k? t[0]->k - t[1]->k + t[1]->len : t[1]->k - t[0]->k + t[0]->len; |
| 42 |
if (l >= max_ins) continue; // skip pairs with excessively large insert |
| 43 |
max_len = max_len > t[0]->end - t[0]->beg? max_len : t[0]->end - t[0]->beg; |
| 44 |
max_len = max_len > t[1]->end - t[1]->beg? max_len : t[1]->end - t[1]->beg; |
| 45 |
isize[k++] = l; |
| 46 |
} |
| 47 |
ks_introsort_64(k, isize); |
| 48 |
p25 = isize[(int)(.25 * k + .499)]; |
| 49 |
p50 = isize[(int)(.50 * k + .499)]; |
| 50 |
p75 = isize[(int)(.75 * k + .499)]; |
| 51 |
ksprintf(msg, "[%s] infer the insert size distribution from %d high-quality pairs.\n", __func__, k); |
| 52 |
if (k < 8) { |
| 53 |
ksprintf(msg, "[%s] fail to infer the insert size distribution: too few good pairs.\n", __func__); |
| 54 |
free(isize); |
| 55 |
r.failed = 1; |
| 56 |
return r; |
| 57 |
} |
| 58 |
tmp = (int)(p25 - OUTLIER_BOUND * (p75 - p25) + .499); |
| 59 |
r.low = tmp > max_len? tmp : max_len; |
| 60 |
if (r.low < 1) r.low = 1; |
| 61 |
r.high = (int)(p75 + OUTLIER_BOUND * (p75 - p25) + .499); |
| 62 |
if (r.low > r.high) { |
| 63 |
ksprintf(msg, "[%s] fail to infer the insert size distribution: upper bound is smaller than max read length.\n", __func__); |
| 64 |
free(isize); |
| 65 |
r.failed = 1; |
| 66 |
return r; |
| 67 |
} |
| 68 |
ksprintf(msg, "[%s] (25, 50, 75) percentile: (%d, %d, %d)\n", __func__, p25, p50, p75); |
| 69 |
ksprintf(msg, "[%s] low and high boundaries for computing mean and std.dev: (%d, %d)\n", __func__, r.low, r.high); |
| 70 |
for (i = x = 0, r.avg = 0; i < k; ++i) |
| 71 |
if (isize[i] >= r.low && isize[i] <= r.high) |
| 72 |
r.avg += isize[i], ++x; |
| 73 |
if (x == 0) { |
| 74 |
ksprintf(msg, "[%s] fail to infer the insert size distribution: no pairs within boundaries.\n", __func__); |
| 75 |
free(isize); |
| 76 |
r.failed = 1; |
| 77 |
return r; |
| 78 |
} |
| 79 |
r.avg /= x; |
| 80 |
for (i = 0, r.std = 0; i < k; ++i) |
| 81 |
if (isize[i] >= r.low && isize[i] <= r.high) |
| 82 |
r.std += (isize[i] - r.avg) * (isize[i] - r.avg); |
| 83 |
r.std = sqrt(r.std / x); |
| 84 |
ksprintf(msg, "[%s] mean and std.dev: (%.2f, %.2f)\n", __func__, r.avg, r.std); |
| 85 |
tmp = (int)(p25 - 3. * (p75 - p25) + .499); |
| 86 |
r.low = tmp > max_len? tmp : max_len; |
| 87 |
if (r.low < 1) r.low = 1; |
| 88 |
r.high = (int)(p75 + 3. * (p75 - p25) + .499); |
| 89 |
if (r.low > r.avg - MAX_STDDEV * r.std) r.low = (int)(r.avg - MAX_STDDEV * r.std + .499); |
| 90 |
r.low = tmp > max_len? tmp : max_len; |
| 91 |
if (r.high < r.avg + MAX_STDDEV * r.std) r.high = (int)(r.avg + MAX_STDDEV * r.std + .499); |
| 92 |
ksprintf(msg, "[%s] low and high boundaries for proper pairs: (%d, %d)\n", __func__, r.low, r.high); |
| 93 |
free(isize); |
| 94 |
return r; |
| 95 |
} |
| 96 |
|
| 97 |
typedef struct { |
| 98 |
int n_cigar, beg, end, len; |
| 99 |
int64_t pos; |
| 100 |
uint32_t *cigar; |
| 101 |
} pairaux_t; |
| 102 |
|
| 103 |
extern unsigned char nst_nt4_table[256]; |
| 104 |
|
| 105 |
void bsw2_pair1(const bsw2opt_t *opt, int64_t l_pac, const uint8_t *pac, const bsw2pestat_t *st, const bsw2hit_t *h, int l_mseq, const char *mseq, bsw2hit_t *a, int8_t g_mat[25]) |
| 106 |
{ |
| 107 |
extern void seq_reverse(int len, ubyte_t *seq, int is_comp); |
| 108 |
int64_t k, beg, end; |
| 109 |
uint8_t *seq, *ref; |
| 110 |
int i; |
| 111 |
// compute the region start and end |
| 112 |
a->n_seeds = 1; a->flag |= BSW2_FLAG_MATESW; // before calling this routine, *a has been cleared with memset(0); the flag is set with 1<<6/7 |
| 113 |
if (h->is_rev == 0) { |
| 114 |
beg = (int64_t)(h->k + st->avg - EXT_STDDEV * st->std - l_mseq + .499); |
| 115 |
if (beg < h->k) beg = h->k; |
| 116 |
end = (int64_t)(h->k + st->avg + EXT_STDDEV * st->std + .499); |
| 117 |
a->is_rev = 1; a->flag |= 16; |
| 118 |
} else { |
| 119 |
beg = (int64_t)(h->k + h->end - h->beg - st->avg - EXT_STDDEV * st->std + .499); |
| 120 |
end = (int64_t)(h->k + h->end - h->beg - st->avg + EXT_STDDEV * st->std + l_mseq + .499); |
| 121 |
if (end > h->k + (h->end - h->beg)) end = h->k + (h->end - h->beg); |
| 122 |
a->is_rev = 0; |
| 123 |
} |
| 124 |
if (beg < 1) beg = 1; |
| 125 |
if (end > l_pac) end = l_pac; |
| 126 |
if (end - beg < l_mseq) return; |
| 127 |
// generate the sequence |
| 128 |
seq = malloc(l_mseq + (end - beg)); |
| 129 |
ref = seq + l_mseq; |
| 130 |
for (k = beg; k < end; ++k) |
| 131 |
ref[k - beg] = pac[k>>2] >> ((~k&3)<<1) & 0x3; |
| 132 |
if (h->is_rev == 0) { |
| 133 |
for (i = 0; i < l_mseq; ++i) { // on the reverse strand |
| 134 |
int c = nst_nt4_table[(int)mseq[i]]; |
| 135 |
seq[l_mseq - 1 - i] = c > 3? 4 : 3 - c; |
| 136 |
} |
| 137 |
} else { |
| 138 |
for (i = 0; i < l_mseq; ++i) // on the forward strand |
| 139 |
seq[i] = nst_nt4_table[(int)mseq[i]]; |
| 140 |
} |
| 141 |
{ |
| 142 |
int flag = KSW_XSUBO | KSW_XSTART | (l_mseq * g_mat[0] < 250? KSW_XBYTE : 0) | opt->t; |
| 143 |
kswr_t aln; |
| 144 |
aln = ksw_align(l_mseq, seq, end - beg, ref, 5, g_mat, opt->q, opt->r, flag, 0); |
| 145 |
a->G = aln.score; |
| 146 |
a->G2 = aln.score2; |
| 147 |
if (a->G < opt->t) a->G = 0; |
| 148 |
if (a->G2 < opt->t) a->G2 = 0; |
| 149 |
if (a->G2) a->flag |= BSW2_FLAG_TANDEM; |
| 150 |
a->k = beg + aln.tb; |
| 151 |
a->len = aln.te - aln.tb + 1; |
| 152 |
a->beg = aln.qb; |
| 153 |
a->end = aln.qe + 1; |
| 154 |
/* |
| 155 |
printf("[Q] "); for (i = 0; i < l_mseq; ++i) putchar("ACGTN"[(int)seq[i]]); putchar('\n'); |
| 156 |
printf("[R] "); for (i = 0; i < end - beg; ++i) putchar("ACGTN"[(int)ref[i]]); putchar('\n'); |
| 157 |
printf("G=%d,G2=%d,beg=%d,end=%d,k=%lld,len=%d\n", a->G, a->G2, a->beg, a->end, a->k, a->len); |
| 158 |
*/ |
| 159 |
} |
| 160 |
if (a->is_rev) i = a->beg, a->beg = l_mseq - a->end, a->end = l_mseq - i; |
| 161 |
free(seq); |
| 162 |
} |
| 163 |
|
| 164 |
void bsw2_pair(const bsw2opt_t *opt, int64_t l_pac, const uint8_t *pac, int n, bsw2seq1_t *seq, bwtsw2_t **hits) |
| 165 |
{ |
| 166 |
extern int bsw2_resolve_duphits(const bntseq_t *bns, const bwt_t *bwt, bwtsw2_t *b, int IS); |
| 167 |
bsw2pestat_t pes; |
| 168 |
int i, j, k, n_rescued = 0, n_moved = 0, n_fixed = 0; |
| 169 |
int8_t g_mat[25]; |
| 170 |
kstring_t msg; |
| 171 |
memset(&msg, 0, sizeof(kstring_t)); |
| 172 |
pes = bsw2_stat(n, hits, &msg, opt->max_ins); |
| 173 |
for (i = k = 0; i < 5; ++i) { |
| 174 |
for (j = 0; j < 4; ++j) |
| 175 |
g_mat[k++] = i == j? opt->a : -opt->b; |
| 176 |
g_mat[k++] = 0; |
| 177 |
} |
| 178 |
for (i = 0; i < n; i += 2) { |
| 179 |
bsw2hit_t a[2]; |
| 180 |
memset(&a, 0, sizeof(bsw2hit_t) * 2); |
| 181 |
a[0].flag = 1<<6; a[1].flag = 1<<7; |
| 182 |
for (j = 0; j < 2; ++j) { // set the read1/2 flag |
| 183 |
if (hits[i+j] == 0) continue; |
| 184 |
for (k = 0; k < hits[i+j]->n; ++k) { |
| 185 |
bsw2hit_t *p = &hits[i+j]->hits[k]; |
| 186 |
p->flag |= 1<<(6+j); |
| 187 |
} |
| 188 |
} |
| 189 |
if (pes.failed) continue; |
| 190 |
if (hits[i] == 0 || hits[i+1] == 0) continue; // one end has excessive N |
| 191 |
if (hits[i]->n != 1 && hits[i+1]->n != 1) continue; // no end has exactly one hit |
| 192 |
if (hits[i]->n > 1 || hits[i+1]->n > 1) continue; // one read has more than one hit |
| 193 |
if (!opt->skip_sw) { |
| 194 |
if (hits[i+0]->n == 1) bsw2_pair1(opt, l_pac, pac, &pes, &hits[i+0]->hits[0], seq[i+1].l, seq[i+1].seq, &a[1], g_mat); |
| 195 |
if (hits[i+1]->n == 1) bsw2_pair1(opt, l_pac, pac, &pes, &hits[i+1]->hits[0], seq[i+0].l, seq[i+0].seq, &a[0], g_mat); |
| 196 |
} // else a[0].G == a[1].G == a[0].G2 == a[1].G2 == 0 |
| 197 |
// the following enumerate all possibilities. It is tedious but necessary... |
| 198 |
if (hits[i]->n + hits[i+1]->n == 1) { // one end mapped; the other not; |
| 199 |
bwtsw2_t *p[2]; |
| 200 |
int which; |
| 201 |
if (hits[i]->n == 1) p[0] = hits[i], p[1] = hits[i+1], which = 1; |
| 202 |
else p[0] = hits[i+1], p[1] = hits[i], which = 0; |
| 203 |
if (a[which].G == 0) continue; |
| 204 |
a[which].flag |= BSW2_FLAG_RESCUED; |
| 205 |
if (p[1]->max == 0) { |
| 206 |
p[1]->max = 1; |
| 207 |
p[1]->hits = malloc(sizeof(bsw2hit_t)); |
| 208 |
} |
| 209 |
p[1]->hits[0] = a[which]; |
| 210 |
p[1]->n = 1; |
| 211 |
p[0]->hits[0].flag |= 2; |
| 212 |
p[1]->hits[0].flag |= 2; |
| 213 |
++n_rescued; |
| 214 |
} else { // then both ends mapped |
| 215 |
int is_fixed = 0; |
| 216 |
//fprintf(stderr, "%d; %lld,%lld; %d,%d\n", a[0].is_rev, hits[i]->hits[0].k, a[0].k, hits[i]->hits[0].end, a[0].end); |
| 217 |
for (j = 0; j < 2; ++j) { // fix wrong mappings and wrong suboptimal alignment score |
| 218 |
bsw2hit_t *p = &hits[i+j]->hits[0]; |
| 219 |
if (p->G < a[j].G) { // the orginal mapping is suboptimal |
| 220 |
a[j].G2 = a[j].G2 > p->G? a[j].G2 : p->G; // FIXME: reset BSW2_FLAG_TANDEM? |
| 221 |
*p = a[j]; |
| 222 |
++n_fixed; |
| 223 |
is_fixed = 1; |
| 224 |
} else if (p->k != a[j].k && p->G2 < a[j].G) { |
| 225 |
p->G2 = a[j].G; |
| 226 |
} else if (p->k == a[j].k && p->G2 < a[j].G2) { |
| 227 |
p->G2 = a[j].G2; |
| 228 |
} |
| 229 |
} |
| 230 |
if (hits[i]->hits[0].k == a[0].k && hits[i+1]->hits[0].k == a[1].k) { // properly paired and no ends need to be moved |
| 231 |
for (j = 0; j < 2; ++j) |
| 232 |
hits[i+j]->hits[0].flag |= 2 | (a[j].flag & BSW2_FLAG_TANDEM); |
| 233 |
} else if (hits[i]->hits[0].k == a[0].k || hits[i+1]->hits[0].k == a[1].k) { // a tandem match |
| 234 |
for (j = 0; j < 2; ++j) { |
| 235 |
hits[i+j]->hits[0].flag |= 2; |
| 236 |
if (hits[i+j]->hits[0].k != a[j].k) |
| 237 |
hits[i+j]->hits[0].flag |= BSW2_FLAG_TANDEM; |
| 238 |
} |
| 239 |
} else if (!is_fixed && (a[0].G || a[1].G)) { // it is possible to move one end |
| 240 |
if (a[0].G && a[1].G) { // now we have two "proper pairs" |
| 241 |
int G[2]; |
| 242 |
double diff; |
| 243 |
G[0] = hits[i]->hits[0].G + a[1].G; |
| 244 |
G[1] = hits[i+1]->hits[0].G + a[0].G; |
| 245 |
diff = fabs((double)(G[0] - G[1])) / (opt->a + opt->b) / ((hits[i]->hits[0].len + a[1].len + hits[i+1]->hits[0].len + a[0].len) / 2.); |
| 246 |
if (diff > 0.05) a[G[0] > G[1]? 0 : 1].G = 0; |
| 247 |
} |
| 248 |
if (a[0].G == 0 || a[1].G == 0) { // one proper pair only |
| 249 |
bsw2hit_t *p[2]; // p[0] points the unchanged hit; p[1] to the hit to be moved |
| 250 |
int which, isize; |
| 251 |
double dev, diff; |
| 252 |
if (a[0].G) p[0] = &hits[i+1]->hits[0], p[1] = &hits[i]->hits[0], which = 0; |
| 253 |
else p[0] = &hits[i]->hits[0], p[1] = &hits[i+1]->hits[0], which = 1; |
| 254 |
isize = p[0]->is_rev? p[0]->k + p[0]->len - a[which].k : a[which].k + a[which].len - p[0]->k; |
| 255 |
dev = fabs(isize - pes.avg) / pes.std; |
| 256 |
diff = (double)(p[1]->G - a[which].G) / (opt->a + opt->b) / (p[1]->end - p[1]->beg) * 100.0; |
| 257 |
if (diff < dev * 2.) { // then move (heuristic) |
| 258 |
a[which].G2 = a[which].G; |
| 259 |
p[1][0] = a[which]; |
| 260 |
p[1]->flag |= BSW2_FLAG_MOVED | 2; |
| 261 |
p[0]->flag |= 2; |
| 262 |
++n_moved; |
| 263 |
} |
| 264 |
} |
| 265 |
} else if (is_fixed) { |
| 266 |
hits[i+0]->hits[0].flag |= 2; |
| 267 |
hits[i+1]->hits[0].flag |= 2; |
| 268 |
} |
| 269 |
} |
| 270 |
} |
| 271 |
ksprintf(&msg, "[%s] #fixed=%d, #rescued=%d, #moved=%d\n", __func__, n_fixed, n_rescued, n_moved); |
| 272 |
fputs(msg.s, stderr); |
| 273 |
free(msg.s); |
| 274 |
} |