(4.1) MEMS for BMC. MEMS is the technology of miniature actuators, valves, pumps, sensors and other such mechanisms. In particular, when controlling fluids it is known as micro-flow device technology. We investigated the use of micro-flow device technology for BMC, as this provides multiple benefits over the current techniques for BMC. Some of the current limits of BMC stem from the labor intensive nature of the laboratory work. Automation using available micro-flow technology allows a drastic reduction in this lab work. Micro-flow technology also may allow a drastic reduction in the large volume needed for the desired bio-molecular reactions to occur.

John H. Reif and Ashish Gehani, Microflow Bio-Molecular Computation, 4th DIMACS Workshop on DNA Based Computers, University of Pennsylvania , June, 1998. Invited to special issue of BIOSYSTEMS, 1999.

Demonstrated key portions of a prototype software simulation system for DNA computation. These software tools are expected to be very useful to optimize the experimental BMC protocols and minimize errors. A simulator was written in Java, which implemented the operations of the recombinant DNA model. The software models recombinant DNA operations at multiple levels of detail from high level down to the kinetics of reactions. For example, molecular complexes are represented as graphs at the granularity of nucleotides and have a level of spatial description such that most infeasible nucleotide complexes are not allowed to contaminate the data set as the computation is simulated. We used thermodynamic and kinetic models to represent interactions between complexes.

Improved Splicing Models. Characterized the generative capacity for formal representations of enzymatic actions on DNA molecules. We developed a dynamical model of time progression of DNA concentrations, using systems of differential equations for dynamic development of the concentrations of each variety of DNA molecules in a test tube as the molecules are processed by specified sets of enzymes. Performed second wet lab test of splicing theory.

We have developed an approach to DNA computation in which we 'write' on circular double stranded DNA molecules (plasmids) using biochemical processes. We have confirmed in the laboratory that we can carry out three of our 'write' operations in sequence - and then 'read' the result. New theoretical results concerning the splicing operations used in our laboratory work have been obtained.

T.Head, Circular suggestions for DNA computing, in: Eds. M.Gromov & A.Carbone, Pattern Formation, World Scientific, invited paper, 1999.

T.Head, M.Yamamura & S.Gal, Aqueous computing: writing on molecules, Proceedings of the Congress on Evolutionary Computing (CEC'99), invited paper, July 6-9, 1999.

Liposome Models. We also have developed a theoretical liposome-based approach to DNA-based computation. This technique is based upon the compartmentalization and/or combination of the DNA molecules to be employed in a computation, via encapsulation in liposomes formed from various types of biological lipids.

Bloom, B., C. Bancroft, Liposomal-Mediated Biomolecular Computation, 5th International Meeting on DNA Based Computers(DNA5), MIT, Cambridge, MA, (June, 1999).To appear in DIMACS Series in Discrete Mathematics and Theoretical Computer Science, ed. E. Winfree, (1999).

We developed models of BMC based on the gene scrambling and RNA editing done by biological systems such as Ciliates.

Landweber, L. F. (1998) The Evolution of DNA Computing: Nature's Solution to a Path Problem. IEEE Proceedings of Symposia on Intelligence and Systems '98, May 21-23, 1998. IEEE Computer Society Press, 133-139.

Landweber, L. F. and L. Kari. (1998) The Evolution of DNA Computing: Nature's Solution to a Computational Problem. 1998 Genetic Programming Conference Proceedings, John Koza et al., eds., Morgan Kaufmann Publishers, Inc., 700-708.

Kari, L. and L. F. Landweber. (in press) Computing with DNA. Methods in Molecular Biology.

Forbes, N. A. and L. F. Landweber. (1999, in press) Computer Science and Meta-Evolution. Trends in Genetics.

Landweber, L. F., Horton, T. L. and L. Kari. (in press) Evolution of Gene Scrambling and RNA Editing: Protists Perform Computations!

Landweber, L. F. (in press) The Evolution of Cellular Computing. The Biological Bulletin.

We have developed methods for evaluating large Boolean circuits (logic gate circuits) using DNA. We showed the tight connection between the simplest computational model with DNA and traditional circuit model. In particular, we proved that bounded fan-in circuits can be evaluated by DNA-based computers that use a small number of biochemical operations within computation time O(depth). The running time under the model corresponds to that of circuits and the size to that of circuits. This on-going work is expected to lead to more efficient BMC experimental protocols.

M. Ogihara, Relating the Minimum Model for DNA Computation and Boolean Circuits, to appear in Genetic and Evolutionary Computing conference '99 (GECCO '99)

M. Ogihara and A. Ray, Circuit evaluation: thoughts on a killer application in DNA computing. In Computing with Bio-Molecules. Theory and Experiments (G. Paun, ed.), pages 111--126, Springer-Verlag, Singapore, 1998.

We intend to collaborate with a MEMS group to experimentally demonstrate the utility of MEMS in BMC.

We are now completing a demonstration of all features of prototype software simulation system for DNA computation. These software tools are expected to be very useful to optimize the experimental BMC protocols and minimize errors.

We are now completing a lab demonstration of an example illustrating the new limit language concept. We are now completing our new differential equations model for the dynamics of the DNA contents of a test tube in which the DNA molecules are being acted on by enzymes and to initiate wet lab confirmation of the model.

We plan to solve several hard algorithmic problems by using our tested method of 'writing' (cut & paste). Our next step will be to develop a method of 'writing' on our plasmids that will allow the solution of large scale instances of similar problems. We plan to 'write' by attaching short single stranded PNA molecules (P: protein backbone) to the plasmids and to 'read' by separation based on mass of the resulting complexes. New theoretical results on splicing and test tube computing will be written by two Ph.D. candidates working with us.

In the next year we will further explore the potential of DNA methods as those for evaluating Boolean circuits. In particular we will explore problems that are amenable to massive parallel circuit evaluation with DNA. We are now designing experimental tests of our new methods for efficient simulation of NC circuits.