An approximate string matching algorithm with extension to higher dimensions
Kathleen M. Kaplan · 1996
Approximate string matching is needed to compare strings or sequences of characters in many applications, one being the comparison of deoxyribonucleic acid (DNA) data. Modifications to an approximate string matching algorithm, such as including multiple strings or higher dimensional data, increase its usefulness. The study describes an original algorithm to perform approximate string matching using DNA data. This algorithm, deemed the longest consecutive algorithm (LCA), is modified and used to include higher dimensional data (2-, 3-, and 4-D) weights, reverse subsequence matching, and the comparison of many data sets at one time (R sequences) with and without reverse subsequences. Performance measures, including time and space complexity, are provided, Also, a priori knowledge of data and the incorporation of parallelism and dynamic storage are investigated (resulting in an improvement in the algorithm's time complexity). The modifications are programmed and tested with DNA data or 2-D data. A second original algorithm to perform 2-D matching also is described. The algorithm, the largest contiguous set (LCS) algorithm, is modified and used to include inexact matching and weighted matching. The LCS is programmed and tested with 2-D data. This study shows that the most common approximate string matching method, dynamic programming (DP), does not incorporate many of the above-mentioned modifications, such as reverse subsequence matching and higher dimensional data sets. A comparison of DP and LCA using DNA data shows that the LCA is competitive both in theory and in practice.