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 "rawtrainingdatamaker.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                 ifstream phyloTreeTest(phyloTreeName.c_str());
  22
  23                 ofstream out;
  24                 string probFileName = tfile.substr(0,tfile.find_last_of(".")+1) + tempFile.substr(0,tempFile.find_last_of(".")+1) + char('0'+ kmerSize) + "mer.prob";
  25                 ifstream probFileTest(probFileName.c_str());
  26
  27                 ofstream out2;
  28                 string probFileName2 = tfile.substr(0,tfile.find_last_of(".")+1) + tempFile.substr(0,tempFile.find_last_of(".")+1) + char('0'+ kmerSize) + "mer.numNonZero";
  29                 ifstream probFileTest2(probFileName2.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);
  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);
  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                         ofstream out;
  70                         openOutputFile(probFileName, out);
  71
  72                         out << numKmers << endl;
  73
  74                         ofstream out2;
  75                         openOutputFile(probFileName2, out2);
  76
  77                         //for each word
  78                         for (int i = 0; i < numKmers; i++) {
  79                                 if (m->control_pressed) { break; }
  80
  81                                 out << i << '\t';
  82
  83                                 vector<int> seqsWithWordi = database->getSequencesWithKmer(i);
  84
  85                                 map<int, int> count;
  86                                 for (int k = 0; k < genusNodes.size(); k++) {  count[genusNodes[k]] = 0;  }
  87
  88                                 //for each sequence with that word
  89                                 for (int j = 0; j < seqsWithWordi.size(); j++) {
  90                                         int temp = phyloTree->getIndex(names[seqsWithWordi[j]]);
  91                                         count[temp]++;  //increment count of seq in this genus who have this word
  92                                 }
  93
  94                                 //probabilityInTemplate = (# of seqs with that word in template + 0.05) / (total number of seqs in template + 1);
  95                                 float probabilityInTemplate = (seqsWithWordi.size() + 0.50) / (float) (names.size() + 1);
  96
  97                                 int numNotZero = 0;
  98                                 for (int k = 0; k < genusNodes.size(); k++) {
  99                                         //probabilityInThisTaxonomy = (# of seqs with that word in this taxonomy + probabilityInTemplate) / (total number of seqs in this taxonomy + 1);
 100                                         wordGenusProb[i][k] = log((count[genusNodes[k]] + probabilityInTemplate) / (float) (genusTotals[k] + 1));
 101                                         if (count[genusNodes[k]] != 0) {  out << k << '\t' << wordGenusProb[i][k] << '\t';  numNotZero++;  }
 102                                 }
 103                                 out << endl;
 104                                 out2 << probabilityInTemplate << '\t' << numNotZero << endl;
 105                         }
 106
 107                         out.close();
 108                         out2.close();
 109
 110                         //read in new phylotree with less info. - its faster
 111                         ifstream phyloTreeTest(phyloTreeName.c_str());
 112                         delete phyloTree;
 113
 114                         phyloTree = new PhyloTree(phyloTreeTest);
 115                 }
 116
 117                 m->mothurOut("DONE."); m->mothurOutEndLine();
 118                 m->mothurOut("It took " + toString(time(NULL) - start) + " seconds get probabilities. "); m->mothurOutEndLine();
 119         }
 120         catch(exception& e) {
 121                 m->errorOut(e, "Bayesian", "Bayesian");
 122                 exit(1);
 123         }
 124 }
 125 /**************************************************************************************************/
 126 string Bayesian::getTaxonomy(Sequence* seq) {
 127         try {
 128                 string tax = "";
 129                 Kmer kmer(kmerSize);
 130
 131                 //get words contained in query
 132                 //getKmerString returns a string where the index in the string is hte kmer number
 133                 //and the character at that index can be converted to be the number of times that kmer was seen
 134
 135                 string queryKmerString = kmer.getKmerString(seq->getUnaligned());
 136
 137                 vector<int> queryKmers;
 138                 for (int i = 0; i < queryKmerString.length(); i++) {
 139                         if (queryKmerString[i] != '!') { //this kmer is in the query
 140                                 queryKmers.push_back(i);
 141                         }
 142                 }
 143
 144                 if (queryKmers.size() == 0) {  m->mothurOut(seq->getName() + "is bad."); m->mothurOutEndLine(); return "bad seq"; }
 145
 146                 int index = getMostProbableTaxonomy(queryKmers);
 147
 148                 if (m->control_pressed) { return tax; }
 149
 150                 //bootstrap - to set confidenceScore
 151                 int numToSelect = queryKmers.size() / 8;
 152                 tax = bootstrapResults(queryKmers, index, numToSelect);
 153
 154                 return tax;
 155         }
 156         catch(exception& e) {
 157                 m->errorOut(e, "Bayesian", "getTaxonomy");
 158                 exit(1);
 159         }
 160 }
 161 /**************************************************************************************************/
 162 string Bayesian::bootstrapResults(vector<int> kmers, int tax, int numToSelect) {
 163         try {
 164
 165                 //taxConfidenceScore.clear(); //clear out previous seqs scores
 166
 167                 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
 168                                                                                 //map of classification to confidence for all areas seen
 169                                                                            //ie. Bacteria;Alphaproteobacteria;Rhizobiales;Azorhizobium_et_rel.;Methylobacterium_et_rel.;Bosea;
 170                                                                            //ie. Bacteria -> 100, Alphaproteobacteria -> 100, Rhizobiales -> 87, Azorhizobium_et_rel. -> 78, Methylobacterium_et_rel. -> 70, Bosea -> 50
 171                 confidenceScores.resize(100);  //if you have more than 100 levels of classification...
 172
 173                 map<string, int>::iterator itBoot;
 174                 map<string, int>::iterator itBoot2;
 175                 map<int, int>::iterator itConvert;
 176
 177                 for (int i = 0; i < iters; i++) {
 178                         if (m->control_pressed) { return "control"; }
 179
 180                         vector<int> temp;
 181
 182                         for (int j = 0; j < numToSelect; j++) {
 183                                 int index = int(rand() % kmers.size());
 184
 185                                 //add word to temp
 186                                 temp.push_back(kmers[index]);
 187                         }
 188
 189                         //get taxonomy
 190                         int newTax = getMostProbableTaxonomy(temp);
 191                         TaxNode taxonomy = phyloTree->get(newTax);
 192
 193                         //add to confidence results
 194                         while (taxonomy.level != 0) { //while you are not at the root
 195
 196                                 itBoot2 = confidenceScores[taxonomy.level].find(taxonomy.name); //is this a classification we already have a count on
 197
 198                                 if (itBoot2 == confidenceScores[taxonomy.level].end()) { //not already in confidence scores
 199                                         confidenceScores[taxonomy.level][taxonomy.name] = 1;
 200                                 }else{
 201                                         confidenceScores[taxonomy.level][taxonomy.name]++;
 202                                 }
 203
 204                                 taxonomy = phyloTree->get(taxonomy.parent);
 205                         }
 206
 207                 }
 208
 209                 string confidenceTax = "";
 210                 simpleTax = "";
 211                 TaxNode seqTax = phyloTree->get(tax);
 212
 213                 while (seqTax.level != 0) { //while you are not at the root
 214
 215                                 itBoot2 = confidenceScores[seqTax.level].find(seqTax.name); //is this a classification we already have a count on
 216
 217                                 int confidence = 0;
 218                                 if (itBoot2 != confidenceScores[seqTax.level].end()) { //not already in confidence scores
 219                                         confidence = confidenceScores[seqTax.level][seqTax.name];
 220                                 }
 221
 222                                 if (confidence >= confidenceThreshold) {
 223                                         confidenceTax = seqTax.name + "(" + toString(((confidence/(float)iters) * 100)) + ");" + confidenceTax;
 224                                         simpleTax = seqTax.name + ";" + simpleTax;
 225                                 }
 226
 227                                 seqTax = phyloTree->get(seqTax.parent);
 228                 }
 229
 230                 if (confidenceTax == "") { confidenceTax = "unclassified;"; simpleTax = "unclassified;"; }
 231                 return confidenceTax;
 232
 233         }
 234         catch(exception& e) {
 235                 m->errorOut(e, "Bayesian", "bootstrapResults");
 236                 exit(1);
 237         }
 238 }
 239 /**************************************************************************************************/
 240 int Bayesian::getMostProbableTaxonomy(vector<int> queryKmer) {
 241         try {
 242                 int indexofGenus = 0;
 243
 244                 double maxProbability = -1000000.0;
 245                 //find taxonomy with highest probability that this sequence is from it
 246                 for (int k = 0; k < genusNodes.size(); k++) {
 247                         //for each taxonomy calc its probability
 248                         double prob = 1.0;
 249                         for (int i = 0; i < queryKmer.size(); i++) {
 250                                 prob += wordGenusProb[queryKmer[i]][k];
 251                         }
 252
 253                         //is this the taxonomy with the greatest probability?
 254                         if (prob > maxProbability) {
 255                                 indexofGenus = genusNodes[k];
 256                                 maxProbability = prob;
 257                         }
 258                 }
 259
 260                 return indexofGenus;
 261         }
 262         catch(exception& e) {
 263                 m->errorOut(e, "Bayesian", "getMostProbableTaxonomy");
 264                 exit(1);
 265         }
 266 }
 267 /*************************************************************************************************
 268 map<string, int> Bayesian::parseTaxMap(string newTax) {
 269         try{
 270
 271                 map<string, int> parsed;
 272
 273                 newTax = newTax.substr(0, newTax.length()-1);  //get rid of last ';'
 274
 275                 //parse taxonomy
 276                 string individual;
 277                 while (newTax.find_first_of(';') != -1) {
 278                         individual = newTax.substr(0,newTax.find_first_of(';'));
 279                         newTax = newTax.substr(newTax.find_first_of(';')+1, newTax.length());
 280                         parsed[individual] = 1;
 281                 }
 282
 283                 //get last one
 284                 parsed[newTax] = 1;
 285
 286                 return parsed;
 287
 288         }
 289         catch(exception& e) {
 290                 m->errorOut(e, "Bayesian", "parseTax");
 291                 exit(1);
 292         }
 293 }
 294 /**************************************************************************************************/
 295 void Bayesian::readProbFile(ifstream& in, ifstream& inNum) {
 296         try{
 297
 298                 in >> numKmers; gobble(in);
 299
 300                 //initialze probabilities
 301                 wordGenusProb.resize(numKmers);
 302
 303                 for (int j = 0; j < wordGenusProb.size(); j++) {        wordGenusProb[j].resize(genusNodes.size());             }
 304
 305                 int kmer, name, count;  count = 0;
 306                 vector<int> num; num.resize(numKmers);
 307                 float prob;
 308                 vector<float> zeroCountProb; zeroCountProb.resize(numKmers);
 309
 310                 while (inNum) {
 311                         inNum >> zeroCountProb[count] >> num[count];
 312                         count++;
 313                         gobble(inNum);
 314                 }
 315                 inNum.close();
 316
 317                 while(in) {
 318                         in >> kmer;
 319
 320                         //set them all to zero value
 321                         for (int i = 0; i < genusNodes.size(); i++) {
 322                                 wordGenusProb[kmer][i] = log(zeroCountProb[kmer] / (float) (genusTotals[i]+1));
 323                         }
 324
 325                         //get probs for nonzero values
 326                         for (int i = 0; i < num[kmer]; i++) {
 327                                 in >> name >> prob;
 328                                 wordGenusProb[kmer][name] = prob;
 329                         }
 330
 331                         gobble(in);
 332                 }
 333                 in.close();
 334         }
 335         catch(exception& e) {
 336                 m->errorOut(e, "Bayesian", "readProbFile");
 337                 exit(1);
 338         }
 339 }
 340 /**************************************************************************************************/
 341
 342
 343
 344
 345
 346