Devices and methods for locating a sample read in a reference genome

A method of locating a sample read with respect to a reference genome, the method comprising:

• storing, in a plurality of groups of cells of at least one two-dimensional systolic array, reference sequences representing reference bases from the reference genome, the reference sequences corresponding to an order of cells in respective groups of cells of the plurality of groups of cells, wherein each group of cells of the plurality of groups of cells stores a reference sequence representing a portion of the reference genome that partially overlaps at least one other portion of the reference genome represented by one or more other reference sequences stored in one or more other groups of cells;
• storing, in each group of cells of the plurality of groups of cells, a current substring sequence for sample bases from the sample read by passing the first substring sequence from one group of cells to a next group of cells in the at least one two-dimensional systolic array with the current substring sequence corresponding to the order of cells in the respective groups of cells;
• and
• identifying groups of cells in the at least one two-dimensional systolic array where the stored reference sequence matches the current substring sequence stored in the group of cells.

A method of operating a device comprising at least one two-dimensional systolic array including a plurality of groups of cells, the method comprising:

• storing, in each group of cells of the plurality of groups of cells, a first substring sequence for sample bases from a sample read by passing the first substring sequence from one group of cells to a next group of cells in the at least one two-dimensional systolic array such that the sample bases in the first substring sequence correspond to the order of cells in the respective groups of cells of the plurality of groups of cells;
• wherein each group of cells of the plurality of groups of cells is configured to store a reference sequence representing different portions of a reference genome;
• identifying groups of cells in the at least one two-dimensional systolic array where the stored reference sequence matches the first substring sequence stored in the group of cells;
• storing, in each group of cells of the plurality of groups of cells, a second substring sequence for sample bases from another portion of the sample read by passing the second substring sequence from one group of cells to a next group of cells in the at least one two-dimensional systolic array such that the sample bases for the second substring sequence correspond to the order of cells in the group of cells and overwrite the first substring sequence;
• and
• identifying groups of cells in the at least one two-dimensional systolic array where the stored reference sequence matches the second substring sequence stored in the group of cells.