Fetching contributors…
Cannot retrieve contributors at this time
28 lines (23 sloc) 1.22 KB
Title Proposer Category
Word Design for DNA Computing on Surfaces
Marc van Dongen
Combinatorial mathematics

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 xR and yC differ in at least 4 positions. Here, ( x1,…,x8 )R = ( x8,…,x1 ) is the reverse of ( x1,…,x8 ) and ( y1,…,y8 )C is the Watson-Crick complement of ( y1,…,y8 ), 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.