CLOSEST SUBSTRING PROBLEMS WITH SMALL DISTANCES∗

We study two pattern matching problems that are motivated by applications in computational biology. In the Closest Substring problem k strings s1,..., sk are given, and the task is to find a string s of length L such that each string si has a consecutive substring of length L whose distance is at most d from s. We present two algorithms that aim to be efficient for small fixed values of d and k: for some functions f and g, the algorithms have running time f(d) ·nO(log d) and g(d, k) ·nO(log log k), respectively. The second algorithm is based on connections with the extremal combinatorics of hy-pergraphs. The Closest Substring problem is also investigated from the parameterized complexity point of view. Answering an open question from [13, 14, 20, 21], we show that the problem is W[1]-hard even if both d and k are parameters. It follows as a consequence of this hardness result that our algorithms are optimal in the sense that the exponent of n in the running time cannot be improved to o(log d) or to o(log log k) (modulo some complexity-theoretic assumptions). Consensus Patterns is the variant of the problem where, instead of the requirement that each si has a substring that is of distance at most d from s, we have to select the substrings in such a way that the average of these k distances is at most δ. By giving an f(δ) · n9 time algorithm, we show that the problem is fixed-parameter tractable. This answers an open question from [14]