Common approximate substrings
Andrew D. Smith · 2004
Discovering patterns in strings is a central task in analyzing molecular sequences. One pattern discovery problem is to find a pattern that occurs as a substring in each member of a given set of strings. Additionally, occurrences of this pattern are allowed to have up to some specified number of errors, so the occurrences may not exactly match the pattern. Allowing such “approximate occurrences ” significantly complicates methods for discovering the pattern, rendering it NP-hard. The pattern discovery problem is abstracted as a decision problem under the name Common Approximate Substring. A systematic parameterized complexity analysis is conducted, producing a nearly complete parameterized complexity map with respect to the number of input sequences, their maximum length, the length of the pattern, the maximum number of mismatches between the pattern and its occurrences, and the size of the sequence alphabet. The analysis has also revealed several new results, including the first FPT variant not parameterized with alphabet size. The