Definition. Let S = {S1,S2,...,SN} be a set of strings of length L over an alphabet Σ. A Closest String to S is defined as any string CS of length L over Σ such that hd(CS,Si) ≤ d ∀i ∈ {1,2*,...,*N}
with d being the minimal such distance for S. The Hamming diameter *HD of S is defined as* HD(S) = max(hd(Si,Sj)) ∀i, j ∈ {1,2*,...,*N}.

A solution to a closest string problem involving the strings in S is therefore a string CS and a minimal distance d such that each member of S is within d of CS. The Hamming distance is an edit distance that quantifies the number of substitutions from Σ required to turn one string into another. It is easy to show that Hamming distance is a metric, satisfying the triangle inequality. It is clear that the Hamming Diameter is an upper bound for the distance of a closest string: a candidate closest string at a greater distance can be replaced by any member of S, reducing the maximal distance to HD(S). We can obtain a lower bound for the distance of a closest string by observing that the distance can not be less than half the Hamming Diameter:
Lemma 1. Let S = {S1,S2,...,SN} be a set of strings of length L over an alphabet Σ. A closest string CS to S must be within dHD(S)/2e of S.

Proof. Let Si and Sj be two strings from S for which the Hamming Diameter is achieved, and let Sk be any other string of length L over Σ. By the triangle inequality H(S) = hd(Si,Sj) ≤ hd(Si,Sk)+hd(Sj,Sk). If (without loss of generality) hd(Si,Sk) < dHD(S)/2e then hd(Sj,Sk) ≥ dHD(S)/2e. Hence any distance less than dHD(S)/2e can not be a maximal distance from Sk to any string in S.

Search space reduction can be achieved by noting that any value not appearing in position j of any of the strings in S need not appear in a closest string solution. It should be noted that this only applies when searching for the first optimal solution. When searching for all solutions, any symbol from Σ can, in principle, appear at any position in CS.

Lemma 2. Let S = {S1,S2,...,SN} be defined as in Lemma 1. Let Σjfor j ∈ 1,2,...,L denote the subset of Σ obtained by selecting every symbol that appears in position j of a string in S. Then any symbol in position j of a closest string to S must also be in Σj.

Proof. Suppose symbol s in Σ\Σj appears in position j of a solution CS. Let CS∗ be the string consisting of CS with s replaced by a symbol from Σj at position j. Then CS∗is strictly closer to those strings in S
with that symbol at that position, and distance to all other strings is unchanged. Hence if the current d is optimal for CS, it remains optimal for CS∗.

The final definition needed for this investigation encapsulates frequencies of symbol appearances per string position, and will be used in Section 2.1 to direct backtrack search for closest strings.

Definition. Let S = {S1,S2,...,SN} be a set of strings of length L over an alphabet Σ. A Position Weight Matrix (PWM) for S is an |Σ| × L matrix with entries PMSS(i, j) defined as the frequency of symbol i appearing at position j in S. An example Position Weight Matrix is given in Figure 1.