Math 297/Biol 497

Biomolecular Computing in Nature

Assignment 9

 [Home]

The following color-coded strips represent doublestranded DNA molecules in 5' to 3' direction. Each symbol in these strips represents a segment of DNA in such a way that distinct symbols represent ``significantly distinct" nucleotide sequences, while identical nucleotide sequences are represented by identical symbols.

Consider the following DNA computational set-up:

The Program:  The following 33 DNA molecules represent the program for the computation:

 

A

x

N

D

x

N

E

x

N

F

x

N

A

x

1

B

x

2

D

x

2

D

x

4

G

x

4

H

x

4

E

x

5

E

x

6

F

x

6

F

x

7

G

x

7

H

x

7

N

y

C

N

y

F

N

y

G

N

y

H

N

y

I

N

y

J

2

y

F

4

y

J

5

y

F

5

y

G

5

y

I

6

y

G

6

y

J

7

y

J

8

y

E

8

y

F

8

y

I

The Hardware: The processing hardware is the enzyme complex responsible for carrying out the dlad intra-molecular operation.

1. Determine the output for the following input:

   A

   x

   8

   y

   B

   x

   1

   y

   C

   x

   3

   y

   D

   x

   5

   y

   E

   x

   7

   y

   F

   x

   4

   y

   G

   x

   2

   y

   H

   x

   6

   y

   I

   x

   N

   y

   J

    

2. What is the relationship between this computation, and the following ``8-puzzle"? (See the notes on permutations handed out some time ago.)

    

   8	1	3
   5	7	4
   2	6

    

3. Determine corresponding program molecules and an input molecule that would compute a solution of the following 8-puzzle:

    

   7	3	5
   4	8	1
   2	6

    

4. Is there a single molecular program that would, for each input molecule representing a solvable 8-puzzle, produce an output molecule representing a solved 8-puzzle?