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 (CSP for short) asks for a string t_(sot) 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~3 ?6.731~d) time, while the previous best runs in O(nL + nd ? 8~d) time. We then extend the algorithm to arbitrary alphabet sizes, obtaining an algorithm that runs in time O(nL + nd ·(1.612(|Σ| + β~2 + β-2))~d), where |Σ| is the alphabet size and β = α~2 + 1-2α~(-1) + α~(-2) with α=(|Σ|-1+1)/(α+3)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).