Patent Document ID: 9384239
Application ID: 13716231
Patent Status: 1

Claim One:
1. A method of aligning a query sequence with a database sequence, the query sequence comprises a string of symbols having a query sequence length, the database sequence comprises a string of symbols having a database sequence length, and the database sequence being segmented into at least a first stripe and a second stripe, the method comprising: computing, utilizing a first processing unit, Smith-Waterman values for cells in a first column-wise partition of a table based on a cost function that models similarity between sequences, the first column-wise partition corresponding to the first stripe of the database sequence across the query sequence, wherein Smith-Waterman values for cells in a second column-wise partition of the table are computed utilizing a second processing unit, the second column-wise partition corresponding to the second stripe of the database sequence across the query sequence; re-computing a subset of the Smith-Waterman values for the cells in the second column-wise partition of the table based on the cost function, the subset of the Smith-Waterman values being based on the query sequence length and the cost function; and producing an alignment between the symbols in the query sequence and the symbols in the database sequence based on Smith-Waterman values for cells of the table, the Smith-Waterman values for the cells of the table comprise at least the Smith-Waterman values for the cells in the first column-wise partition and the Smith-Waterman values for the cells in the second column-wise partition.