/******************************************************************** * * Implementation of the adaptive algorithm for determining * strings from substrings. * Suffix tree version. * * Node *initial_suffix_tree(); * Leaf *add_a_string(Node *root, char *str, int id); * * Suffix tree-related functions. ********************************************************************/ #include "stree.h" #define _DEBUG #define ISEQUAL 0 #define SUPERSTR -1 int ch2int[128]; char int2ch[ALPHABET+1]; long numOfNodes; long numOfArcs; long numOfLeaves; long numOfStrings; long numOfChars; char *strPtr[NUMSTR]; int idMap[NUMSTR]; /* external functioon */ extern char *get_string(int id, int from, int length); /* internal function */ char *getmem(unsigned bytes); int mystrcmp(char *mystr, int len, char *arcstr, int len); Node *create_node(); Leaf *create_leaf(); Node *insert_a_suffix(Node *root, char *str, int len, int id, int suffix, Node**); /* outside function */ Node *initial_suffix_tree(); void add_a_string(Node *root, char *str, int id); void DFS(Node *root); /******************************************************************** * * Memory allocator. Exits program if not enough memory exists. * ********************************************************************/ char *getmem(unsigned bytes) { char *ptr; if ((ptr = (char *) malloc(bytes)) == (char *) NULL) { perror("getmem()"); fprintf(stderr, "Couldn't allocate %u byte(s).\n", bytes); exit(1); } return ptr; } /******************************************************************** * * Initialize suffix tree, create root and return root; * ********************************************************************/ Node *initial_suffix_tree() { Node *root; ch2int['A'] = 0; int2ch[0] = 'A'; ch2int['G'] = 1; int2ch[1] = 'G'; ch2int['C'] = 2; int2ch[2] = 'C'; ch2int['T'] = 3; int2ch[3] = 'T'; ch2int['N'] = 4; int2ch[4] = 'N'; numOfNodes = 0; numOfArcs = 0; numOfLeaves = 0; numOfStrings=0; numOfChars = 0; root = create_node(); return root; } /******************************************************************** * * DFS : Depth-first search * ********************************************************************/ void DFS(Node *subroot) { Node *mynode, *tempnode; Leaf *myleaf; int vtrace[1000]; /* the path from subroot */ Node *ntrace[1000]; /* the path from subroot */ int i, j, k; /* i as path level, j as arc index */ i=0; j=-1; vtrace[i]=j; ntrace[i]=subroot; while (i>=0) { j = vtrace[i] + 1; mynode = ntrace[i]; while (jchildren[j]==NULL) j++; if (j>=ALPHABET) i--; /* return to upper level */ else /* explore new level */ { vtrace[i++] = j; vtrace[i] = -1; ntrace[i] = mynode->children[j]; /* new node */ } } /* end of while () */ } /******************************************************************** * * Create the suffix tree for the string "sequence". * return first leaf (Leaf *) of the string. * ********************************************************************/ void add_a_string(Node *root, char *str, int id) { int i, k, j, mylen; char *mystr; Node *firstnode, *nextnode, *parent; mystr = str; mylen = strlen(mystr); idMap[numOfStrings] = id; strPtr[numOfStrings] = str; firstnode = insert_a_suffix(root, mystr, mylen, numOfStrings, 0, &parent); if (mylen>=MINLEN) for(i=1; mystr[i+MINLEN-1]!='\0'; i++) /* insert succsive suffix */ { if (firstnode->suff_link!=NULL) nextnode = insert_a_suffix(firstnode->suff_link, mystr, mylen, numOfStrings, i, &parent); else if (parent->suff_link!=NULL) nextnode = insert_a_suffix(parent->suff_link, mystr, mylen, numOfStrings, i, &parent); else nextnode = insert_a_suffix(root, mystr, mylen, numOfStrings, i, &parent); firstnode->suff_link = nextnode; firstnode = nextnode; } numOfStrings++; numOfChars += strlen(str); } /******************************************************************** * * Insert a string (with all suffixes) into the suffix tree. * return the leaf (Leaf*) * ********************************************************************/ Node* insert_a_suffix(Node *subroot, char *str, int len, int id, int suffix, Node **parent) { int i, j, k, l, mylen; Node *mynode, *mychild, *tempnode, *myparent; Leaf *myleaf; char *mystr, *arcstr; if (subroot->depth > (len-suffix)) { printf("\n Error in insert_a_suffix()"); exit(2); } mylen = len; mystr=str; mynode=subroot; *parent = subroot; for(i=suffix+subroot->depth; ;) { if (i==len) { myleaf = create_leaf(); /* add leaf */ myleaf->fragid = id; myleaf->suffix = suffix; myleaf->next_leaf = mynode->leaves; mynode->leaves = myleaf; return mynode; } k = ch2int[mystr[i]]; mychild = mynode->children[k]; if(mychild==NULL) /* add a new node and leaf node */ { mychild = create_node(); /* add node */ mychild->fragid = id; mychild->first = i; mychild->length = mylen-i; mychild->depth = mylen-suffix; mynode->children[k] = mychild; myleaf = create_leaf(); /* add leaf */ myleaf->fragid = id; myleaf->suffix = suffix; mychild->leaves = myleaf; *parent = mynode; return mychild; /* quit this procedure */ } else /* split or continue travesing */ { arcstr = strPtr[mychild->fragid]+mychild->first; j=mystrcmp(mystr+i, mylen-i, arcstr, mychild->length); switch(j) { case ISEQUAL: myleaf = create_leaf(); /* add a leaf */ myleaf->fragid = id; myleaf->suffix = suffix; myleaf->next_leaf = mychild->leaves; mychild->leaves = myleaf; *parent = mynode; return mychild; /* quit this procedure */ case SUPERSTR: i += mychild->length; /* skip */ *parent = mynode; mynode = mychild; break; default : tempnode = create_node(); /*common prefix*/ tempnode->fragid = mychild->fragid; tempnode->first = mychild->first; tempnode->length = j; tempnode->depth = mynode->depth + j; l = ch2int[arcstr[j]]; tempnode->children[l] = mychild; mynode->children[k] = tempnode; mychild->first += j; mychild->length -= j; i += j; *parent = mynode; mynode = tempnode; break; /* next round */ } /* end of switch */ } /* end of else */ } /* end of for() */ } /******************************************************************** * * Compare two string, return equal, super string or common prefix * ********************************************************************/ int mystrcmp(char *mystr, int mylen, char *arcstr, int arclen) { int i=0; while((mystr[i]==arcstr[i]) && (i suff_link = (Node *) NULL; newnode -> leaves = (Leaf *) NULL; for (i = 0; i < ALPHABET; i++) newnode->children[i] = (Node *) NULL; newnode -> fragid = 0; newnode -> first = 0; newnode -> length = 0; newnode -> depth = 0; numOfNodes++; return newnode; } /******************************************************************** * * Construct a new suffix-tree leaf. Return a pointer to it. * ********************************************************************/ Leaf *create_leaf() { Leaf *newleaf; newleaf = (Leaf *) getmem(sizeof(Leaf)); newleaf -> next_leaf = (Leaf *) NULL; newleaf -> fragid = 0; newleaf -> suffix = 0; numOfLeaves++; return newleaf; } /* end of stree.cc */ From tichen Tue Aug 6 16:08:05 1996 Received: from sbvassili.csdept (sbvassili.cs.sunysb.edu [130.245.15.4]) by cs.sunysb.edu (8.6.12/8.6.9) with SMTP id QAA20069 for ; Tue, 6 Aug 1996 16:08:04 -0400 Date: Tue, 6 Aug 1996 16:08:04 -0400 From: Ting Chen Message-Id: <199608062008.QAA20069@cs.sunysb.edu> To: skiena Subject: README Status: RO this program is using vectors for outedges of a suffix node. For DNA sequences, each node will have 5 out edges, representing nucleotides a c g t and n(unknown). This program is to build one suffix tree for multiple strings, which can be used for searching common substrings or patterns among different strings but requires extra memory for leaves because a leaf can be shared by several strings. Node *initial_suffix_tree() - Initializing suffix trees and return the root of the tree. Leaf *add_a_string(Node *root, char *str, int id) - Adding a string *str into Suffix Tree *root with string label id and return the pointer to the first leaf of $str. Usage : Node *root; Leaf *leaf; root = initial_suffix_tree(); leaf = add_a_string(root, str, 0);