A solution of size 108 is reported in the
(Anthony G. Frutos,
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.
have managed to find the solution of size 112
listed at the end of this page
with an implementation of an optimisation CSP in
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 ECLiPSe) 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