A Three-String Approach to the Closest String Problem

摘要

Given a set of n strings of length L and a radius d, the closest string problem asks for a new string t_(sol) that is within a Hamming distance of d to each of the given strings. It is known that the problem is NP-hard and its optimization version admits a polynomial time approximation scheme (PTAS). Parameterized algorithms have been then developed to solve the problem when d is small. In this paper, with a new approach (called the 3-string approach), we first design a parameterized algorithm for binary strings that runs in O (nL + nd~36.731~d) time, while the previous best runs in O (nL + nd8~d) time. We then extend the algorithm to arbitrary alphabet sizes, obtaining an algorithm that runs in O (nL + ndl.612~d (α~2 + 1 - 2α~(-1) + α~(-2))~(3d)) time, where α = 3(1/2)|Σ|— 1 + 1. This new time bound is better than the previous best for small alphabets, including the very important case where ∑ = 4 (i.e., the case of DNA strings).