Experimentally Constructing Semantic Models Based on DNA Computing
Yusei Tsuboi, Zuwairie Ibrahim, and Osamu Ono
Institute of Applied DNA Computing, Graduate School of Science & Technology, Meiji University, 1-1-1 Higashimita, Tama-ku, Kawasaki-shi, Kanagawa 214-8571, Japan
We propose a new DNA-based semantic model, constructed of DNA molecules, called a semantic model based on molecular computing (SMC). It is structured as a graph formed by the set of all (attribute, attribute value) pairs contained in the set of represented objects, plus a tag node for each object. Each path in the network, from an initial object-representing tag node to the terminal node, represents the object named on the tag. Inputting a set of input strands the forms object-representing dsDNAs via parallel self-assembly from encoded ssDNAs representing both attributes and attribute values (nodes), as directed by ssDNA splitting strands representing relations (edges) in the network. The success of experiments in constructing a small test model demonstrates that our proposed model suitably represents knowledge to storing vast amounts of information at high density.
-  A. Marathe, A. E. Condon, and R. M. Corn, “On combinatorial DNA word design,” J. Comp. Biol., Vol.8, pp. 201-219, 2001.
-  D. Faulhammer, A. R. Cukras, R. J. Lipton, and L. F. Landweber, “Molecular Computation: RNA solutions to chess problems,” Proc. Nat1, Acad. Sci. USA., Vol.98, pp. 1385-1389, 2000.
-  E. B. Baum, “How to build an associative memory vastly larger than the brain,” Science, Vol.268, pp. 583-585, 1995.
-  F. Udo, S. Sam, B. Wolfgang, and R. Hilmar, “DNA sequence generator: A program for the construction of DNA sequences,” In N. Jonoska and N. C. Seeman (editors), Proc. of the Seventh International Workshop on DNA Based Computers, pp. 21-32, 2001.
-  G. Frutos, Q. Liu, A. J. Thiel, A. M. W. Sanner, A. E. Condon, L. M. Smith, and R. M. Corn, “Demonstration of a word design strategy for DNA computing on surfaces,” Nucl. Acids Res., Vol.25, pp. 4748-4757, 1997.
-  J. A. Rose, R. Deaton, D. Franceschetti, M. Garzon, and S. E. Stevens Jr., “A statistical mechanical treatment of error in the annealing biostep of DNA computation,” Proc. of Genetic and Evolutionary Computation 1999 Conference, pp. 1829-1834, 1999.
-  J. Chen, R. Deaton, and Y.-Z. Wang, “A DNA-based memory with in vitro learning and associative recall,” The 9th International Workshop on DNA Based Computers, DNA9, Revised Papers, Lecture Notes in Computer Science, Vol.2943, pp. 145-156, 2003.
-  J. F. Sowa, “Semantic networks,”
-  J. H. Rief, “parallel molecular computation, Models and simulations,” Proc. of the 7th Annual Symaposium on Parallel Algorithms and Architectures, pp. 213-223, 1995.
-  J. H. Reif, H. T. LaBean, M. Pirrung, V. S. Rana, B. Guo, C. Kingsford, and G. S. Wickham, “Experimental construction of very large scale DNA databases with associative search capability,” The 10th International Workshop on DNA Based Computers, Revised Papers, Lecture Notes in Computer Science, Vol.2943, pp. 231-247, 2002.
-  J. SantaLucia, H. Allawi, and P. Seneviratne, “Improved nearestneighbor parameters for predicting DNA duplex stability,” Biochemistry, Vol.35, No.11, pp. 355-356, 1996.
-  L. M. Adleman, “Molecular computation of solutions to combinatorial problems,” Science, Vol.266, pp. 583-585, 1994.
-  L. M. Adleman, “DNA computing FAQ,”
-  M. Arita, M. Hagiya, and A. Suyama, “Joining and rotating data with molecules,” Proc. of IEEE International conference on evolutionary computation, pp. 243-248, 1997.
-  M. R. Quillian, and M. Minsky, “Semantic memory, Semantic information processing,” MIT Press, Cambridge, MA, pp. 216-270, 1968.
-  P. Wasiewicz, T. Janczak, and J. J. Mulawka, “The Inference via DNA Computing,” Proc. of 1999 Congress on Evolutionary Computation, pp. 988-993, 1999.
-  R. Deaton, C. R. Murphy, M. Garzon, D. R. Franceschetti, and S. E. Stevens Jr., “Good encodings for DNA-based solutions to combinatorial problems,” in DNA Based Computers II (Landweber, L. and Baum, E., Eds.), American Mathematical Society, Providence, Vol.44, pp. 247-258, 1999.
-  R. Deaton, M. Garzon, R. C. Murphy, J. A. Rose, D. R. Franceschetti, and S. E. Stevens Jr., “Reliability and Efficiency of a DNA-based computation,” Phys. Review Letters, Vol.80, pp. 417-420, 1998.
-  R. J. Lipton, “DNA solution of hard computation problems,” Science, Vol.268, 1995.
-  R. Penchovsky, and J. Ackermann, “DNA library design for molecular computation,” Journal of Computational Biology, Vol.10, No.2, pp. 215-229, 2003.
-  S. Kobayashi, “Horn Clause Computation with DNA Molecules,” Journal of Combinatorial Optimization, Vol.3, pp. 277-299, 1999.
-  V. Mihalache, “Prolog Approach to DNA Computing,” Proc. of IEEE International Conference on Evolutionary Computation, pp. 249-254, 1997.