Patent ID: 7418455

Claim:
A method of generating an index for a sequence that supports a non-contiguous subsequence match, comprising: receiving a sequence comprising one or more pairs of symbol and weight elements, the symbol elements corresponding to a non-uniform frequency distribution; receiving a window size; encoding the sequence into a weighted-sequence; encoding the weighted sequence into one or more one-dimensional sequences, wherein the length of each of the one or more one-dimensional sequences is less than the window size; reordering the one or more one one-dimensional sequences using the non-uniform frequency distribution to generate a new sequence; inserting the new sequence as one or more trie nodes into a trie structure; and generating an index, wherein generating the index comprises: generating a current sequential ID and a maximum sequential ID pair for each of the one or more trie nodes, wherein the current sequential ID of any descendant of a given the node of the one or more trie nodes is between the current sequential ID of the given trie node and the maximum sequential ID; generating an iso-depth link for each unique symbol in each of the one or more one-dimensional sequences, wherein the iso-depth link comprises trie nodes under the symbol; and generating an offset list comprising an original position for each of one or more subsequences in the weighted-sequence.