A Fast Algorithm for the Inexact Characteristic String Problem

We present a new algorithm to solve the Inexact Characteristic String Problem (ICSP) using Hamming distance instead of Levenshtein distance as a measure. We embed our new algorithm and the previously known algorithm for Levenshtein distance in a common framework which reveals an additional improvement to the Levenshtein distance algorithm. The ICSP can thus be solved in time O(||T||+l*||S-T||) for Hamming distance and in time O(||T|| + k*l*||S-T||) for Levenshtein distance, where S is a set of strings, T is a non-empty subset of S (the target set), and l is the length of a shortest string in T. The ICSP has applications in probe and primer design. Both algorithms need to solve the Common Substring Problem for more than two strings. We present an improved algorithm for this problem being simpler and faster in practice by a constant factor than the previous algorithm.     «

We present a new algorithm to solve the Inexact Characteristic String Problem (ICSP) using Hamming distance instead of Levenshtein distance as a measure. We embed our new algorithm and the previously known algorithm for Levenshtein distance in a common framework which reveals an additional improvement to the Levenshtein distance algorithm. The ICSP can thus be solved in time O(||T||+l*||S-T||) for Hamming distance and in time O(||T|| + k*l*||S-T||) for Levenshtein distance, where S is a set of s...     »