4. ∆4 is minimised: if a solution is found with ∆4 = d, search for another solution with ∆4 = d − 1
(unless d = dmin).
∆1 are the search variables: nodes of the search tree consist of values assigned to these variables. ∆4 is the objective function (or cost function). A returned solution is ∆1 ∪∆4, a closest string together with the optimal distance. Solving ϒ(S,dmin,HD(S)) is guaranteed to return a solution, although it is not impossible that all 4L nodes are visited for every current minimal d. Restricting the domains of ∆3 will save computational effort when a solution is found with d = dmin and will have no effect otherwise.

Restricting the domains of the ∆1 variables in line with lemma 2 also reduces the search space, although the restrictions can not apply when searching for all solutions.

To find all closest strings ϒ(S,dmin,HD(S))is solved to obtainCS and dopt. By restricting the domains of ∆3 to dmin through dopt and removing the optimisation constraint we obtain a new CSP ϒ
∗(S,dmin,d)
which can be solved for all solutions. The search undertaken to find the first solution CS need not be repeated: constraints can be added that rule out those parts of the search tree already processed. It should also be noted that CS and d need not be obtained using the Constraint Satisfaction approach: any method that returns an optimal solution can be used to create an all closest strings CSP.

## 2.1 Position Weight Matrix Variable And Value Ordering

We now use results from computational biology to devise a bespoke variable and value ordering schema for ϒ(S,dmin). By precalculating a Position Weight Matrix for S as defined in Section 1.3 we can order the search variables by maximum frequency. For each variable, we order the values assigned during search by decreasing relative frequency. Tie breaks are either random or by least index. In the example given as Figure 1 the variable ordering by position 1 through 8 would be 1: position 4 (having 5 occurrences), 2 - 5: positions 2, 3, 6, and 8 in any order (each having 4 occurrences), 6–8: positions 1 and 7 in any order
(having the least highest frequency of 3). The value ordering for position 5 in the figure would be 1: A (most frequent), 2–3: T and C in any order, 4: G (least frequent). By Lemma 2, when seeking a single solution it is safe to exclude values that don't appear at a given position from their respective variable domains before search. Hence in for the example in Figure 1 the value ordering would be values typeset in blue followed by values typeset in red, with black values excluded.

The idea behind this search heuristic is that search starts close to (in the sense of maximum likelihood) an optimal solution. Only if no such solution is found does search progress to less likely (but not impossible) parts of the search tree .

## 2.2 Comparison Of Search Heuristics

In this Section we test the hypothesis that PMS-based search heuristics reduce the search needed for solutions to ϒ(S,dmin) CSP instances when compared to a standard heuristic. Figure 2 illustrates the results from 200 closest string problems. Each problem was run first with smallest domain variable ordering and ascending value ordering (Minion defaults), and then with PWM-based variable and value ordering as described in Section 2.1.

For exact solutions - upper panel of Figure 2 - we observe an improvement of PWM over SDF in almost all cases. The speedup is as high as several orders of magnitude in some cases. The difference is statistically significant at the 0.001 level. These results are as expected: the PWM reflects the maximum likelihood of a closest string, so a search that respects these likelihoods will nearly always be highly efficient, but will visit very many non-essential nodes on the few occasions that the maximum likelihood does not lead to a closest string. A key observation is that the magnitude of speedup increases with increasing string length, which is highly encouraging since the complexity of closest sting is exponential in string length.