DNA alignment using a hierarchical inverted index table

A non-transitory computer-readable memory medium comprising program instructions, wherein the program instructions are executable by at least one processor to:

• a) store a hierarchical index table in the non-transitory computer-readable memory media, wherein the hierarchical index table is based on reference data,
• wherein the hierarchical index table comprises a plurality of entries at each of a plurality of levels, wherein the plurality of levels comprises a first level, wherein the hierarchical index table comprises a respective first level entry for each of a plurality of subsequences of the reference data having a first length,
• wherein for n={1, . . . , i}, the hierarchical index table further comprises n+1 level entries for respective level n entries in the hierarchical index table when matching criteria of the respective level n entry to the reference data exceeds a threshold, wherein the hierarchical index table comprises an n+1 level entry for each of a plurality of subsequences of the reference data having a length corresponding to the n+1 level;
• b) receive input specifying a search sequence;
• and
• c) search, by the at least one processor, the hierarchical index table for one or more matches of the search sequence to the reference data, wherein said searching the hierarchical index table comprises iteratively searching for matches of subsections of the respective search sequence to subsequences in subsequent levels of the hierarchical index table.

A method, comprising:

• a) storing a hierarchical index table in a non-transitory computer-readable memory media, wherein the hierarchical index table is based on reference data,
• wherein the hierarchical index table comprises a plurality of entries at each of a plurality of levels, wherein the plurality of levels comprises a first level, wherein the hierarchical index table comprises a respective first level entry for each of a plurality of subsequences of the reference data having a first length,
• wherein for n={1, . . . , i}, the hierarchical index table further comprises n+1 level entries for respective level n entries in the hierarchical index table when matching criteria of the respective level n entry to the reference data exceeds a threshold, wherein the hierarchical index table comprises an n+1 level entry for each of a plurality of subsequences of the reference data having a length corresponding to the n+1 level;
• b) receiving input specifying a search sequence;
• and
• c) searching the hierarchical index table for one or more matches of the search sequence to the reference data, wherein said searching the hierarchical index table comprises iteratively searching for matches of subsections of the respective search sequence to subsequences in subsequent levels of the hierarchical index table.