preclustercommand.h

   1 #ifndef PRECLUSTERCOMMAND_H
   2 #define PRECLUSTERCOMMAND_H
   3
   4
   5 /*
   6  *  preclustercommand.h
   7  *  Mothur
   8  *
   9  *  Created by westcott on 12/21/09.
  10  *  Copyright 2009 Schloss Lab. All rights reserved.
  11  *
  12  */
  13
  14
  15 #include "command.hpp"
  16 #include "sequence.hpp"
  17 #include "sequenceparser.h"
  18 #include "sequencecountparser.h"
  19
  20 /************************************************************/
  21 struct seqPNode {
  22         int numIdentical;
  23         Sequence seq;
  24         string names;
  25         bool active;
  26         int diffs;
  27         seqPNode() {}
  28         seqPNode(int n, Sequence s, string nm) : numIdentical(n), seq(s), names(nm), active(1) { diffs = 0; }
  29         ~seqPNode() {}
  30 };
  31 /************************************************************/
  32 inline bool comparePriorityTopDown(seqPNode first, seqPNode second) {
  33     if (first.numIdentical > second.numIdentical) { return true;  }
  34     else if (first.numIdentical == second.numIdentical) {
  35         if (first.seq.getName() > second.seq.getName()) { return true; }
  36     }
  37     return false;
  38 }
  39 /************************************************************/
  40 inline bool comparePriorityDownTop(seqPNode first, seqPNode second) {
  41     if (first.numIdentical < second.numIdentical) { return true;  }
  42     else if (first.numIdentical == second.numIdentical) {
  43         if (first.seq.getName() > second.seq.getName()) { return true; }
  44     }
  45     return false;
  46 }
  47 //************************************************************/
  48
  49 class PreClusterCommand : public Command {
  50
  51 public:
  52         PreClusterCommand(string);
  53         PreClusterCommand();
  54         ~PreClusterCommand(){}
  55
  56         vector<string> setParameters();
  57         string getCommandName()                 { return "pre.cluster";                         }
  58         string getCommandCategory()             { return "Sequence Processing";         }
  59
  60         string getHelpString();
  61     string getOutputPattern(string);
  62         string getCitation() { return "Schloss PD, Gevers D, Westcott SL (2011).  Reducing the effects of PCR amplification and sequencing artifacts on 16S rRNA-based studies.  PLoS ONE.  6:e27310.\nhttp://www.mothur.org/wiki/Pre.cluster"; }
  63         string getDescription()         { return "implements a pseudo-single linkage algorithm with the goal of removing sequences that are likely due to pyrosequencing errors"; }
  64
  65
  66         int execute();
  67         void help() { m->mothurOut(getHelpString()); }
  68
  69 private:
  70
  71         struct linePair {
  72                 int start;
  73                 int end;
  74                 linePair(int i, int j) : start(i), end(j) {}
  75         };
  76
  77     SequenceParser* parser;
  78     SequenceCountParser* cparser;
  79     CountTable ct;
  80
  81         int diffs, length, processors;
  82         bool abort, bygroup, topdown;
  83         string fastafile, namefile, outputDir, groupfile, countfile;
  84         vector<seqPNode> alignSeqs; //maps the number of identical seqs to a sequence
  85         map<string, string> names; //represents the names file first column maps to second column
  86         map<string, int> sizes;  //this map a seq name to the number of identical seqs in the names file
  87         map<string, int>::iterator itSize;
  88 //      map<string, bool> active; //maps sequence name to whether it has already been merged or not.
  89         vector<string> outputNames;
  90
  91         int readFASTA();
  92         void readNameFile();
  93         //int readNamesFASTA();
  94         int calcMisMatches(string, string);
  95         void printData(string, string, string); //fasta filename, names file name
  96         int process(string);
  97         int loadSeqs(map<string, string>&, vector<Sequence>&, string);
  98         int driverGroups(string, string, string, int, int, vector<string> groups);
  99         int createProcessesGroups(string, string, string, vector<string>);
 100     int mergeGroupCounts(string, string, string);
 101 };
 102
 103 /**************************************************************************************************/
 104 //custom data structure for threads to use.
 105 // This is passed by void pointer so it can be any data type
 106 // that can be passed using a single void pointer (LPVOID).
 107 struct preClusterData {
 108         string fastafile;
 109         string namefile;
 110         string groupfile, countfile;
 111         string newFName, newNName, newMName;
 112         MothurOut* m;
 113         int start;
 114         int end, count;
 115         int diffs, threadID;
 116         vector<string> groups;
 117         vector<string> mapFileNames;
 118     bool topdown;
 119
 120         preClusterData(){}
 121         preClusterData(string f, string n, string g, string c, string nff,  string nnf, string nmf, vector<string> gr, MothurOut* mout, int st, int en, int d, bool td, int tid) {
 122                 fastafile = f;
 123                 namefile = n;
 124                 groupfile = g;
 125                 newFName = nff;
 126                 newNName = nnf;
 127                 newMName = nmf;
 128                 m = mout;
 129                 start = st;
 130                 end = en;
 131                 diffs = d;
 132                 threadID = tid;
 133                 groups = gr;
 134         countfile = c;
 135         topdown = td;
 136         count=0;
 137         }
 138 };
 139
 140 /**************************************************************************************************/
 141 #if defined (__APPLE__) || (__MACH__) || (linux) || (__linux) || (__linux__) || (__unix__) || (__unix)
 142 #else
 143 static DWORD WINAPI MyPreclusterThreadFunction(LPVOID lpParam){
 144         preClusterData* pDataArray;
 145         pDataArray = (preClusterData*)lpParam;
 146
 147         try {
 148
 149                 //parse fasta and name file by group
 150                 SequenceParser* parser;
 151         SequenceCountParser* cparser;
 152         if (pDataArray->countfile != "") {
 153             cparser = new SequenceCountParser(pDataArray->countfile, pDataArray->fastafile);
 154         }else {
 155             if (pDataArray->namefile != "") { parser = new SequenceParser(pDataArray->groupfile, pDataArray->fastafile, pDataArray->namefile);  }
 156             else                                { parser = new SequenceParser(pDataArray->groupfile, pDataArray->fastafile);                    }
 157         }
 158
 159                 int numSeqs = 0;
 160                 vector<seqPNode> alignSeqs;
 161                 //clear out old files
 162                 ofstream outF; pDataArray->m->openOutputFile(pDataArray->newFName, outF); outF.close();
 163                 ofstream outN; pDataArray->m->openOutputFile(pDataArray->newNName, outN);  outN.close();
 164
 165                 //precluster each group
 166                 for (int k = pDataArray->start; k < pDataArray->end; k++) {
 167
 168             pDataArray->count++;
 169
 170                         int start = time(NULL);
 171
 172                         if (pDataArray->m->control_pressed) {  delete parser; return 0; }
 173
 174                         pDataArray->m->mothurOutEndLine(); pDataArray->m->mothurOut("Processing group " + pDataArray->groups[k] + ":"); pDataArray->m->mothurOutEndLine();
 175
 176                         map<string, string> thisNameMap;
 177             vector<Sequence> thisSeqs;
 178                         if (pDataArray->groupfile != "") {
 179                 thisSeqs = parser->getSeqs(pDataArray->groups[k]);
 180             }else if (pDataArray->countfile != "") {
 181                 thisSeqs = cparser->getSeqs(pDataArray->groups[k]);
 182             }
 183                         if (pDataArray->namefile != "") {  thisNameMap = parser->getNameMap(pDataArray->groups[k]); }
 184
 185                         //fill alignSeqs with this groups info.
 186                         ////////////////////////////////////////////////////
 187                         //numSeqs = loadSeqs(thisNameMap, thisSeqs); same function below
 188
 189                         int length = 0;
 190                         alignSeqs.clear();
 191                         map<string, string>::iterator it;
 192                         bool error = false;
 193             map<string, int> thisCount;
 194             if (pDataArray->countfile != "") { thisCount = cparser->getCountTable(pDataArray->groups[k]);  }
 195
 196
 197                         for (int i = 0; i < thisSeqs.size(); i++) {
 198
 199                                 if (pDataArray->m->control_pressed) { delete parser; return 0; }
 200
 201                                 if (pDataArray->namefile != "") {
 202                                         it = thisNameMap.find(thisSeqs[i].getName());
 203
 204                                         //should never be true since parser checks for this
 205                                         if (it == thisNameMap.end()) { pDataArray->m->mothurOut(thisSeqs[i].getName() + " is not in your names file, please correct."); pDataArray->m->mothurOutEndLine(); error = true; }
 206                                         else{
 207                                                 //get number of reps
 208                                                 int numReps = 1;
 209                                                 for(int j=0;j<(it->second).length();j++){
 210                                                         if((it->second)[j] == ','){     numReps++;      }
 211                                                 }
 212
 213                                                 seqPNode tempNode(numReps, thisSeqs[i], it->second);
 214                                                 alignSeqs.push_back(tempNode);
 215                                                 if (thisSeqs[i].getAligned().length() > length) {  length = thisSeqs[i].getAligned().length();  }
 216                                         }
 217                                 }else { //no names file, you are identical to yourself
 218                                         int numRep = 1;
 219                     if (pDataArray->countfile != "") {
 220                         map<string, int>::iterator it2 = thisCount.find(thisSeqs[i].getName());
 221
 222                         //should never be true since parser checks for this
 223                         if (it2 == thisCount.end()) { pDataArray->m->mothurOut(thisSeqs[i].getName() + " is not in your count file, please correct."); pDataArray->m->mothurOutEndLine(); error = true; }
 224                         else { numRep = it2->second;  }
 225                     }
 226                     seqPNode tempNode(numRep, thisSeqs[i], thisSeqs[i].getName());
 227                     alignSeqs.push_back(tempNode);
 228                                         if (thisSeqs[i].getAligned().length() > length) {  length = thisSeqs[i].getAligned().length();  }
 229                                 }
 230                         }
 231
 232                         //sanity check
 233                         if (error) { pDataArray->m->control_pressed = true; }
 234
 235                         thisSeqs.clear();
 236                         numSeqs = alignSeqs.size();
 237
 238                         ////////////////////////////////////////////////////
 239
 240                         if (pDataArray->m->control_pressed) {   delete parser; return 0; }
 241
 242                         if (pDataArray->diffs > length) { pDataArray->m->mothurOut("Error: diffs is greater than your sequence length."); pDataArray->m->mothurOutEndLine(); pDataArray->m->control_pressed = true; return 0;  }
 243
 244                         ////////////////////////////////////////////////////
 245                         //int count = process(); - same function below
 246
 247                         ofstream out;
 248                         pDataArray->m->openOutputFile(pDataArray->newMName+pDataArray->groups[k]+".map", out);
 249                         pDataArray->mapFileNames.push_back(pDataArray->newMName+pDataArray->groups[k]+".map");
 250
 251             //sort seqs by number of identical seqs
 252             if (pDataArray->topdown) { sort(alignSeqs.begin(), alignSeqs.end(), comparePriorityTopDown);  }
 253             else {  sort(alignSeqs.begin(), alignSeqs.end(), comparePriorityDownTop);  }
 254
 255                         int count = 0;
 256
 257             if (pDataArray->topdown) {
 258                 //think about running through twice...
 259                 for (int i = 0; i < numSeqs; i++) {
 260
 261                     //are you active
 262                     //                  itActive = active.find(alignSeqs[i].seq.getName());
 263
 264                     if (alignSeqs[i].active) {  //this sequence has not been merged yet
 265
 266                         string chunk = alignSeqs[i].seq.getName() + "\t" + toString(alignSeqs[i].numIdentical) + "\t" + toString(0) + "\t" + alignSeqs[i].seq.getAligned() + "\n";
 267
 268                         //try to merge it with all smaller seqs
 269                         for (int j = i+1; j < numSeqs; j++) {
 270
 271                             if (pDataArray->m->control_pressed) { delete parser; return 0; }
 272
 273                             if (alignSeqs[j].active) {  //this sequence has not been merged yet
 274                                 //are you within "diff" bases
 275                                 //int mismatch = calcMisMatches(alignSeqs[i].seq.getAligned(), alignSeqs[j].seq.getAligned());
 276                                 int mismatch = 0;
 277
 278                                 for (int k = 0; k < alignSeqs[i].seq.getAligned().length(); k++) {
 279                                     //do they match
 280                                     if (alignSeqs[i].seq.getAligned()[k] != alignSeqs[j].seq.getAligned()[k]) { mismatch++; }
 281                                     if (mismatch > pDataArray->diffs) { mismatch = length; break; } //to far to cluster
 282                                 }
 283
 284                                 if (mismatch <= pDataArray->diffs) {
 285                                     //merge
 286                                     alignSeqs[i].names += ',' + alignSeqs[j].names;
 287                                     alignSeqs[i].numIdentical += alignSeqs[j].numIdentical;
 288
 289                                     alignSeqs[j].active = 0;
 290                                     alignSeqs[j].numIdentical = 0;
 291                                     alignSeqs[j].diffs = mismatch;
 292                                     count++;
 293                                     chunk += alignSeqs[j].seq.getName() + "\t" + toString(alignSeqs[j].numIdentical) + "\t" + toString(mismatch) + "\t" + alignSeqs[j].seq.getAligned() + "\n";
 294                                 }
 295                             }//end if j active
 296                         }//end for loop j
 297
 298                         //remove from active list
 299                         alignSeqs[i].active = 0;
 300
 301                         out << "ideal_seq_" << (i+1) << '\t' << alignSeqs[i].numIdentical << endl << chunk << endl;
 302
 303                     }//end if active i
 304                     if(i % 100 == 0)    { pDataArray->m->mothurOutJustToScreen(toString(i) + "\t" + toString(numSeqs - count) + "\t" + toString(count)+"\n");   }
 305                 }
 306
 307             }else {
 308                 map<int, string> mapFile;
 309                 map<int, int> originalCount;
 310                 map<int, int>::iterator itCount;
 311                 for (int i = 0; i < numSeqs; i++) { mapFile[i] = ""; originalCount[i] = alignSeqs[i].numIdentical; }
 312
 313                 //think about running through twice...
 314                 for (int i = 0; i < numSeqs; i++) {
 315
 316                     //try to merge it into larger seqs
 317                     for (int j = i+1; j < numSeqs; j++) {
 318
 319                         if (pDataArray->m->control_pressed) { out.close(); return 0; }
 320
 321                         if (originalCount[j] > originalCount[i]) {  //this sequence is more abundant than I am
 322                             //are you within "diff" bases
 323                             //int mismatch = calcMisMatches(alignSeqs[i].seq.getAligned(), alignSeqs[j].seq.getAligned());
 324                             int mismatch = 0;
 325
 326                             for (int k = 0; k < alignSeqs[i].seq.getAligned().length(); k++) {
 327                                 //do they match
 328                                 if (alignSeqs[i].seq.getAligned()[k] != alignSeqs[j].seq.getAligned()[k]) { mismatch++; }
 329                                 if (mismatch > pDataArray->diffs) { mismatch = length; break; } //to far to cluster
 330                             }
 331
 332                             if (mismatch <= pDataArray->diffs) {
 333                                 //merge
 334                                 alignSeqs[j].names += ',' + alignSeqs[i].names;
 335                                 alignSeqs[j].numIdentical += alignSeqs[i].numIdentical;
 336
 337                                 mapFile[j] = alignSeqs[i].seq.getName() + "\t" + toString(alignSeqs[i].numIdentical) + "\t" + toString(mismatch) + "\t" + alignSeqs[i].seq.getAligned() + "\n" + mapFile[i];
 338                                 alignSeqs[i].numIdentical = 0;
 339                                 originalCount.erase(i);
 340                                 mapFile[i] = "";
 341                                 count++;
 342                                 j+=numSeqs; //exit search, we merged this one in.
 343                             }
 344                         }//end abundance check
 345                     }//end for loop j
 346
 347                     if(i % 100 == 0)    { pDataArray->m->mothurOutJustToScreen(toString(i) + "\t" + toString(numSeqs - count) + "\t" + toString(count)+"\n");   }
 348                 }
 349
 350                 for (int i = 0; i < numSeqs; i++) {
 351                     if (alignSeqs[i].numIdentical != 0) {
 352                         out << "ideal_seq_" << (i+1) << '\t' << alignSeqs[i].numIdentical << endl  << alignSeqs[i].seq.getName() + "\t" + toString(alignSeqs[i].numIdentical) + "\t" + toString(0) + "\t" + alignSeqs[i].seq.getAligned() + "\n" << mapFile[i] << endl;
 353                     }
 354                 }
 355
 356             }
 357             out.close();
 358             if(numSeqs % 100 != 0)      { pDataArray->m->mothurOut(toString(numSeqs) + "\t" + toString(numSeqs - count) + "\t" + toString(count)); pDataArray->m->mothurOutEndLine();   }
 359                         ////////////////////////////////////////////////////
 360
 361                         if (pDataArray->m->control_pressed) {  delete parser; return 0; }
 362
 363                         pDataArray->m->mothurOut("Total number of sequences before pre.cluster was " + toString(alignSeqs.size()) + ".");pDataArray-> m->mothurOutEndLine();
 364                         pDataArray->m->mothurOut("pre.cluster removed " + toString(count) + " sequences."); pDataArray->m->mothurOutEndLine(); pDataArray->m->mothurOutEndLine();
 365
 366                         ////////////////////////////////////////////////////
 367                         //printData(pDataArray->newFFile, pDataArray->newNFile); - same as below
 368                         ofstream outFasta;
 369                         ofstream outNames;
 370
 371                         pDataArray->m->openOutputFileAppend(pDataArray->newFName, outFasta);
 372                         pDataArray->m->openOutputFileAppend(pDataArray->newNName, outNames);
 373
 374                         for (int i = 0; i < alignSeqs.size(); i++) {
 375                                 if (alignSeqs[i].numIdentical != 0) {
 376                                         alignSeqs[i].seq.printSequence(outFasta);
 377                                         if (pDataArray->countfile != "") {  outNames << pDataArray->groups[k] << '\t' << alignSeqs[i].seq.getName() << '\t' << alignSeqs[i].names << endl;
 378                     }else {  outNames << alignSeqs[i].seq.getName() << '\t' << alignSeqs[i].names << endl;  }
 379
 380                                 }
 381                         }
 382
 383                         outFasta.close();
 384                         outNames.close();
 385                         ////////////////////////////////////////////////////
 386
 387                         pDataArray->m->mothurOut("It took " + toString(time(NULL) - start) + " secs to cluster " + toString(numSeqs) + " sequences."); pDataArray->m->mothurOutEndLine();
 388
 389                 }
 390
 391                 return numSeqs;
 392
 393
 394         }
 395         catch(exception& e) {
 396                 pDataArray->m->errorOut(e, "PreClusterCommand", "MyPreclusterThreadFunction");
 397                 exit(1);
 398         }
 399 }
 400 #endif
 401
 402 /**************************************************************************************************/
 403
 404
 405 #endif
 406
 407