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