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