Various technologies described herein pertain to parallel local sequence alignment that aligns a query sequence with a database sequence. The database sequence is segmented into a plurality of stripes. A first processing unit can compute Smith-Waterman values for a first stripe of the database sequence across the query sequence based on a cost function that models biological similarity between sequences. Moreover, a second processing unit can compute Smith-Waterman values for a second stripe of the database sequence across the query sequence based on the cost function. Further, a subset of the Smith-Waterman values for the second stripe of the database sequence across the query sequence can be re-computed based on the cost function (e.g., by the first processing unit or the second processing unit). The subset of the Smith-Waterman values to be re-computed can be determined based on a query sequence length and the cost function.