|M.Sc Thesis||Department of Chemistry|
|Supervisor:||Prof. Keinan Ehud|
The first nanoscale, programmable 2-state-2-symbol finite automaton that computed autonomously with all of its components, including hardware, software, input and output being biomolecules, mixed together in solution was recently presented (Benenson, Y. et al., Nature, 2001, 414, 430). The hardware consisted of a restriction nuclease and a ligase, while the software (transition rules) and the input were double-stranded (ds) DNA oligomers. Computation was carried out by processing the input molecule via repetitive cycles of restriction, hybridization, and ligation reactions to produce a final-state output in the form of dsDNA molecules.
We increased the levels of complexity and mathematical power of these automata by the design of a 3-state-3-symbol automaton having as many as 27 possible transition rules and a remarkable number of 939,524,089 syntactically distinct programs. This number is significantly larger than the corresponding number of 765 available programs with the previously reported 2-symbol-2-state device. Restrictions at the beginning of the symbol domain, 1 basepair deeper, and 2 basepairs deeper into the domain represent the three internal states, S0, S1 and S2, respectively. The applicability of this design was further amplified by employing surface-anchored input molecules, using the surface plasmon resonance (SPR) technology to monitor the computation steps in real time. Computation was performed by alternating the feed solutions between BbvI endonuclease and a solution containing ligase, ATP and appropriate transition molecules. The output detection involved final ligation with one of three soluble detection molecules. Parallel computation and real-time detection were carried out automatically with a Biacore chip that carried 4 different inputs.