The Closest Substring problem with small distances∗

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. The problem is moti-vated by applications in computational biology. We present two algorithms that can be efficient for small fixed values of d and k: for some functions f and g, the algorithms have running time f (d) ·nO(logd) and g(d,k) ·nO(loglogk), respec-tively. The second algorithm is based on connections with the extremal combinatorics of hypergraphs. The CLOSEST SUBSTRING problem is also investigated from the parame-terized complexity point of view. Answering an open ques-tion from [6, 7, 11, 12], 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 run-ning time cannot be improved to o(logd) or to o(log logk) (modulo some complexity-theoretic assumptions). Another consequence is that the running time nO(1/ε4) of the approxi-mation scheme for CLOSEST SUBSTRING presented in [13] cannot be improved to f (ε) ·nc, i.e., the ε has to appear in the exponent of n.