Patent ID: 7917302

Claim:
A computer-implemented method for measuring similarity between two polynucleotide sequences or two amino acid sequences, the two sequences represented as sequence A of M elements and sequence B of N elements to be used in a Smith-Waterman local alignment similarity score calculations, comprising calculating a score S based on an alignment matrix H of M times N elements by using a substitution score value matrix Z, an open penalty gap q and a gap extension penalty r, where the calculation of the alignment matrix H comprises the steps of a) using K elements located sequentially on the same row or column in the alignment matrix H, and b) providing vectors V with the K elements where the vectors V are represented as registers or processing elements in a microprocessor, thereby enabling parallel processing of K elements, and c) determining if the calculation of the value of any one of the said K elements in one of said vectors is dependent on the value of any of the different K−1 elements in said one vector or on a value in an element from a different vector, the determination comprising the steps of: (i) calculating initial score values for the K elements of the said vector by ignoring any effect that could have resulted from potential gaps in the sequence in the direction of the said vector; and (ii) determining if dependency is possible by checking whether the last element of the previous vector or any but the last of said initial values exceed a limit formed as the sum of the gap open penalty and gap extension penalty parameters, and d) computing the vector element values without taking potential gaps in the direction of the vector into account if no dependency is detected, or e) recursively computing the optimized values by taking potential gaps in the direction of the vector into account if dependency is detected, and f) using a maximum range of values in the storage element representing one of said K elements, comprising applying only non-negative values in the processing of said K elements by adding a bias if the starting value is negative, applying only unsigned arithmetic in the processing of said K elements, and subtracting the same bias later on, said bias being equal to the absolute value of the largest representation of negative value in the element storing said one of said K elements, and g) outputting the score S to a user, a display, a memory, or a computer in a network, and wherein every method step is performed by a suitably programmed computer.