pre-defined tolerance, then numeric branch and bound methods are used to solve an Integer Programming formulation of the problem not yet solved by Minion. If the distance under consideration ever becomes fixed, then the linear time methods set out in [11] can be applied.

It should be stressed that these three methods (CSP, IP branch and bound, and linear time) need not be exclusive: once tolerance achieving bounds are found by Minion, the distributed Minion search can continue, and the CSP and numeric methods are then competing to find the first solution. This of course pre-supposes that computational resource is not a problem, but that is why we are using web-scale facilities in the first place.

## 4 Discussion

We have performed (to our knowledge) the first evaluation of Constraint Satisfaction as a computational framework for solving closest string problems. We have shown that careful consideration of symbol occurrences can provide search heuristics that give, in general, several orders of magnitude speedup when computing approximate solutions. We have also shown that CSP is less effective when searching for certificates of distance optimality. This result motivated our detailed description of algorithms for web-scale distributed CSP computation, and also our design of hybrid distributed algorithms that can take advantage of the strengths of both numeric and CSP computational techniques.

We have also performed (to our knowledge) the first analysis of the computational difficulties involved in the identification of all closest strings for a given input set, irrespective of the computational framework used. Our results for all closest strings motivate the question of which definition of selfsimilarity is suitable for the computational biology setting. In terms of information theory the all closest strings problem can not exclude alphabet symbols and still be correct. However, when seeking to quantify the self-similarity of DNA sequences it may be perfectly justifiable to exclude closest strings that can have no symbol in common with the sequences in question at a given point. If this were to be the case, then the computational efficiency of the search for all closest strings would be greatly increased (Figure 4).

We have designed, implemented and deployed a computational methodology for distributed search for closest string solutions. This contribution provides a practically useful means of attacking the NPcomplete instances by division into smaller sub-problems. Our system is guaranteed never to perform the same search twice, will recover seamlessly from any unforseen loss of compute nodes, and is extendable to web-scale clouds.

The limitations of this study are that we have not been able to compare numeric solutions to CSP
solutions directly, (nor assess the hybrid numeric-CSP algorithm described in the paper), and that we have not attacked real world problems in a distributed setting, instead solving randomly-generated instances. We have outlined the possibility of super-linear speedups for distributed search, but present no supporting evidence as our distributed implementation has as yet been tested solely for accuracy, scalability and robustness.

## 4.1 Future Work

Possible future avenues of research include

- Performing full-scale cloud searches for solutions to real-world closest string problems (rather than concentrating on randomly-generated problem instances as for this paper)
- The provision of a fully distributed IP branch and bound solver for use in Algorithm 3