suffixtree.hpp

   1 #ifndef SUFFIXTREE_H
   2 #define SUFFIXTREE_H
   3
   4 /*
   5  *  suffixtree.h
   6  *
   7  *
   8  *  Created by Pat Schloss on 12/15/08.
   9  *  Copyright 2008 Patrick D. Schloss. All rights reserved.
  10  *
  11  *      This is my half-assed attempt to implement a suffix tree.  This is a cobbled together algorithm using materials that
  12  *      I found at http://marknelson.us/1996/08/01/suffix-trees/ and:
  13  *
  14  *              Ukkonen E. (1995). On-line construction of suffix trees. Algorithmica 14 (3): 249--260
  15  *              Gusfield, Dan (1999). Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology.
  16  *                      USA: Cambridge University Press
  17  *
  18  *      The Ukkonen paper is the seminal paper describing the on-line method of constructing a suffix tree.
  19  *
  20  *      I have chosen to store the nodes of the tree as a vector of pointers to SuffixNode objects.  The root is stored at
  21  *      nodeVector[0].  Each tree also stores the sequence name and the string that corresponds to the actual sequence.
  22  *      Finally, this class provides a way of counting the number of suffixes that are needed in one tree to generate a new
  23  *      sequence (countSuffixes).  This method is used to determine similarity between sequences and was inspired by the
  24  *      article and Perl source code provided at http://www.ddj.com/web-development/184416093.
  25  *
  26  */
  27
  28 #include "mothur.h"
  29
  30 class SuffixNode;
  31
  32 //********************************************************************************************************************
  33
  34 class SuffixTree {
  35
  36 public:
  37         SuffixTree();
  38         ~SuffixTree();
  39
  40         void loadSequence(Sequence);
  41         string getSeqName();
  42         void print();
  43         int countSuffixes(string, int&);
  44         int countSuffixes(string);
  45
  46 private:
  47         void addPrefix(int);
  48         void canonize();
  49         int split(int, int);
  50         void makeSuffixLink(int&, int);
  51         bool isExplicit(){      return activeStartPosition > activeEndPosition; }
  52
  53         int activeStartPosition;
  54         int activeEndPosition;
  55
  56         vector<SuffixNode*> nodeVector;
  57         int root;
  58         int activeNode;
  59         int nodeCounter;
  60         string seqName;
  61         string sequence;
  62         MothurOut* m;
  63
  64 };
  65
  66 //********************************************************************************************************************
  67
  68 #endif