A method configured for execution by a first processing unit, the method comprising: obtaining a nucleotide or protein query sequence to align with a database sequence, wherein the query sequence comprises a string of symbols having a query sequence length, wherein the database sequence comprises a string of symbols having a database sequence length, and wherein the database sequence is segmented into at least a first stripe and a second stripe, each stripe including a string of symbols from the database sequence; computing, utilizing the first processing unit, Smith-Waterman values for cells in a first column-wise partition of a cost table based on a cost function that models biological similarity between sequences, the first column-wise partition corresponding to the first stripe of the database 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; and re-computing, utilizing the first processing unit, a subset of the Smith-Waterman values for the cells in the second column-wise partition of the table based on the cost function, wherein the subset of the Smith-Waterman values to be re-computed is determined based on the query sequence length and the cost function; determining overlaps between stripes that are further employed to re-compute Smith-Waterman values within overlap regions of the cost table; and wherein a lower bound on the re-computation is determined from:i ≤ (j * M max - Gs) / Ge for i from 1 to (Q* M max - G s)/ G e and for j from 1 to Q, where M max is an upper bound of entries in the cost matrix, G s is the gap start penalty, G e is the gap extend penalty and Q is a length of a query sequence. obtaining a nucleotide or protein query sequence to align with a database sequence, wherein the query sequence comprises a string of symbols having a query sequence length, wherein the database sequence comprises a string of symbols having a database sequence length, and wherein the database sequence is segmented into at least a first stripe and a second stripe, each stripe including a string of symbols from the database sequence; computing, utilizing the first processing unit, Smith-Waterman values for cells in a first column-wise partition of a cost table based on a cost function that models biological similarity between sequences, the first column-wise partition corresponding to the first stripe of the database 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; and re-computing, utilizing the first processing unit, a subset of the Smith-Waterman values for the cells in the second column-wise partition of the table based on the cost function, wherein the subset of the Smith-Waterman values to be re-computed is determined based on the query sequence length and the cost function; determining overlaps between stripes that are further employed to re-compute Smith-Waterman values within overlap regions of the cost table; and wherein a lower bound on the re-computation is determined from:i ≤ (j * M max - Gs) / Ge for i from 1 to (Q* M max - G s)/ G e and for j from 1 to Q, where M max is an upper bound of entries in the cost matrix, G s is the gap start penalty, G e is the gap extend penalty and Q is a length of a query sequence.