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