15 #include "my_assert.h"
19 #include "SingleRead.h"
20 #include "SingleReadQ.h"
21 #include "PairedEndRead.h"
22 #include "PairedEndReadQ.h"
24 #include "SingleHit.h"
25 #include "PairedEndHit.h"
28 #include "SingleModel.h"
29 #include "SingleQModel.h"
30 #include "PairedEndModel.h"
31 #include "PairedEndQModel.h"
33 #include "Transcript.h"
34 #include "Transcripts.h"
37 #include "GroupInfo.h"
38 #include "HitContainer.h"
39 #include "ReadIndex.h"
40 #include "ReadReader.h"
42 #include "ModelParams.h"
44 #include "HitWrapper.h"
45 #include "BamWriter.h"
47 #include "WriteResults.h"
51 const double STOP_CRITERIA = 0.001;
52 const int MAX_ROUND = 10000;
53 const int MIN_ROUND = 20;
57 void *reader, *hitv, *ncpv, *mhp, *countv;
61 int m, M; // m genes, M isoforms
62 READ_INT_TYPE N0, N1, N2, N_tot;
66 bool genBamF; // If user wants to generate bam file, true; otherwise, false.
67 bool bamSampling; // true if sampling from read posterior distribution when bam file is generated
68 bool updateModel, calcExpectedWeights;
69 bool genGibbsOut; // generate file for Gibbs sampler
71 char refName[STRLEN], outName[STRLEN];
72 char imdName[STRLEN], statName[STRLEN];
73 char refF[STRLEN], cntF[STRLEN], tiF[STRLEN];
74 char mparamsF[STRLEN];
75 char modelF[STRLEN], thetaF[STRLEN];
78 char *pt_fn_list, *pt_chr_list;
79 char inpSamF[STRLEN], outBamF[STRLEN], fn_list[STRLEN], chr_list[STRLEN];
81 char out_for_gibbs_F[STRLEN];
83 vector<double> theta, eel; // eel : expected effective length
85 double *probv, **countvs;
88 Transcripts transcripts;
95 template<class ReadType, class HitType, class ModelType>
96 void init(ReadReader<ReadType> **&readers, HitContainer<HitType> **&hitvs, double **&ncpvs, ModelType **&mhps) {
101 READ_INT_TYPE nrLeft, curnr; // nrLeft : number of reads left, curnr: current number of reads
102 HIT_INT_TYPE nhT; // nhT : hit threshold per thread
106 char readFs[2][STRLEN];
107 ReadIndex *indices[2];
110 readers = new ReadReader<ReadType>*[nThreads];
111 genReadFileNames(imdName, 1, read_type, s, readFs);
112 for (int i = 0; i < s; i++) {
113 indices[i] = new ReadIndex(readFs[i]);
115 for (int i = 0; i < nThreads; i++) {
116 readers[i] = new ReadReader<ReadType>(s, readFs, refs.hasPolyA(), mparams.seedLen); // allow calculation of calc_lq() function
117 readers[i]->setIndices(indices);
120 hitvs = new HitContainer<HitType>*[nThreads];
121 for (int i = 0; i < nThreads; i++) {
122 hitvs[i] = new HitContainer<HitType>();
125 sprintf(datF, "%s.dat", imdName);
127 general_assert(fin.is_open(), "Cannot open " + cstrtos(datF) + "! It may not exist.");
128 fin>>nReads>>nHits>>rt;
129 general_assert(nReads == N1, "Number of alignable reads does not match!");
130 general_assert(rt == read_type, "Data file (.dat) does not have the right read type!");
133 //A just so so strategy for paralleling
134 nhT = nHits / nThreads;
138 ncpvs = new double*[nThreads];
139 for (int i = 0; i < nThreads; i++) {
140 HIT_INT_TYPE ntLeft = nThreads - i - 1; // # of threads left
142 general_assert(readers[i]->locate(curnr), "Read indices files do not match!");
144 while (nrLeft > ntLeft && (i == nThreads - 1 || hitvs[i]->getNHits() < nhT)) {
145 general_assert(hitvs[i]->read(fin), "Cannot read alignments from .dat file!");
148 if (verbose && nrLeft % 1000000 == 0) { cout<< "DAT "<< nrLeft << " reads left"<< endl; }
150 ncpvs[i] = new double[hitvs[i]->getN()];
151 memset(ncpvs[i], 0, sizeof(double) * hitvs[i]->getN());
152 curnr += hitvs[i]->getN();
154 if (verbose) { cout<<"Thread "<< i<< " : N = "<< hitvs[i]->getN()<< ", NHit = "<< hitvs[i]->getNHits()<< endl; }
159 mhps = new ModelType*[nThreads];
160 for (int i = 0; i < nThreads; i++) {
161 mhps[i] = new ModelType(mparams, false); // just model helper
164 probv = new double[M + 1];
165 countvs = new double*[nThreads];
166 for (int i = 0; i < nThreads; i++) {
167 countvs[i] = new double[M + 1];
171 if (verbose) { printf("EM_init finished!\n"); }
174 template<class ReadType, class HitType, class ModelType>
175 void* E_STEP(void* arg) {
176 Params *params = (Params*)arg;
177 ModelType *model = (ModelType*)(params->model);
178 ReadReader<ReadType> *reader = (ReadReader<ReadType>*)(params->reader);
179 HitContainer<HitType> *hitv = (HitContainer<HitType>*)(params->hitv);
180 double *ncpv = (double*)(params->ncpv);
181 ModelType *mhp = (ModelType*)(params->mhp);
182 double *countv = (double*)(params->countv);
184 bool needCalcConPrb = model->getNeedCalcConPrb();
188 READ_INT_TYPE N = hitv->getN();
190 vector<double> fracs; //to remove this, do calculation twice
191 HIT_INT_TYPE fr, to, id;
193 if (needCalcConPrb || updateModel) { reader->reset(); }
194 if (updateModel) { mhp->init(); }
196 memset(countv, 0, sizeof(double) * (M + 1));
197 for (READ_INT_TYPE i = 0; i < N; i++) {
198 if (needCalcConPrb || updateModel) {
199 general_assert(reader->next(read), "Can not load a read!");
202 fr = hitv->getSAt(i);
203 to = hitv->getSAt(i + 1);
204 fracs.resize(to - fr + 1);
208 if (needCalcConPrb) { ncpv[i] = model->getNoiseConPrb(read); }
209 fracs[0] = probv[0] * ncpv[i];
210 if (fracs[0] < EPSILON) fracs[0] = 0.0;
212 for (HIT_INT_TYPE j = fr; j < to; j++) {
213 HitType &hit = hitv->getHitAt(j);
214 if (needCalcConPrb) { hit.setConPrb(model->getConPrb(read, hit)); }
216 fracs[id] = probv[hit.getSid()] * hit.getConPrb();
217 if (fracs[id] < EPSILON) fracs[id] = 0.0;
221 if (sum >= EPSILON) {
223 countv[0] += fracs[0];
224 if (updateModel) { mhp->updateNoise(read, fracs[0]); }
225 if (calcExpectedWeights) { ncpv[i] = fracs[0]; }
226 for (HIT_INT_TYPE j = fr; j < to; j++) {
227 HitType &hit = hitv->getHitAt(j);
230 countv[hit.getSid()] += fracs[id];
231 if (updateModel) { mhp->update(read, hit, fracs[id]); }
232 if (calcExpectedWeights) { hit.setConPrb(fracs[id]); }
235 else if (calcExpectedWeights) {
237 for (HIT_INT_TYPE j = fr; j < to; j++) {
238 HitType &hit = hitv->getHitAt(j);
247 template<class ReadType, class HitType, class ModelType>
248 void* calcConProbs(void* arg) {
249 Params *params = (Params*)arg;
250 ModelType *model = (ModelType*)(params->model);
251 ReadReader<ReadType> *reader = (ReadReader<ReadType>*)(params->reader);
252 HitContainer<HitType> *hitv = (HitContainer<HitType>*)(params->hitv);
253 double *ncpv = (double*)(params->ncpv);
256 READ_INT_TYPE N = hitv->getN();
259 assert(model->getNeedCalcConPrb());
262 for (READ_INT_TYPE i = 0; i < N; i++) {
263 general_assert(reader->next(read), "Can not load a read!");
265 fr = hitv->getSAt(i);
266 to = hitv->getSAt(i + 1);
268 ncpv[i] = model->getNoiseConPrb(read);
269 for (HIT_INT_TYPE j = fr; j < to; j++) {
270 HitType &hit = hitv->getHitAt(j);
271 hit.setConPrb(model->getConPrb(read, hit));
278 template<class ModelType>
279 void writeResults(ModelType& model, double* counts) {
280 sprintf(modelF, "%s.model", statName);
282 writeResultsEM(M, refName, imdName, transcripts, theta, eel, countvs[0]);
285 template<class ReadType, class HitType, class ModelType>
286 void release(ReadReader<ReadType> **readers, HitContainer<HitType> **hitvs, double **ncpvs, ModelType **mhps) {
288 for (int i = 0; i < nThreads; i++) {
293 for (int i = 0; i < nThreads; i++) {
305 inline bool doesUpdateModel(int ROUND) {
306 // return ROUND <= 20 || ROUND % 100 == 0;
310 //Including initialize, algorithm and results saving
311 template<class ReadType, class HitType, class ModelType>
318 double bChange = 0.0, change = 0.0; // bChange : biggest change
321 ModelType model(mparams); //master model
322 ReadReader<ReadType> **readers;
323 HitContainer<HitType> **hitvs;
325 ModelType **mhps; //model helpers
327 Params fparams[nThreads];
328 pthread_t threads[nThreads];
333 //initialize boolean variables
334 updateModel = calcExpectedWeights = false;
337 theta.resize(M + 1, 0.0);
338 init<ReadType, HitType, ModelType>(readers, hitvs, ncpvs, mhps);
340 //set initial parameters
342 theta[0] = max(N0 * 1.0 / (N_tot - N2), 1e-8);
343 double val = (1.0 - theta[0]) / M;
344 for (int i = 1; i <= M; i++) theta[i] = val;
346 model.estimateFromReads(imdName);
348 for (int i = 0; i < nThreads; i++) {
349 fparams[i].model = (void*)(&model);
351 fparams[i].reader = (void*)readers[i];
352 fparams[i].hitv = (void*)hitvs[i];
353 fparams[i].ncpv = (void*)ncpvs[i];
354 fparams[i].mhp = (void*)mhps[i];
355 fparams[i].countv = (void*)countvs[i];
358 /* set thread attribute to be joinable */
359 pthread_attr_init(&attr);
360 pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_JOINABLE);
366 updateModel = doesUpdateModel(ROUND);
368 for (int i = 0; i <= M; i++) probv[i] = theta[i];
371 for (int i = 0; i < nThreads; i++) {
372 rc = pthread_create(&threads[i], &attr, E_STEP<ReadType, HitType, ModelType>, (void*)(&fparams[i]));
373 pthread_assert(rc, "pthread_create", "Cannot create thread " + itos(i) + " (numbered from 0) at ROUND " + itos(ROUND) + "!");
376 for (int i = 0; i < nThreads; i++) {
377 rc = pthread_join(threads[i], NULL);
378 pthread_assert(rc, "pthread_join", "Cannot join thread " + itos(i) + " (numbered from 0) at ROUND " + itos(ROUND) + "!");
381 model.setNeedCalcConPrb(false);
383 for (int i = 1; i < nThreads; i++) {
384 for (int j = 0; j <= M; j++) {
385 countvs[0][j] += countvs[i][j];
394 for (int i = 0; i <= M; i++) sum += countvs[0][i];
395 assert(sum >= EPSILON);
396 for (int i = 0; i <= M; i++) theta[i] = countvs[0][i] / sum;
400 for (int i = 0; i < nThreads; i++) { model.collect(*mhps[i]); }
405 bChange = 0.0; totNum = 0;
406 for (int i = 0; i <= M; i++)
407 if (probv[i] >= 1e-7) {
408 change = fabs(theta[i] - probv[i]) / probv[i];
409 if (change >= STOP_CRITERIA) ++totNum;
410 if (bChange < change) bChange = change;
413 if (verbose) { cout<< "ROUND = "<< ROUND<< ", SUM = "<< setprecision(15)<< sum<< ", bChange = " << setprecision(6)<< bChange<< ", totNum = " << totNum<< endl; }
414 } while (ROUND < MIN_ROUND || (totNum > 0 && ROUND < MAX_ROUND));
415 // } while (ROUND < 1);
417 if (totNum > 0) { cout<< "Warning: RSEM reaches "<< MAX_ROUND<< " iterations before meeting the convergence criteria."<< endl; }
419 //generate output file used by Gibbs sampler
421 if (model.getNeedCalcConPrb()) {
422 for (int i = 0; i < nThreads; i++) {
423 rc = pthread_create(&threads[i], &attr, calcConProbs<ReadType, HitType, ModelType>, (void*)(&fparams[i]));
424 pthread_assert(rc, "pthread_create", "Cannot create thread " + itos(i) + " (numbered from 0) when generating files for Gibbs sampler!");
426 for (int i = 0; i < nThreads; i++) {
427 rc = pthread_join(threads[i], NULL);
428 pthread_assert(rc, "pthread_join", "Cannot join thread " + itos(i) + " (numbered from 0) when generating files for Gibbs sampler!");
431 model.setNeedCalcConPrb(false);
433 sprintf(out_for_gibbs_F, "%s.ofg", imdName);
434 ofstream fout(out_for_gibbs_F);
435 fout<< M<< " "<< N0<< endl;
436 for (int i = 0; i < nThreads; i++) {
437 READ_INT_TYPE numN = hitvs[i]->getN();
438 for (READ_INT_TYPE j = 0; j < numN; j++) {
439 HIT_INT_TYPE fr = hitvs[i]->getSAt(j);
440 HIT_INT_TYPE to = hitvs[i]->getSAt(j + 1);
441 HIT_INT_TYPE totNum = 0;
443 if (ncpvs[i][j] >= EPSILON) { ++totNum; fout<< "0 "<< setprecision(15)<< ncpvs[i][j]<< " "; }
444 for (HIT_INT_TYPE k = fr; k < to; k++) {
445 HitType &hit = hitvs[i]->getHitAt(k);
446 if (hit.getConPrb() >= EPSILON) {
448 fout<< hit.getSid()<< " "<< setprecision(15)<< hit.getConPrb()<< " ";
452 if (totNum > 0) { fout<< endl; }
458 //calculate expected weights and counts using learned parameters
459 //just use the raw theta learned from the data, do not correct for eel or mw
460 updateModel = false; calcExpectedWeights = true;
461 for (int i = 0; i <= M; i++) probv[i] = theta[i];
462 for (int i = 0; i < nThreads; i++) {
463 rc = pthread_create(&threads[i], &attr, E_STEP<ReadType, HitType, ModelType>, (void*)(&fparams[i]));
464 pthread_assert(rc, "pthread_create", "Cannot create thread " + itos(i) + " (numbered from 0) when calculating expected weights!");
466 for (int i = 0; i < nThreads; i++) {
467 rc = pthread_join(threads[i], NULL);
468 pthread_assert(rc, "pthread_join", "Cannot join thread " + itos(i) + " (numbered from 0) when calculating expected weights!");
470 model.setNeedCalcConPrb(false);
471 for (int i = 1; i < nThreads; i++) {
472 for (int j = 0; j <= M; j++) {
473 countvs[0][j] += countvs[i][j];
478 /* destroy attribute */
479 pthread_attr_destroy(&attr);
482 sprintf(thetaF, "%s.theta", statName);
483 fo = fopen(thetaF, "w");
484 fprintf(fo, "%d\n", M + 1);
487 for (int i = 0; i < M; i++) fprintf(fo, "%.15g ", theta[i]);
488 fprintf(fo, "%.15g\n", theta[M]);
490 //calculate expected effective lengths for each isoform
491 calcExpectedEffectiveLengths<ModelType>(M, refs, model, eel);
492 polishTheta(M, theta, eel, model.getMW());
495 for (int i = 0; i < M; i++) fprintf(fo, "%.15g ", theta[i]);
496 fprintf(fo, "%.15g\n", theta[M]);
500 writeResults<ModelType>(model, countvs[0]);
503 sprintf(outBamF, "%s.transcript.bam", outName);
506 READ_INT_TYPE local_N;
507 HIT_INT_TYPE fr, to, len, id;
509 engine_type engine(hasSeed ? seed : time(NULL));
510 uniform_01_dist uniform_01;
511 uniform_01_generator rg(engine, uniform_01);
513 if (verbose) cout<< "Begin to sample reads from their posteriors."<< endl;
514 for (int i = 0; i < nThreads; i++) {
515 local_N = hitvs[i]->getN();
516 for (READ_INT_TYPE j = 0; j < local_N; j++) {
517 fr = hitvs[i]->getSAt(j);
518 to = hitvs[i]->getSAt(j + 1);
521 arr[0] = ncpvs[i][j];
522 for (HIT_INT_TYPE k = fr; k < to; k++) arr[k - fr + 1] = arr[k - fr] + hitvs[i]->getHitAt(k).getConPrb();
523 id = (arr[len - 1] < EPSILON ? -1 : sample(rg, arr, len)); // if all entries in arr are 0, let id be -1
524 for (HIT_INT_TYPE k = fr; k < to; k++) hitvs[i]->getHitAt(k).setConPrb(k - fr + 1 == id ? 1.0 : 0.0);
528 if (verbose) cout<< "Sampling is finished."<< endl;
531 BamWriter writer(inpSamType, inpSamF, pt_fn_list, outBamF, transcripts);
532 HitWrapper<HitType> wrapper(nThreads, hitvs);
533 writer.work(wrapper);
536 release<ReadType, HitType, ModelType>(readers, hitvs, ncpvs, mhps);
539 int main(int argc, char* argv[]) {
544 printf("Usage : rsem-run-em refName read_type sampleName imdName statName [-p #Threads] [-b samInpType samInpF has_fn_list_? [fn_list]] [-q] [--gibbs-out] [--sampling] [--seed seed]\n\n");
545 printf(" refName: reference name\n");
546 printf(" read_type: 0 single read without quality score; 1 single read with quality score; 2 paired-end read without quality score; 3 paired-end read with quality score.\n");
547 printf(" sampleName: sample's name, including the path\n");
548 printf(" sampleToken: sampleName excludes the path\n");
549 printf(" -p: number of threads which user wants to use. (default: 1)\n");
550 printf(" -b: produce bam format output file. (default: off)\n");
551 printf(" -q: set it quiet\n");
552 printf(" --gibbs-out: generate output file used by Gibbs sampler. (default: off)\n");
553 printf(" --sampling: sample each read from its posterior distribution when bam file is generated. (default: off)\n");
554 printf(" --seed uint32: the seed used for the BAM sampling. (default: off)\n");
555 printf("// model parameters should be in imdName.mparams.\n");
559 time_t a = time(NULL);
561 strcpy(refName, argv[1]);
562 read_type = atoi(argv[2]);
563 strcpy(outName, argv[3]);
564 strcpy(imdName, argv[4]);
565 strcpy(statName, argv[5]);
572 pt_fn_list = pt_chr_list = NULL;
575 for (int i = 6; i < argc; i++) {
576 if (!strcmp(argv[i], "-p")) { nThreads = atoi(argv[i + 1]); }
577 if (!strcmp(argv[i], "-b")) {
579 inpSamType = argv[i + 1][0];
580 strcpy(inpSamF, argv[i + 2]);
581 if (atoi(argv[i + 3]) == 1) {
582 strcpy(fn_list, argv[i + 4]);
583 pt_fn_list = (char*)(&fn_list);
586 if (!strcmp(argv[i], "-q")) { quiet = true; }
587 if (!strcmp(argv[i], "--gibbs-out")) { genGibbsOut = true; }
588 if (!strcmp(argv[i], "--sampling")) { bamSampling = true; }
589 if (!strcmp(argv[i], "--seed")) {
591 int len = strlen(argv[i + 1]);
593 for (int k = 0; k < len; k++) seed = seed * 10 + (argv[i + 1][k] - '0');
597 general_assert(nThreads > 0, "Number of threads should be bigger than 0!");
602 sprintf(refF, "%s.seq", refName);
606 sprintf(tiF, "%s.ti", refName);
607 transcripts.readFrom(tiF);
609 sprintf(cntF, "%s.cnt", statName);
612 general_assert(fin.is_open(), "Cannot open " + cstrtos(cntF) + "! It may not exist.");
614 fin>>N0>>N1>>N2>>N_tot;
617 general_assert(N1 > 0, "There are no alignable reads!");
619 if ((READ_INT_TYPE)nThreads > N1) nThreads = N1;
621 //set model parameters
623 mparams.N[0] = N0; mparams.N[1] = N1; mparams.N[2] = N2;
624 mparams.refs = &refs;
626 sprintf(mparamsF, "%s.mparams", imdName);
629 general_assert(fin.is_open(), "Cannot open " + cstrtos(mparamsF) + "It may not exist.");
631 fin>> mparams.minL>> mparams.maxL>> mparams.probF;
632 int val; // 0 or 1 , for estRSPD
634 mparams.estRSPD = (val != 0);
635 fin>> mparams.B>> mparams.mate_minL>> mparams.mate_maxL>> mparams.mean>> mparams.sd;
636 fin>> mparams.seedLen;
641 case 0 : EM<SingleRead, SingleHit, SingleModel>(); break;
642 case 1 : EM<SingleReadQ, SingleHit, SingleQModel>(); break;
643 case 2 : EM<PairedEndRead, PairedEndHit, PairedEndModel>(); break;
644 case 3 : EM<PairedEndReadQ, PairedEndHit, PairedEndQModel>(); break;
645 default : fprintf(stderr, "Unknown Read Type!\n"); exit(-1);
648 time_t b = time(NULL);
650 printTimeUsed(a, b, "EM.cpp");