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

Mike Codish reports a new solution with 128 words. This was included in Dan C Tuplan’s PhD thesis ( [tulpan2006effective]).

M. Codish, M. Frank, and V. Lagoon also found a solution with 128 words using a SAT solver and a clustering technique. This work was presented at ModRef 2016 workshop [codishWordDesign].

The solution file provided by Mike Codish can be found here

File	Type	Notes
length_112.md	md	A solution of size 112
length_118.md	md	A solution of size 118 found using BDD/SAT methods by Vitaly Lagoon.
length_128.md	md	A solution of size 128