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 using namespace std;
  31
  32 class SuffixNode;
  33
  34 //********************************************************************************************************************
  35
  36 class SuffixTree {
  37
  38 public:
  39         SuffixTree();
  40         ~SuffixTree();
  41 //      SuffixTree(string, string);
  42
  43         void loadSequence(Sequence*);
  44         string getSeqName();
  45         void print();
  46         int countSuffixes(string, int&);
  47
  48 private:
  49         void addPrefix(int);
  50         void canonize();
  51         int split(int, int);
  52         void makeSuffixLink(int&, int);
  53         bool isExplicit(){      return activeStartPosition > activeEndPosition; }
  54
  55         int activeStartPosition;
  56         int activeEndPosition;
  57
  58         vector<SuffixNode*> nodeVector;
  59         int root;
  60         int activeNode;
  61         int nodeCounter;
  62         string seqName;
  63         string sequence;
  64
  65 };
  66
  67 //********************************************************************************************************************
  68
  69 #endif