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