033: Word Design for DNA Computing on Surfaces

A solution of size 108 is reported in the literature (Anthony G. Frutos, Qinghua Liu, Andrew J. Thiel, Anne Marie W. Sanner, Anne E. Condon, Lloyd M. Smith, and Robert M. Corn, “ Demonstration of a Word Design Strategy for DNA Computing on Surfaces,” Nucleic Acids Research, 25 4748-4757 (1997). The solution was obtained by construction.

Coding theorists at UCC have since then computed a solution of size 112. This solution was obtained using a greedy algorithm. I have understood that the authors of the original paper have also found such a solution. (Private communication).

I have managed to find the solution of size 112 listed at the end of this page with an implementation of an optimisation CSP in ECLⁱPS^e. The solution was not easy to find in two ways. The first reason is that the CSP formulation is too large and that it is impossible to find a solution within reasonable time (at least with ECLⁱPS^e) and without a linear programming tool. To overcome this problem I combined the greedy and optimisation approach. The second reason is that the problem (at least with my formulation) is very sensitive to heuristics. This sensitivity to heuristics (choice of bases, really) also manifests itself with the greedy algorithms. Here then is the solution of size 112: