Comp.rgu.ac.uk

PROB033: WORD DESIGN FOR DNA COMPUTING ON SURFACES This problem has its roots in bio-informatics and coding theory, it involves to find as large a set S of strings(words) of length 8 over the alphabet W = {A C G T } with the following properties: • C1: each word in S has 4 symbols from {C G}.
• C2: each pair of distinct words in S differ in at least 4 positions.
• C3: each pair of words x y ∈ S (where x and y may be identical) are such that x R and yC differ in 8)C is the Watson-Crick complement of (y1 , . . . , 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.
Without losing generality, we use natural numbers to model the problem, under the mapping {(1 → A) (2 → C ) (3 → G) (4 → T )}, we introduce the set W as Integer range and the type word to be the set of all sequences over W , whose length is 8.
Since the problem involves position-wise comparison of words, we use the following recursively-defined func-tion seqdiff , which compares two sequences and returns the number of different positions.
∀ x y : X • diff (x y) = if x = y then 1 else 0 seqdiff (s t) = diff (head s head t) + seqdiff (tail s tail t) We proceed with the problem constraints, the Watson-Crick complement is achieved by composition with astatic mapping as shown below.
PROB033: WORD DESIGN FOR DNA COMPUTING ON SURFACES ∀ w : word • watson crick (w ) = {1 → 4 2 → 3 3 → 2 4 → 1} ◦ w (count(items w ) 2) + (count(items w ) 4) = 4 Constraint C1 follows the description of the complement, elements C and G are represented by 2 and 4,respectively. The count function counts the occurrences of elements in a bag p. 124], items returns abag of all items in a sequence p. 127]. The subsequent constraintC2 uses the difference of w1 and w2 asantecedent. The seqdiff function is applied here and in the following C3 constraint, where rev s reverses thesequence s p. 116].
[1] J. M. Spivey. The Z Notation: A Reference Manual. J. M. Spivey, Oriel College, Oxford OX1 4EW, second edition, 1998.
First published 1992 by Prentice Hall, current version on

Source: http://www.comp.rgu.ac.uk/staff/ha/ZCSP/prob033/prob033.pdf