bayesian.cpp

   1 /*
   2  *  bayesian.cpp
   3  *  Mothur
   4  *
   5  *  Created by westcott on 11/3/09.
   6  *  Copyright 2009 Schloss Lab. All rights reserved.
   7  *
   8  */
   9
  10 #include "bayesian.h"
  11 #include "kmer.hpp"
  12 #include "phylosummary.h"
  13
  14 /**************************************************************************************************/
  15 Bayesian::Bayesian(string tfile, string tempFile, string method, int ksize, int cutoff, int i) :
  16 Classify(), kmerSize(ksize), confidenceThreshold(cutoff), iters(i)  {
  17         try {
  18
  19                 /************calculate the probablity that each word will be in a specific taxonomy*************/
  20                 string tfileroot = tfile.substr(0,tfile.find_last_of(".")+1);
  21                 string tempfileroot = getRootName(getSimpleName(tempFile));
  22                 string phyloTreeName = tfileroot + "tree.train";
  23                 string phyloTreeSumName = tfileroot + "tree.sum";
  24                 string probFileName = tfileroot + tempfileroot + char('0'+ kmerSize) + "mer.prob";
  25                 string probFileName2 = tfileroot + tempfileroot + char('0'+ kmerSize) + "mer.numNonZero";
  26
  27                 ofstream out;
  28                 ofstream out2;
  29
  30                 ifstream phyloTreeTest(phyloTreeName.c_str());
  31                 ifstream probFileTest2(probFileName2.c_str());
  32                 ifstream probFileTest(probFileName.c_str());
  33                 ifstream probFileTest3(phyloTreeSumName.c_str());
  34
  35                 int start = time(NULL);
  36
  37                 if(probFileTest && probFileTest2 && phyloTreeTest && probFileTest3){
  38                         m->mothurOut("Reading template taxonomy...     "); cout.flush();
  39
  40                         phyloTree = new PhyloTree(phyloTreeTest, phyloTreeName);
  41
  42                         m->mothurOut("DONE."); m->mothurOutEndLine();
  43
  44                         genusNodes = phyloTree->getGenusNodes();
  45                         genusTotals = phyloTree->getGenusTotals();
  46
  47                         m->mothurOut("Reading template probabilities...     "); cout.flush();
  48                         readProbFile(probFileTest, probFileTest2, probFileName, probFileName2);
  49
  50                 }else{
  51
  52                         //create search database and names vector
  53                         generateDatabaseAndNames(tfile, tempFile, method, ksize, 0.0, 0.0, 0.0, 0.0);
  54
  55                         //prevents errors caused by creating shortcut files if you had an error in the sanity check.
  56                         if (m->control_pressed) {  remove(phyloTreeName.c_str());  remove(probFileName.c_str()); remove(probFileName2.c_str()); }
  57                         else{
  58                                 genusNodes = phyloTree->getGenusNodes();
  59                                 genusTotals = phyloTree->getGenusTotals();
  60
  61                                 m->mothurOut("Calculating template taxonomy tree...     "); cout.flush();
  62
  63                                 phyloTree->printTreeNodes(phyloTreeName);
  64
  65                                 m->mothurOut("DONE."); m->mothurOutEndLine();
  66
  67                                 m->mothurOut("Calculating template probabilities...     "); cout.flush();
  68
  69                                 numKmers = database->getMaxKmer() + 1;
  70
  71                                 //initialze probabilities
  72                                 wordGenusProb.resize(numKmers);
  73
  74                                 for (int j = 0; j < wordGenusProb.size(); j++) {        wordGenusProb[j].resize(genusNodes.size());             }
  75
  76                                 ofstream out;
  77                                 ofstream out2;
  78
  79                                 #ifdef USE_MPI
  80                                         int pid;
  81                                         MPI_Comm_rank(MPI_COMM_WORLD, &pid); //find out who we are
  82
  83                                         if (pid == 0) {
  84                                 #endif
  85
  86
  87                                 openOutputFile(probFileName, out);
  88
  89                                 out << numKmers << endl;
  90
  91                                 openOutputFile(probFileName2, out2);
  92
  93                                 #ifdef USE_MPI
  94                                         }
  95                                 #endif
  96
  97
  98                                 //for each word
  99                                 for (int i = 0; i < numKmers; i++) {
 100                                         if (m->control_pressed) {  break; }
 101
 102                                         #ifdef USE_MPI
 103                                                 MPI_Comm_rank(MPI_COMM_WORLD, &pid); //find out who we are
 104
 105                                                 if (pid == 0) {
 106                                         #endif
 107
 108                                         out << i << '\t';
 109
 110                                         #ifdef USE_MPI
 111                                                 }
 112                                         #endif
 113
 114                                         vector<int> seqsWithWordi = database->getSequencesWithKmer(i);
 115
 116                                         map<int, int> count;
 117                                         for (int k = 0; k < genusNodes.size(); k++) {  count[genusNodes[k]] = 0;  }
 118
 119                                         //for each sequence with that word
 120                                         for (int j = 0; j < seqsWithWordi.size(); j++) {
 121                                                 int temp = phyloTree->getIndex(names[seqsWithWordi[j]]);
 122                                                 count[temp]++;  //increment count of seq in this genus who have this word
 123                                         }
 124
 125                                         //probabilityInTemplate = (# of seqs with that word in template + 0.05) / (total number of seqs in template + 1);
 126                                         float probabilityInTemplate = (seqsWithWordi.size() + 0.50) / (float) (names.size() + 1);
 127
 128                                         int numNotZero = 0;
 129                                         for (int k = 0; k < genusNodes.size(); k++) {
 130                                                 //probabilityInThisTaxonomy = (# of seqs with that word in this taxonomy + probabilityInTemplate) / (total number of seqs in this taxonomy + 1);
 131                                                 wordGenusProb[i][k] = log((count[genusNodes[k]] + probabilityInTemplate) / (float) (genusTotals[k] + 1));
 132                                                 if (count[genusNodes[k]] != 0) {
 133                                                         #ifdef USE_MPI
 134                                                                 int pid;
 135                                                                 MPI_Comm_rank(MPI_COMM_WORLD, &pid); //find out who we are
 136
 137                                                                 if (pid == 0) {
 138                                                         #endif
 139
 140                                                         out << k << '\t' << wordGenusProb[i][k] << '\t';
 141
 142                                                         #ifdef USE_MPI
 143                                                                 }
 144                                                         #endif
 145
 146                                                         numNotZero++;
 147                                                 }
 148                                         }
 149
 150                                         #ifdef USE_MPI
 151                                                 MPI_Comm_rank(MPI_COMM_WORLD, &pid); //find out who we are
 152
 153                                                 if (pid == 0) {
 154                                         #endif
 155
 156                                         out << endl;
 157                                         out2 << probabilityInTemplate << '\t' << numNotZero << endl;
 158
 159                                         #ifdef USE_MPI
 160                                                 }
 161                                         #endif
 162                                 }
 163
 164                                 #ifdef USE_MPI
 165                                         MPI_Comm_rank(MPI_COMM_WORLD, &pid); //find out who we are
 166
 167                                         if (pid == 0) {
 168                                 #endif
 169
 170                                 out.close();
 171                                 out2.close();
 172
 173                                 #ifdef USE_MPI
 174                                         }
 175                                 #endif
 176
 177                                 //read in new phylotree with less info. - its faster
 178                                 ifstream phyloTreeTest(phyloTreeName.c_str());
 179                                 delete phyloTree;
 180
 181                                 phyloTree = new PhyloTree(phyloTreeTest, phyloTreeName);
 182                         }
 183                 }
 184
 185                 m->mothurOut("DONE."); m->mothurOutEndLine();
 186                 m->mothurOut("It took " + toString(time(NULL) - start) + " seconds get probabilities. "); m->mothurOutEndLine();
 187         }
 188         catch(exception& e) {
 189                 m->errorOut(e, "Bayesian", "Bayesian");
 190                 exit(1);
 191         }
 192 }
 193 /**************************************************************************************************/
 194 Bayesian::~Bayesian() {
 195         try {
 196                  delete phyloTree;
 197                  if (database != NULL) {  delete database; }
 198         }
 199         catch(exception& e) {
 200                 m->errorOut(e, "Bayesian", "~Bayesian");
 201                 exit(1);
 202         }
 203 }
 204
 205 /**************************************************************************************************/
 206 string Bayesian::getTaxonomy(Sequence* seq) {
 207         try {
 208                 string tax = "";
 209                 Kmer kmer(kmerSize);
 210
 211                 //get words contained in query
 212                 //getKmerString returns a string where the index in the string is hte kmer number
 213                 //and the character at that index can be converted to be the number of times that kmer was seen
 214
 215                 string queryKmerString = kmer.getKmerString(seq->getUnaligned());
 216
 217                 vector<int> queryKmers;
 218                 for (int i = 0; i < queryKmerString.length(); i++) {
 219                         if (queryKmerString[i] != '!') { //this kmer is in the query
 220                                 queryKmers.push_back(i);
 221                         }
 222                 }
 223
 224                 if (queryKmers.size() == 0) {  m->mothurOut(seq->getName() + "is bad."); m->mothurOutEndLine(); return "bad seq"; }
 225
 226                 int index = getMostProbableTaxonomy(queryKmers);
 227
 228                 if (m->control_pressed) { return tax; }
 229 //cout << seq->getName() << '\t' << index << endl;
 230                 //bootstrap - to set confidenceScore
 231                 int numToSelect = queryKmers.size() / 8;
 232                 tax = bootstrapResults(queryKmers, index, numToSelect);
 233
 234                 return tax;
 235         }
 236         catch(exception& e) {
 237                 m->errorOut(e, "Bayesian", "getTaxonomy");
 238                 exit(1);
 239         }
 240 }
 241 /**************************************************************************************************/
 242 string Bayesian::bootstrapResults(vector<int> kmers, int tax, int numToSelect) {
 243         try {
 244
 245                 map<int, int> confidenceScores;
 246
 247                 map<int, int>::iterator itBoot;
 248                 map<int, int>::iterator itBoot2;
 249                 map<int, int>::iterator itConvert;
 250
 251                 for (int i = 0; i < iters; i++) {
 252                         if (m->control_pressed) { return "control"; }
 253
 254                         vector<int> temp;
 255
 256                         for (int j = 0; j < numToSelect; j++) {
 257                                 int index = int(rand() % kmers.size());
 258
 259                                 //add word to temp
 260                                 temp.push_back(kmers[index]);
 261                         }
 262
 263                         //get taxonomy
 264                         int newTax = getMostProbableTaxonomy(temp);
 265                         TaxNode taxonomyTemp = phyloTree->get(newTax);
 266
 267                         //add to confidence results
 268                         while (taxonomyTemp.level != 0) { //while you are not at the root
 269
 270                                 itBoot2 = confidenceScores.find(newTax); //is this a classification we already have a count on
 271
 272                                 if (itBoot2 == confidenceScores.end()) { //not already in confidence scores
 273                                         confidenceScores[newTax] = 1;
 274                                 }else{
 275                                         confidenceScores[newTax]++;
 276                                 }
 277
 278                                 newTax = taxonomyTemp.parent;
 279                                 taxonomyTemp = phyloTree->get(newTax);
 280                         }
 281
 282                 }
 283
 284                 string confidenceTax = "";
 285                 simpleTax = "";
 286
 287                 int seqTaxIndex = tax;
 288                 TaxNode seqTax = phyloTree->get(tax);
 289
 290                 while (seqTax.level != 0) { //while you are not at the root
 291
 292                                 itBoot2 = confidenceScores.find(seqTaxIndex); //is this a classification we already have a count on
 293
 294                                 int confidence = 0;
 295                                 if (itBoot2 != confidenceScores.end()) { //already in confidence scores
 296                                         confidence = confidenceScores[seqTaxIndex];
 297                                 }
 298
 299                                 if (((confidence/(float)iters) * 100) >= confidenceThreshold) {
 300                                         confidenceTax = seqTax.name + "(" + toString(((confidence/(float)iters) * 100)) + ");" + confidenceTax;
 301                                         simpleTax = seqTax.name + ";" + simpleTax;
 302                                 }
 303
 304                                 seqTaxIndex = seqTax.parent;
 305                                 seqTax = phyloTree->get(seqTax.parent);
 306                 }
 307
 308                 if (confidenceTax == "") { confidenceTax = "unclassified;"; simpleTax = "unclassified;"; }
 309                 return confidenceTax;
 310
 311         }
 312         catch(exception& e) {
 313                 m->errorOut(e, "Bayesian", "bootstrapResults");
 314                 exit(1);
 315         }
 316 }
 317 /**************************************************************************************************/
 318 int Bayesian::getMostProbableTaxonomy(vector<int> queryKmer) {
 319         try {
 320                 int indexofGenus = 0;
 321
 322                 double maxProbability = -1000000.0;
 323                 //find taxonomy with highest probability that this sequence is from it
 324                 for (int k = 0; k < genusNodes.size(); k++) {
 325                         //for each taxonomy calc its probability
 326                         double prob = 1.0;
 327                         for (int i = 0; i < queryKmer.size(); i++) {
 328                                 prob += wordGenusProb[queryKmer[i]][k];
 329                         }
 330
 331                         //is this the taxonomy with the greatest probability?
 332                         if (prob > maxProbability) {
 333                                 indexofGenus = genusNodes[k];
 334                                 maxProbability = prob;
 335                         }
 336                 }
 337
 338                 return indexofGenus;
 339         }
 340         catch(exception& e) {
 341                 m->errorOut(e, "Bayesian", "getMostProbableTaxonomy");
 342                 exit(1);
 343         }
 344 }
 345 /*************************************************************************************************
 346 map<string, int> Bayesian::parseTaxMap(string newTax) {
 347         try{
 348
 349                 map<string, int> parsed;
 350
 351                 newTax = newTax.substr(0, newTax.length()-1);  //get rid of last ';'
 352
 353                 //parse taxonomy
 354                 string individual;
 355                 while (newTax.find_first_of(';') != -1) {
 356                         individual = newTax.substr(0,newTax.find_first_of(';'));
 357                         newTax = newTax.substr(newTax.find_first_of(';')+1, newTax.length());
 358                         parsed[individual] = 1;
 359                 }
 360
 361                 //get last one
 362                 parsed[newTax] = 1;
 363
 364                 return parsed;
 365
 366         }
 367         catch(exception& e) {
 368                 m->errorOut(e, "Bayesian", "parseTax");
 369                 exit(1);
 370         }
 371 }
 372 /**************************************************************************************************/
 373 void Bayesian::readProbFile(ifstream& in, ifstream& inNum, string inName, string inNumName) {
 374         try{
 375
 376                 #ifdef USE_MPI
 377
 378                         int pid, num, num2, processors;
 379                         vector<unsigned long int> positions;
 380                         vector<unsigned long int> positions2;
 381
 382                         MPI_Status status;
 383                         MPI_File inMPI;
 384                         MPI_File inMPI2;
 385                         MPI_Comm_rank(MPI_COMM_WORLD, &pid); //find out who we are
 386                         MPI_Comm_size(MPI_COMM_WORLD, &processors);
 387                         int tag = 2001;
 388
 389                         char inFileName[1024];
 390                         strcpy(inFileName, inNumName.c_str());
 391
 392                         char inFileName2[1024];
 393                         strcpy(inFileName2, inName.c_str());
 394
 395                         MPI_File_open(MPI_COMM_WORLD, inFileName, MPI_MODE_RDONLY, MPI_INFO_NULL, &inMPI);  //comm, filename, mode, info, filepointer
 396                         MPI_File_open(MPI_COMM_WORLD, inFileName2, MPI_MODE_RDONLY, MPI_INFO_NULL, &inMPI2);  //comm, filename, mode, info, filepointer
 397
 398                         if (pid == 0) {
 399                                 positions = setFilePosEachLine(inNumName, num);
 400                                 positions2 = setFilePosEachLine(inName, num2);
 401
 402                                 for(int i = 1; i < processors; i++) {
 403                                         MPI_Send(&num, 1, MPI_INT, i, tag, MPI_COMM_WORLD);
 404                                         MPI_Send(&positions[0], (num+1), MPI_LONG, i, tag, MPI_COMM_WORLD);
 405
 406                                         MPI_Send(&num2, 1, MPI_INT, i, tag, MPI_COMM_WORLD);
 407                                         MPI_Send(&positions2[0], (num2+1), MPI_LONG, i, tag, MPI_COMM_WORLD);
 408                                 }
 409
 410                         }else{
 411                                 MPI_Recv(&num, 1, MPI_INT, 0, tag, MPI_COMM_WORLD, &status);
 412                                 positions.resize(num+1);
 413                                 MPI_Recv(&positions[0], (num+1), MPI_LONG, 0, tag, MPI_COMM_WORLD, &status);
 414
 415                                 MPI_Recv(&num2, 1, MPI_INT, 0, tag, MPI_COMM_WORLD, &status);
 416                                 positions2.resize(num2+1);
 417                                 MPI_Recv(&positions2[0], (num2+1), MPI_LONG, 0, tag, MPI_COMM_WORLD, &status);
 418                         }
 419
 420                         //read numKmers
 421                         int length = positions2[1] - positions2[0];
 422                         char* buf = new char[length];
 423
 424                         MPI_File_read_at(inMPI2, positions2[0], buf, length, MPI_CHAR, &status);
 425
 426                         string tempBuf = buf;
 427                         if (tempBuf.length() > length) { tempBuf = tempBuf.substr(0, length); }
 428                         delete buf;
 429
 430                         istringstream iss (tempBuf,istringstream::in);
 431                         iss >> numKmers;
 432
 433                         //initialze probabilities
 434                         wordGenusProb.resize(numKmers);
 435
 436                         for (int j = 0; j < wordGenusProb.size(); j++) {        wordGenusProb[j].resize(genusNodes.size());             }
 437
 438                         int kmer, name;
 439                         vector<int> numbers; numbers.resize(numKmers);
 440                         float prob;
 441                         vector<float> zeroCountProb; zeroCountProb.resize(numKmers);
 442
 443                         //read file
 444                         for(int i=0;i<num;i++){
 445                                 //read next sequence
 446                                 length = positions[i+1] - positions[i];
 447                                 char* buf4 = new char[length];
 448
 449                                 MPI_File_read_at(inMPI, positions[i], buf4, length, MPI_CHAR, &status);
 450
 451                                 tempBuf = buf4;
 452                                 if (tempBuf.length() > length) { tempBuf = tempBuf.substr(0, length); }
 453                                 delete buf4;
 454
 455                                 istringstream iss (tempBuf,istringstream::in);
 456                                 iss >> zeroCountProb[i] >> numbers[i];
 457                         }
 458
 459                         MPI_File_close(&inMPI);
 460
 461                         for(int i=1;i<num2;i++){
 462                                 //read next sequence
 463                                 length = positions2[i+1] - positions2[i];
 464                                 char* buf4 = new char[length];
 465
 466                                 MPI_File_read_at(inMPI2, positions2[i], buf4, length, MPI_CHAR, &status);
 467
 468                                 tempBuf = buf4;
 469                                 if (tempBuf.length() > length) { tempBuf = tempBuf.substr(0, length); }
 470                                 delete buf4;
 471
 472                                 istringstream iss (tempBuf,istringstream::in);
 473
 474                                 iss >> kmer;
 475
 476                                 //set them all to zero value
 477                                 for (int i = 0; i < genusNodes.size(); i++) {
 478                                         wordGenusProb[kmer][i] = log(zeroCountProb[kmer] / (float) (genusTotals[i]+1));
 479                                 }
 480
 481                                 //get probs for nonzero values
 482                                 for (int i = 0; i < numbers[kmer]; i++) {
 483                                         iss >> name >> prob;
 484                                         wordGenusProb[kmer][name] = prob;
 485                                 }
 486
 487                         }
 488                         MPI_File_close(&inMPI2);
 489                         MPI_Barrier(MPI_COMM_WORLD); //make everyone wait - just in case
 490                 #else
 491
 492                         in >> numKmers; gobble(in);
 493
 494                         //initialze probabilities
 495                         wordGenusProb.resize(numKmers);
 496
 497                         for (int j = 0; j < wordGenusProb.size(); j++) {        wordGenusProb[j].resize(genusNodes.size());             }
 498
 499                         int kmer, name, count;  count = 0;
 500                         vector<int> num; num.resize(numKmers);
 501                         float prob;
 502                         vector<float> zeroCountProb; zeroCountProb.resize(numKmers);
 503
 504                         while (inNum) {
 505                                 inNum >> zeroCountProb[count] >> num[count];
 506                                 count++;
 507                                 gobble(inNum);
 508                         }
 509                         inNum.close();
 510
 511                         while(in) {
 512                                 in >> kmer;
 513
 514                                 //set them all to zero value
 515                                 for (int i = 0; i < genusNodes.size(); i++) {
 516                                         wordGenusProb[kmer][i] = log(zeroCountProb[kmer] / (float) (genusTotals[i]+1));
 517                                 }
 518
 519                                 //get probs for nonzero values
 520                                 for (int i = 0; i < num[kmer]; i++) {
 521                                         in >> name >> prob;
 522                                         wordGenusProb[kmer][name] = prob;
 523                                 }
 524
 525                                 gobble(in);
 526                         }
 527                         in.close();
 528
 529                 #endif
 530         }
 531         catch(exception& e) {
 532                 m->errorOut(e, "Bayesian", "readProbFile");
 533                 exit(1);
 534         }
 535 }
 536 /**************************************************************************************************/
 537
 538
 539
 540
 541
 542