033: Word Design for DNA Computing on Surfaces

Proposed by Marc van Dongen

This problem has its roots in Bioinformatics and Coding Theory.

Problem: find as large a set S of strings (words) of length 8 over the alphabet W = { A,C,G,T } with the following properties:

• Each word in S has 4 symbols from { C,G };
• Each pair of distinct words in S differ in at least 4 positions; and
• Each pair of words x and y in S (where x and y may be identical) are such that x^R and y^C differ in at least 4 positions. Here, ( x₁,…,x₈ )^R = ( x₈,…,x₁ ) is the reverse of ( x₁,…,x₈ ) and ( y₁,…,y₈ )^C is the Watson-Crick complement of ( y₁,…,y₈ ), i.e. the word where each A is replaced by a T and vice versa and each C is replaced by a G and vice versa.