Closest string

In theoretical computer science, closest string is the name of an NP-hard computational problem,^[1] which tries to find the geometrical center of a set of input strings.

To understand the word "center" it is necessary to define a distance between two strings. Usually, this problem is studied with the Hamming distance in mind.

Formal definition

More formally, given n length-m strings s₁, s₂, ..., s_n, the closest string problem seeks for a new length-m string s such that d(s,s_i) ≤ k for all i, where d denotes the Hamming distance, and where k is as small as possible.^[2] A decision problem version of the closest string problem, which is NP-complete, instead takes k as another input and asks for any string that is within Hamming distance k of all the input strings.^[1]

The closest string problem can be seen as an instance of the 1-center problem in which the distances between elements are measured using Hamming distance.

Motivation

In bioinformatics, the closest string problem is an intensively studied facet of the problem of finding signals in DNA.

Simplifications and data reductions

Instances of closest string may contain information that is not essential to the problem. In some sense, the usual input of closest string contains information, that does not contribute to the hardness of the problem. For example, if some strings contain the character a, but none contains the character z, replacing all as with zs would yield an essentially equivalent instance, that is: from a solution of the modified instance, the original solution can be restored, and vice versa.

Normalizing the input

When all input strings that share the same length are written on top of each other, they form a matrix. Certain row types have essentially the same implications to the solution. For example, replacing a column with entries (a,a,b) with another column (x,x,y) might lead to a different solution string, but cannot affect solvability, because both columns express the same structure, viz. the first two entries being equal, but different from the third one.

An input instance can be normalized by replacing, in each column, the character that occurs the most often with a, the character that occurs the second most often with b, and so forth. Given a solution to the normalized instance, the original instance can be found by remapping the characters of the solution to its original version in every column.

The order of the columns does not contribute to the hardness of the problem. That means, if we permute all input strings according to a certain permutation π and obtain a solution string s to that modified instance, then π⁻¹(s) will be a solution to the original instance.

Example

Search space for the normalized problem. The center string aaaa and aaab leads to Hamming distances 1,2,1 and 2,1,1, respectively.

Given an instance with three input strings uvwx, xuwv, and xvwu. This could be written as a matrix like this:

u	v	w	x
x	u	w	v
x	v	w	u

The first column has the values (u,x,x). As x is the character that appears the most often, we replace it by a, and we replace u, the second most often character, by b, obtaining the new first column (b,a,a). Doing the same with all columns gives the normalized instance

b	a	a	a
a	b	a	b
a	a	a	c

Data reduction obtained from normalization

Normalizing the input reduces the alphabet size to at most the number of input strings. This can be useful for algorithms whose running times depend on the alphabet size.

Approximability

Li et al. evolved a polynomial-time approximation scheme^[3] which is practically unusable because of the large hidden constants.

Fixed-parameter tractability

Closest String can be solved in $O(kL+kd\cdot d^d)$, where k is the number of input strings, L is the length of all strings and d is the desired maximum distance from the solution string to any input string.^[4]

Relations to other problems

Closest string is a special case of the more general closest substring problem, which is strictly more difficult. While closest string turns out to be fixed-parameter tractable in a number of ways, closest substring is W[1]-hard with regard to these parameters.

References

1. Lanctot, J. Kevin; Li, Ming; Ma, Bin; Wang, Shaojiu; Zhang, Louxin (2003), "Distinguishing string selection problems", Information and Computation 185 (1): 41–55, doi:10.1016/S0890-5401(03)00057-9, MR 1994748
2. Bin Ma and Xiaming Sun, (2008), More Efficient Algorithms for Closest String and Substring Problems (PDF), LNCS 4955, Springer, pp. 396–409
3. M. Li, B. Ma, and L. Wang. (2002), "On the Closest String and Substring Problems." (PDF), Journal of the ACM 49 (2): 157–171, doi:10.1145/506147.506150
4. Jens Gramm, Rolf Niedermeier, and Peter Rossmanith (2003), "Fixed-Parameter Algorithms for Closest String and Related Problems", Algorithmica 37: 25–42, doi:10.1007/s00453-003-1028-3