Molecular Computing

A ground-breaking paper by Leonard Adleman in 1994 presented a method for solving the Hamilton Path Problem using liquid-phase DNA chemistry and demonstrated that the algorithm can be executed in a laboratory. Advantage of using biological molecules such as DNA for computation lies in the fact that they have storage capacity and that the operations can be conducted at room temperature. In search of killer applications of molecular computation, researchers have been exploring various molecular-based computational models and algorithms.

List of Papers

  1. M. Ogihara and A. Ray, The Minimum-Model DNA Computation on a Sequence of Probe Arrays. In Proceedings of the Third International Conference on Unconventional Models of Computation, pages 38-49. Springer-Verlag Lecture Notes in Computer Science #2509, 2002.
  2. S. Diaz, J. L. Esteban, and M. Ogihara, A DNA-based random walk method for solving k-SAT. Proceedings of the Sixth International Workshop on DNA-based Computers, Springer-Verlag Lecture Notes in Computer Science, 2000. GZIP-ed postscripted file GZIP-ed PDF file

  3. M. Ogihara and A. Ray, DNA computing on a chip. Nature 403:143 - 144, 2000.

  4. M. Ogihara, Relating the minimum model for DNA computation and Boolean circuits. Proceedings of the Genetic and Evolutionary Computation Conference, pages 1817 - 1821, Morgan Kaufman Publishers, San Francisco, CA, 1999. GZIP-ed postscripted file GZIP-ed PDF file

  5. M. Ogihara and A. Ray, Executing parallel logical operations with DNA. Proceedings of the Congress on Evolutionary Computation, pages 972 - 979, IEEE Computer Society Press, Piscataway, NJ, 1999. GZIP-ed postscripted file GZIP-ed PDF file

  6. M. Ogihara and A. Ray, Biomolecular computing - recent theoretical and experimental advances, SIGACT News , 30(2):22 - 30, 1999. GZIP-ed postscripted file GZIP-ed PDF file

  7. M. Ogihara and A. Ray, DNA-based parallel computation by counting. In DNA Based Computers III, (H. Rubin and D. H. Wood, eds.), DIMACS Series in Discrete Mathematics and Theoretical Computer Science Volume 48 , The American Mathematics Society Press, pages 255 - 264, 1999. GZIP-ed postscripted file GZIP-ed PDF file

  8. M. Ogihara and A. Ray, DNA-based self-propagating algorithm for solving bounded-fan-in Boolean circuits Third Conference on Genetic Programming, pages 725 - 730, Morgan Kaufman Publishers, San Francisco, CA, 1998. GZIP-ed postscripted file GZIP-ed PDF file

  9. 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. GZIP-ed postscripted file GZIP-ed PDF file

  10. M. Ogihara and A. Ray, The minimum DNA computation model and its computational power. Unconventional Models of Computation (C. S. Calude, J. Casti, and M. J. Dinneen, eds.), pages 309 - 322, Springer, Singapore, 1998. GZIP-ed postscripted file GZIP-ed PDF file

  11. M. Ogihara and A. Ray, Simulating Boolean circuits on a DNA computer. First Annual Conference on Computational Molecular Biology, pages 326 - 331, ACM Press, 1997. The final version: Algorithmica 25:239 - 250, 1999. GZIP-ed postscripted file GZIP-ed PDF file

  12. M. Ogihara, A. Ray, and K. Smith, DNA computation - a shape of computing to come SIGACT News 28(3), pages 2 - 11, 1997. GZIP-ed postscripted file GZIP-ed PDF file

  13. M. Ogihara, Breadth first search 3SAT algorithms for DNA computers. Technical Report TR-629, Department of Computer Science, University of Rochester, July 1996. GZIP-ed postscripted file GZIP-ed PDF file