Finding a best matching string among a set of strings

摘要

A method for finding a best matching string among a set of strings for a reference string includes 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, and calculating a current optimal alignment boundary threshold. The method also includes executing, for each string of the set of strings, a calculation of 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, the method includes calculating a final alignment score for the string of the set of strings associated with the cell. Otherwise, the method includes aborting the calculation of a candidate alignment covering the string associated with the cell.