| 1 |
#include <stdio.h> |
| 2 |
#include <stdlib.h> |
| 3 |
#include <unistd.h> |
| 4 |
#include <string.h> |
| 5 |
#include <zlib.h> |
| 6 |
#include <pthread.h> |
| 7 |
#include <errno.h> |
| 8 |
#include "ksw.h" |
| 9 |
#include "kseq.h" |
| 10 |
#include "kstring.h" |
| 11 |
#include "bwa.h" |
| 12 |
#include "utils.h" |
| 13 |
KSEQ_DECLARE(gzFile) |
| 14 |
|
| 15 |
#ifdef USE_MALLOC_WRAPPERS |
| 16 |
# include "malloc_wrap.h" |
| 17 |
#endif |
| 18 |
|
| 19 |
#define MAX_SCORE_RATIO 0.9f |
| 20 |
#define MAX_ERR 8 |
| 21 |
|
| 22 |
static const char *err_msg[MAX_ERR+1] = { |
| 23 |
"successful merges", |
| 24 |
"low-scoring pairs", |
| 25 |
"pairs where the best SW alignment is not an overlap (long left end)", |
| 26 |
"pairs where the best SW alignment is not an overlap (long right end)", |
| 27 |
"pairs with large 2nd best SW score", |
| 28 |
"pairs with gapped overlap", |
| 29 |
"pairs where the end-to-end alignment is inconsistent with SW", |
| 30 |
"pairs potentially with tandem overlaps", |
| 31 |
"pairs with high sum of errors" |
| 32 |
}; |
| 33 |
|
| 34 |
typedef struct { |
| 35 |
int a, b, q, r, w; |
| 36 |
int q_def, q_thres; |
| 37 |
int T; |
| 38 |
int chunk_size; |
| 39 |
int n_threads; |
| 40 |
int flag; // bit 1: print merged; 2: print unmerged |
| 41 |
int8_t mat[25]; |
| 42 |
} pem_opt_t; |
| 43 |
|
| 44 |
pem_opt_t *pem_opt_init() |
| 45 |
{ |
| 46 |
pem_opt_t *opt; |
| 47 |
opt = calloc(1, sizeof(pem_opt_t)); |
| 48 |
opt->a = 5; opt->b = 4; opt->q = 2, opt->r = 17; opt->w = 20; |
| 49 |
opt->T = opt->a * 10; |
| 50 |
opt->q_def = 20; |
| 51 |
opt->q_thres = 70; |
| 52 |
opt->chunk_size = 10000000; |
| 53 |
opt->n_threads = 1; |
| 54 |
opt->flag = 3; |
| 55 |
bwa_fill_scmat(opt->a, opt->b, opt->mat); |
| 56 |
return opt; |
| 57 |
} |
| 58 |
|
| 59 |
int bwa_pemerge(const pem_opt_t *opt, bseq1_t x[2]) |
| 60 |
{ |
| 61 |
uint8_t *s[2], *q[2], *seq, *qual; |
| 62 |
int i, xtra, l, l_seq, sum_q, ret = 0; |
| 63 |
kswr_t r; |
| 64 |
|
| 65 |
s[0] = malloc(x[0].l_seq); q[0] = malloc(x[0].l_seq); |
| 66 |
s[1] = malloc(x[1].l_seq); q[1] = malloc(x[1].l_seq); |
| 67 |
for (i = 0; i < x[0].l_seq; ++i) { |
| 68 |
int c = x[0].seq[i]; |
| 69 |
s[0][i] = c < 0 || c > 127? 4 : c <= 4? c : nst_nt4_table[c]; |
| 70 |
q[0][i] = x[0].qual? x[0].qual[i] - 33 : opt->q_def; |
| 71 |
} |
| 72 |
for (i = 0; i < x[1].l_seq; ++i) { |
| 73 |
int c = x[1].seq[x[1].l_seq - 1 - i]; |
| 74 |
c = c < 0 || c > 127? 4 : c < 4? c : nst_nt4_table[c]; |
| 75 |
s[1][i] = c < 4? 3 - c : 4; |
| 76 |
q[1][i] = x[1].qual? x[1].qual[x[1].l_seq - 1 - i] - 33 : opt->q_def; |
| 77 |
} |
| 78 |
|
| 79 |
xtra = KSW_XSTART | KSW_XSUBO; |
| 80 |
r = ksw_align(x[1].l_seq, s[1], x[0].l_seq, s[0], 5, opt->mat, opt->q, opt->r, xtra, 0); |
| 81 |
++r.qe; ++r.te; // change to the half-close-half-open coordinates |
| 82 |
|
| 83 |
if (r.score < opt->T) { ret = -1; goto pem_ret; } // poor alignment |
| 84 |
if (r.tb < r.qb) { ret = -2; goto pem_ret; } // no enough space for the left end |
| 85 |
if (x[0].l_seq - r.te > x[1].l_seq - r.qe) { ret = -3; goto pem_ret; } // no enough space for the right end |
| 86 |
if ((double)r.score2 / r.score >= MAX_SCORE_RATIO) { ret = -4; goto pem_ret; } // the second best score is too large |
| 87 |
if (r.qe - r.qb != r.te - r.tb) { ret = -5; goto pem_ret; } // we do not allow gaps |
| 88 |
|
| 89 |
{ // test tandem match; O(n^2) |
| 90 |
int max_m, max_m2, min_l, max_l, max_l2; |
| 91 |
max_m = max_m2 = 0; max_l = max_l2 = 0; |
| 92 |
min_l = x[0].l_seq < x[1].l_seq? x[0].l_seq : x[1].l_seq; |
| 93 |
for (l = 1; l < min_l; ++l) { |
| 94 |
int m = 0, o = x[0].l_seq - l; |
| 95 |
uint8_t *s0o = &s[0][o], *s1 = s[1]; |
| 96 |
for (i = 0; i < l; ++i) // TODO: in principle, this can be done with SSE2. It is the bottleneck! |
| 97 |
m += opt->mat[(s1[i]<<2) + s1[i] + s0o[i]]; // equivalent to s[1][i]*5 + s[0][o+i] |
| 98 |
if (m > max_m) max_m2 = max_m, max_m = m, max_l2 = max_l, max_l = l; |
| 99 |
else if (m > max_m2) max_m2 = m, max_l2 = l; |
| 100 |
} |
| 101 |
if (max_m < opt->T || max_l != x[0].l_seq - (r.tb - r.qb)) { ret = -6; goto pem_ret; } |
| 102 |
if (max_l2 < max_l && max_m2 >= opt->T && (double)(max_m2 + (max_l - max_l2) * opt->a) / max_m >= MAX_SCORE_RATIO) { |
| 103 |
ret = -7; goto pem_ret; |
| 104 |
} |
| 105 |
if (max_l2 > max_l && (double)max_m2 / max_m >= MAX_SCORE_RATIO) { ret = -7; goto pem_ret; } |
| 106 |
} |
| 107 |
|
| 108 |
l = x[0].l_seq - (r.tb - r.qb); // length to merge |
| 109 |
l_seq = x[0].l_seq + x[1].l_seq - l; |
| 110 |
seq = malloc(l_seq + 1); |
| 111 |
qual = malloc(l_seq + 1); |
| 112 |
memcpy(seq, s[0], x[0].l_seq); memcpy(seq + x[0].l_seq, &s[1][l], x[1].l_seq - l); |
| 113 |
memcpy(qual, q[0], x[0].l_seq); memcpy(qual + x[0].l_seq, &q[1][l], x[1].l_seq - l); |
| 114 |
for (i = 0, sum_q = 0; i < l; ++i) { |
| 115 |
int k = x[0].l_seq - l + i; |
| 116 |
if (s[0][k] == 4) { // ambiguous |
| 117 |
seq[k] = s[1][i]; |
| 118 |
qual[k] = q[1][i]; |
| 119 |
} else if (s[1][i] == 4) { // do nothing |
| 120 |
} else if (s[0][k] == s[1][i]) { |
| 121 |
qual[k] = qual[k] > q[1][i]? qual[k] : q[1][i]; |
| 122 |
} else { // s[0][k] != s[1][i] and neither is N |
| 123 |
int qq = q[0][k] < q[1][i]? q[0][k] : q[1][i]; |
| 124 |
sum_q += qq >= 3? qq<<1 : 1; |
| 125 |
seq[k] = q[0][k] > q[1][i]? s[0][k] : s[1][i]; |
| 126 |
qual[k] = abs((int)q[0][k] - (int)q[1][i]); |
| 127 |
} |
| 128 |
} |
| 129 |
if (sum_q>>1 > opt->q_thres) { // too many mismatches |
| 130 |
free(seq); free(qual); |
| 131 |
ret = -8; goto pem_ret; |
| 132 |
} |
| 133 |
|
| 134 |
for (i = 0; i < l_seq; ++i) seq[i] = "ACGTN"[(int)seq[i]], qual[i] += 33; |
| 135 |
seq[l_seq] = qual[l_seq] = 0; |
| 136 |
|
| 137 |
free(x[1].name); free(x[1].seq); free(x[1].qual); free(x[1].comment); |
| 138 |
memset(&x[1], 0, sizeof(bseq1_t)); |
| 139 |
free(x[0].seq); free(x[0].qual); |
| 140 |
x[0].l_seq = l_seq; x[0].seq = (char*)seq; x[0].qual = (char*)qual; |
| 141 |
|
| 142 |
pem_ret: |
| 143 |
free(s[0]); free(s[1]); free(q[0]); free(q[1]); |
| 144 |
return ret; |
| 145 |
} |
| 146 |
|
| 147 |
static inline void print_bseq(const bseq1_t *s, int rn) |
| 148 |
{ |
| 149 |
err_putchar(s->qual? '@' : '>'); |
| 150 |
err_fputs(s->name, stdout); |
| 151 |
if (rn == 1 || rn == 2) { |
| 152 |
err_putchar('/'); err_putchar('0' + rn); err_putchar('\n'); |
| 153 |
} else err_puts(" merged"); |
| 154 |
err_puts(s->seq); |
| 155 |
if (s->qual) { |
| 156 |
err_puts("+"); err_puts(s->qual); |
| 157 |
} |
| 158 |
} |
| 159 |
|
| 160 |
typedef struct { |
| 161 |
int n, start; |
| 162 |
bseq1_t *seqs; |
| 163 |
int64_t cnt[MAX_ERR+1]; |
| 164 |
const pem_opt_t *opt; |
| 165 |
} worker_t; |
| 166 |
|
| 167 |
void *worker(void *data) |
| 168 |
{ |
| 169 |
worker_t *w = (worker_t*)data; |
| 170 |
int i; |
| 171 |
for (i = w->start; i < w->n>>1; i += w->opt->n_threads) |
| 172 |
++w->cnt[-bwa_pemerge(w->opt, &w->seqs[i<<1])]; |
| 173 |
return 0; |
| 174 |
} |
| 175 |
|
| 176 |
static void process_seqs(const pem_opt_t *opt, int n_, bseq1_t *seqs, int64_t cnt[MAX_ERR+1]) |
| 177 |
{ |
| 178 |
int i, j, n = n_>>1<<1; |
| 179 |
worker_t *w; |
| 180 |
|
| 181 |
w = calloc(opt->n_threads, sizeof(worker_t)); |
| 182 |
for (i = 0; i < opt->n_threads; ++i) { |
| 183 |
worker_t *p = &w[i]; |
| 184 |
p->start = i; p->n = n; |
| 185 |
p->opt = opt; |
| 186 |
p->seqs = seqs; |
| 187 |
} |
| 188 |
if (opt->n_threads == 1) { |
| 189 |
worker(w); |
| 190 |
} else { |
| 191 |
pthread_t *tid; |
| 192 |
tid = (pthread_t*)calloc(opt->n_threads, sizeof(pthread_t)); |
| 193 |
for (i = 0; i < opt->n_threads; ++i) pthread_create(&tid[i], 0, worker, &w[i]); |
| 194 |
for (i = 0; i < opt->n_threads; ++i) pthread_join(tid[i], 0); |
| 195 |
free(tid); |
| 196 |
} |
| 197 |
for (i = 0; i < opt->n_threads; ++i) { |
| 198 |
worker_t *p = &w[i]; |
| 199 |
for (j = 0; j <= MAX_ERR; ++j) cnt[j] += p->cnt[j]; |
| 200 |
} |
| 201 |
free(w); |
| 202 |
for (i = 0; i < n>>1; ++i) { |
| 203 |
if (seqs[i<<1|1].l_seq != 0) { |
| 204 |
if (opt->flag&2) { |
| 205 |
print_bseq(&seqs[i<<1|0], 1); |
| 206 |
print_bseq(&seqs[i<<1|1], 2); |
| 207 |
} |
| 208 |
} else if (opt->flag&1) |
| 209 |
print_bseq(&seqs[i<<1|0], 0); |
| 210 |
} |
| 211 |
for (i = 0; i < n; ++i) { |
| 212 |
bseq1_t *s = &seqs[i]; |
| 213 |
free(s->name); free(s->seq); free(s->qual); free(s->comment); |
| 214 |
} |
| 215 |
} |
| 216 |
|
| 217 |
int main_pemerge(int argc, char *argv[]) |
| 218 |
{ |
| 219 |
int c, flag = 0, i, n, min_ovlp = 10; |
| 220 |
int64_t cnt[MAX_ERR+1]; |
| 221 |
bseq1_t *bseq; |
| 222 |
gzFile fp, fp2 = 0; |
| 223 |
kseq_t *ks, *ks2 = 0; |
| 224 |
pem_opt_t *opt; |
| 225 |
|
| 226 |
opt = pem_opt_init(); |
| 227 |
while ((c = getopt(argc, argv, "muQ:t:T:")) >= 0) { |
| 228 |
if (c == 'm') flag |= 1; |
| 229 |
else if (c == 'u') flag |= 2; |
| 230 |
else if (c == 'Q') opt->q_thres = atoi(optarg); |
| 231 |
else if (c == 't') opt->n_threads = atoi(optarg); |
| 232 |
else if (c == 'T') min_ovlp = atoi(optarg); |
| 233 |
else return 1; |
| 234 |
} |
| 235 |
if (flag == 0) flag = 3; |
| 236 |
opt->flag = flag; |
| 237 |
opt->T = opt->a * min_ovlp; |
| 238 |
|
| 239 |
if (optind == argc) { |
| 240 |
fprintf(stderr, "\n"); |
| 241 |
fprintf(stderr, "Usage: bwa pemerge [-mu] <read1.fq> [read2.fq]\n\n"); |
| 242 |
fprintf(stderr, "Options: -m output merged reads only\n"); |
| 243 |
fprintf(stderr, " -u output unmerged reads only\n"); |
| 244 |
fprintf(stderr, " -t INT number of threads [%d]\n", opt->n_threads); |
| 245 |
fprintf(stderr, " -T INT minimum end overlap [%d]\n", min_ovlp); |
| 246 |
fprintf(stderr, " -Q INT max sum of errors [%d]\n", opt->q_thres); |
| 247 |
fprintf(stderr, "\n"); |
| 248 |
free(opt); |
| 249 |
return 1; |
| 250 |
} |
| 251 |
|
| 252 |
fp = strcmp(argv[optind], "-")? gzopen(argv[optind], "r") : gzdopen(fileno(stdin), "r"); |
| 253 |
if (NULL == fp) { |
| 254 |
fprintf(stderr, "Couldn't open %s : %s\n", |
| 255 |
strcmp(argv[optind], "-") ? argv[optind] : "stdin", |
| 256 |
errno ? strerror(errno) : "Out of memory"); |
| 257 |
exit(EXIT_FAILURE); |
| 258 |
} |
| 259 |
ks = kseq_init(fp); |
| 260 |
if (optind + 1 < argc) { |
| 261 |
fp2 = strcmp(argv[optind+1], "-")? gzopen(argv[optind+1], "r") : gzdopen(fileno(stdin), "r"); |
| 262 |
if (NULL == fp) { |
| 263 |
fprintf(stderr, "Couldn't open %s : %s\n", |
| 264 |
strcmp(argv[optind+1], "-") ? argv[optind+1] : "stdin", |
| 265 |
errno ? strerror(errno) : "Out of memory"); |
| 266 |
exit(EXIT_FAILURE); |
| 267 |
} |
| 268 |
ks2 = kseq_init(fp2); |
| 269 |
} |
| 270 |
|
| 271 |
memset(cnt, 0, 8 * (MAX_ERR+1)); |
| 272 |
while ((bseq = bseq_read(opt->n_threads * opt->chunk_size, &n, ks, ks2)) != 0) { |
| 273 |
process_seqs(opt, n, bseq, cnt); |
| 274 |
free(bseq); |
| 275 |
} |
| 276 |
|
| 277 |
fprintf(stderr, "%12ld %s\n", (long)cnt[0], err_msg[0]); |
| 278 |
for (i = 1; i <= MAX_ERR; ++i) |
| 279 |
fprintf(stderr, "%12ld %s\n", (long)cnt[i], err_msg[i]); |
| 280 |
kseq_destroy(ks); |
| 281 |
err_gzclose(fp); |
| 282 |
if (ks2) { |
| 283 |
kseq_destroy(ks2); |
| 284 |
err_gzclose(fp2); |
| 285 |
} |
| 286 |
free(opt); |
| 287 |
|
| 288 |
err_fflush(stdout); |
| 289 |
|
| 290 |
return 0; |
| 291 |
} |