Reduced memory nucleotide sequence comparison

One or more computing devices comprising

• one or more processing units;
• and
• one or more computer-readable storage media comprising computer-executable instructions, which, when executed by the one or more processing units, cause the one or more computing devices to:
• generate, for individual cells of a two-dimensional matrix, scores that are based on generated scores of prior cells and pairs of nucleotides that correspond to the individual cells, wherein the pairs of nucleotides each comprise one nucleotide from each of a first nucleotide sequence and a second nucleotide sequence that are being compared to one another;
• generate backtrack metadata for the individual cells based at least in part on the generating of the scores;
• store, in a cache, backtrack metadata of cells of only a first subsection of the two-dimensional matrix;
• generate again backtrack metadata of cells of only a second subsection of the two-dimensional matrix, based on scores of cells of the two-dimensional matrix that comprise two edges of the second subsection, if a first cell, for which a first backtrack metadata is to be determined, is in the second subsection, the second subsection being mutually exclusive of the first subsection;
• obtain, from the regenerated backtrack metadata of the cells of only the second subsection, stored in the cache, the first backtrack metadata of the first cell of the two-dimensional matrix;
• and
• generate a textual string comprising indicators of similarities and differences of the first nucleotide sequence as compared with the second nucleotide sequence.

A method of comparing nucleotide sequences with one or more computing devices, the method comprising:

• generating, on the one or more computing devices, for individual cells of a two-dimensional matrix, scores that are based on generated scores of prior cells and pairs of nucleotides that correspond to the individual cells, wherein the pairs of nucleotides each comprise one nucleotide from each of a first nucleotide sequence and a second nucleotide sequence that are being compared to one another;
• generating, on the one or more computing devices, backtrack metadata for the individual cells based at least in part on the generating of the scores;
• storing, in a cache on at least one of the one or more computing devices, backtrack metadata of cells of only a first subsection of the two-dimensional matrix;
• generating again, on the one or more computing devices, backtrack metadata of cells of only a second subsection of the two-dimensional matrix, based on scores of cells of the two-dimensional matrix that comprise two edges of the second subsection, if a first cell, for which a first backtrack metadata is to be determined, is in the second subsection, the second subsection being mutually exclusive of the first subsection;
• obtaining, with the one or more computing devices, from the regenerated backtrack metadata of the cells of only the second subsection, stored in the cache, the first backtrack metadata of the first cell of the two-dimensional matrix;
• and
• generating, by the one or more computing devices, a textual string comprising indicators of similarities and differences of the first nucleotide sequence as compared with the second nucleotide sequence.