Finding Consensus Strings with Small Length Difference between Input and Solution Strings

摘要

The Closest Substring Problem is to decide, for given strings s_1,..., s_k of length at most ℓ and numbers m and d, whether there is a length-m string s and length-m substrings s_i~' of s_i, such that s has a Hamming distance of at most d from each s_i~' If we instead require the sum of all the Hamming distances between s and each s_i~' to be bounded by d, then it is called the Consensus Patterns Problem. We contribute to the parameterised complexity analysis of these classical NP-hard string problems by investigating the parameter (ℓ - m), i.e., the length difference between input and solution strings. For most combinations of (ℓ - m) and one of the classical parameters (m, ℓ, k, or d), we obtain fixed-parameter tractability. However, even for constant (ℓ - m) and constant alphabet size, both problems remain NP-hard. While this follows from known results with respect to the Closest Substring, we need a new reduction in the case of the Consensus Patterns. As a by-product of this reduction, we obtain an exact exponential-time algorithm for both problems, which is based on an alphabet reduction.