Math 297/Biol 497
Biomolecular Computing in
Nature
Assignment 9
[Home]
- Design a 2-state, 2-symbol finite automaton which uses the restriction enzyme Fal I as hardware.
Note that this enzyme has the following features:
- Recognition site:
| A |
A |
G |
N |
N |
N |
N |
N |
C |
T |
T |
| T |
T |
C |
N |
N |
N |
N |
N |
G |
A |
A |
- Cleave pattern:
| A |
A |
G |
N |
N |
N |
N |
N |
C |
T |
T |
N |
N |
N |
N |
N |
N |
N |
N |
N |
N |
N |
N |
N |
N |
| T |
T |
C |
N |
N |
N |
N |
N |
G |
A |
A |
N |
N |
N |
N |
N |
N |
N |
N |
N |
N |
N |
N |
N |
N |
- Can a 3-state, 2-symbol finite automaton be implemented using this hardware?
- Can a 2-state, 3-symbol finite automaton be implemented using this
hardware?
- Program the 2-state, 2-symbol (say the symbols are x and y) automaton to
determine for arbitrary inputs, if the final symbol encountered is an x.
Demonstrate the workings of this automaton schematically for at least two
different inputs of length at least 4 symbols.
General question. Examine some of the restriction enzymes commercially
available (For example from Fermentas or New England Biolabs). What is the
largest number of states and alphabet symbols finite state automaton you can
design using these, or a combination of them, as hardware? For example, can you
design a finite state automaton that would determine of a given input number is
divisible by 3? Can you, for a fixed positive integer m, design a finite
automaton that would, for input integers n, report what the remainder is upon
dividing n by m?