We study the complexity of the problem of searching for a set of patterns that separate two given sets of strings. This problem has applications in a wide variety of areas, most notably in data mining, computational biology, and in understanding the complexity of genetic algorithms. We show that the basic problem of finding a small set of patterns that match one set of strings but do not match any string in a second set is difficult (NP-complete, W[2]-hard when parameterized by the size of the pattern set, and APX-hard). We then perform a detailed parameterized analysis of the problem, separating tractable and intractable variants. In particular we show that parameterizing by the size of pattern set and the number of strings, and the size of the alphabet and the number of strings give FPT results, amongst others.
@cite_5: The Closest String problem asks to find a string s which is not too far from each string in a set of m input strings, where the distance is taken as the Hamming distance. This well-studied problem has various applications in computational biology and drug design. In this paper, we introduce a new variant of Closest String where the input strings can contain wildcards that can match any letter in the alphabet, and the goal is to find a solution string without wildcards. We call this problem the Closest String with Wildcards problem, and we analyze it in the framework of parameterized complexity. Our study determines for each natural parameterization whether this parameterization yields a fixed-parameter algorithm, or whether such an algorithm is highly unlikely to exist.
Hermelin and Rozenberg introduce a further variant of the problem @cite_5 , the problem. The input is a set of strings @math , which may include wildcard characters, and an integer @math . The goal is to find a string with hamming distance at most @math to each @math . The solution is required to have no wildcard characters. The examine a number of parameters: the length @math of the input strings, the number @math of input strings, @math , the number @math of characters in the alphabet, and the minimum number @math of wildcard characters in any input string. They show that the problem is in (with varying explicit running times) when parameterized by @math , @math , @math and @math . They also show that the special case where @math can be solved in polynomial time, whereas the problem is -hard for every @math .