Finding a best matching string among a set of strings

1. A computer-implemented method for finding a best matching string among a set of strings for a reference string, the method comprising:

representing, for each of the set of strings paired with the reference string, a dynamic programming problem for calculating a final alignment score as a matrix of cells, each cell representing an intermediate result to be calculated;

calculating a current optimal alignment boundary threshold,

for each string of the set of strings, executing:

calculating a prospective final alignment score of a candidate alignment of the each of the set of strings and the reference string for each cell;

based on determining, that prospective final alignment score improves the current optimal alignment boundary threshold, calculating a final alignment score for the string of the set of strings associated with the cell; and

based on determining, that prospective final alignment score does not improve the current optimal alignment boundary threshold, aborting the calculation of a candidate alignment covering the string of the set of strings associated with the cell, wherein the optimum alignment score value for each of the cells is calculated as MATCHES * BEST_MATCH+GAPPENALTY(gaps),

wherein MATCHES =min(M−(j+1), N−(i+1)), wherein the MATCHES parameter value is the maximum possible number of matching character pairs in the sub-alignment, BEST_MATCH is the highest score obtainable for any aligned character pair for maximizing functions or the smallest obtainable score for minimizing functions, gaps is a minimum possible number of gaps occurring in the sub-alignment; and GAPPENALTY(gaps) is a monotone function which for a given number of gaps that is greater than zero that returns a penalty cost, the penalty cost being a negative value for maximizing functions and being a positive value for minimizing functions.

2. The computer-implemented method of claim 1 , further comprising:

sorting all strings of the set of strings according to a difference in length with respect to a length of the reference string,

wherein the calculation of the final alignment score is executed for all strings of the set of strings in the order of a growing length difference.

3. The computer-implemented method of claim 1 , wherein initially calculating the current optimal alignment boundary threshold comprises:

determining an integer K;

selecting a string from the set of strings, and for the selected string, executing:

determining a sub-set of cells of the matrix, said sub-set comprising all cells of the matrix having a row index i and a column index j fulfilling the equation |i−j|≦K; and

calculating an approximate final alignment score for the selected string by applying the dynamic programming problem on the matrix until the cell having an index of (N−1, M−1) is reached, thereby selectively taking as input to the dynamic programming problem only the intermediate results of those cells of the matrix which belong to the sub-set of cells; and

using the calculated approximate final alignment score as the current optimal alignment boundary threshold.

4. The computer-implemented method of claim 1 , further comprising:

sorting all strings of according to their difference in length with in respect to the length of the reference string; and

using one of the one or more strings having the smallest length difference as the selected string for calculating the initial optimal alignment boundary threshold.

5. The computer-implemented method of claim 1 , wherein initially calculating the current optimal alignment boundary threshold comprises initializing the optimal alignment boundary threshold as negative infinity for a maximizing optimization function and as positive infinity for a minimizing optimizing function.

6. The computer-implemented method of claim 1 , wherein the calculation of the final alignment score of each of the set of strings comprises:

dividing the cells of the matrix into groups of cells, at least some of the cell groups respectively taking intermediate results of cells of one or more other cell groups as input;

upon having calculated intermediate results for all cells of any one of the cell groups, marking these cells of said cell group as useless, for which the prospective final alignment score does not improve the current optimal alignment boundary threshold;

upon starting the calculation of any one of the cell groups, checking if all cells providing input to said one cell group are marked as useless cells; and

aborting the calculation of any one of the cell groups in case the checking returned as result that all the cells providing input to said cell group are marked as useless and marking at least those cells in the cell group aborting its execution as useless, which are operable to provide input to another cell group.

7. A computer program product for finding a best matching string among a set of strings for a reference string, the computer program product comprising:

a computer readable storage medium having computer readable program code embodied therewith, the computer readable program code configured to execute a method comprising:

representing, for each of the set of strings paired with the reference string, a dynamic programming problem for calculating a final alignment score as a matrix of cells, each cell representing an intermediate result to be calculated;

calculating a current optimal alignment boundary threshold,

for each string of the set of strings, executing:

calculating a prospective final alignment score of a candidate alignment of the each of the set of strings and the reference string for each cell;

based on determining, that prospective final alignment score improves the current optimal alignment boundary threshold, calculating a final alignment score for the string of the set of strings associated with the cell; and

based on determining, that prospective final alignment score does not improve the current optimal alignment boundary threshold, aborting the calculation of a candidate alignment covering the string of the set of strings associated with the cell, wherein the optimum alignment score value for each of the cells is calculated as MATCHES * BEST_MATCH +GAPPENALTY(gaps),

wherein MATCHES =min(M-(j+1), N-(i+1)), wherein the MATCHES parameter value is the maximum possible number of matching character pairs in the sub-alignment, BEST_MATCH is the highest score obtainable for any aligned character pair for maximizing functions or the smallest obtainable score for minimizing functions, gaps is a minimum possible number of gaps occurring in the sub-alignment and GAPPENALTY(gaps) is a monotone function which for a given number of gaps that is greater than zero that returns a penalty cost, the penalty cost being a negative value for maximizing functions and being a positive value for minimizing functions.

8. The computer program product of claim 7 , further comprising:

sorting all strings of the set of strings according to a difference in length with respect to a length of the reference string,

wherein the calculation of the final alignment score is executed for all strings of the set of strings in the order of a growing length difference.

9. The computer program product of claim 7 , wherein initially calculating the current optimal alignment boundary threshold comprises:

determining an integer K;

selecting a string from the set of strings, and for the selected string, executing:

determining a sub-set of cells of the matrix, said sub-set comprising all cells of the matrix having a row index i and a column index j fulfilling the equation |i−j|≦K; and

calculating an approximate final alignment score for the selected string by applying the dynamic programming problem on the matrix until the cell having an index of (N−1, M−1) is reached, thereby selectively taking as input to the dynamic programming problem only the intermediate results of those cells of the matrix which belong to the sub-set of cells; and

using the calculated approximate final alignment score as the current optimal alignment boundary threshold.

10. The computer program product of claim 7 , further comprising:

sorting all strings of according to their difference in length with in respect to the length of the reference string; and

using one of the one or more strings having the smallest length difference as the selected string for calculating the initial optimal alignment boundary threshold.

11. The computer program product of claim 7 , wherein initially calculating the current optimal alignment boundary threshold comprises initializing the optimal alignment boundary threshold as negative infinity for a maximizing optimization function and as positive infinity for a minimizing optimizing function.

12. The computer program product of claim 7 , wherein the calculation of the final alignment score of each of the set of strings comprises:

dividing the cells of the matrix into groups of cells, at least some of the cell groups respectively taking intermediate results of cells of one or more other cell groups as input;

upon having calculated intermediate results for all cells of any one of the cell groups, marking these cells of said cell group as useless, for which the prospective final alignment score does not improve the current optimal alignment boundary threshold;

upon starting the calculation of any one of the cell groups, checking if all cells providing input to said one cell group are marked as useless cells; and

aborting the calculation of any one of the cell groups in case the checking returned as result that all the cells providing input to said cell group are marked as useless and marking at least those cells in the cell group aborting its execution as useless, which are operable to provide input to another cell group.