Patent Document ID: 20050114298
Application ID: 10723229
Patent Flag: 0

Claim One:
1. A method of generating an index for a sequence that supports a non-contiguous subsequence match, comprising: receiving a sequence; 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; inserting each of the one or more one-dimensional sequences into a trie structure; and generating the index, comprising: generating a current sequential ID and a maximum sequential ID pair for generating each of the one or more trie nodes, wherein the current sequential ID of any descendant of a given trie node 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 of each of the one or more subsequences in the weighted-sequence.