Improved algorithms for approximate string matching (extended abstract).

ABSTRACT:

Background

The problem of approximate string matching is important in many different areas such as computational biology, text processing and pattern recognition. A great effort has been made to design efficient algorithms addressing several variants of the problem, including comparison of two strings, approximate pattern identification in a string or calculation of the longest common subsequence that two strings share.

Results

We designed an output sensitive algorithm solving the edit distance problem between two strings of lengths n and m respectively in time O((s - |n - m|).min(m, n, s) + m + n) and linear space, where s is the edit distance between the two strings. This worst-case time bound sets the quadratic factor of the algorithm independent of the longest string len

SUBMITTER: Papamichail D 

PROVIDER: S-EPMC2648743 | biostudies-literature | 2009 Jan

REPOSITORIES: biostudies-literature