Mitsunori Ogihara, Wednesday Dec. 13, 2:30 PM
Margery Ishmael
marge at cs.uchicago.edu
Thu Dec 7 12:50:09 CST 2000
DNA-Based Parallel Boolean Circuit Evaluation
Mitsunori Ogihara
University of Rochester
Wednesday, December 13, 2:30 pm
Ryerson Annex 276
(followed by refreshments in Ryerson 255)
Abstract:
DNA-based computation is a new field that integrates molecular biology and
computer science. The goal of the field is to study the use of liquid-phase
DNA for massively parallel computation. The potential of using DNA for
computation lies in the fact that DNA has large
memory capacity (10^22 bits in one liter of DNA solution) and that
biochemical operations are inherently parallel and dissipate little energy.
The drawbacks are that biochemical operations are slow and sometimes
error-prone.
A paper by Adleman in 1994 presented the first DNA-based algorithm, which
is for solving the Hamilton Path Problem. Lipton extended Adleman's idea
and showed that SAT, the basic NP-complete problem, could be solved using
DNA. Since then, various DNA computational models have been proposed and
many DNA-based algorithms have been
developed. Two most important issues in this field are to clarify the power
of DNA-based computation and to find killer applications, i.e., the
problems in which DNA are more efficient than silicon-based computers.
In this talk I will speak about simulation of logic-gates using DNA. First,
I will show how one can simulate AND and OR using DNA and then based on the
construction how one can evaluate the output of a Boolean circuit on a
given input. Then I will discuss the issue of eliminating human
intervention in circuit evaluation. Finally, I will talk about
characterization of DNA-based computation in terms of Boolean circuit
complexity.
Host: Stuart Kurtz
If you would like to meet with the visitor on December 13, please send a
request by e-mail to marge at cs.uchicago.edu
====================================================
Margery Ishmael
Department of Computer Science
1100 E. 58th St.
Chicago, IL 60637
tel: 773 834-8977 fax: 773 702-8487
marge at cs.uchicago.edu
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20001207/fce1623d/attachment.htm
More information about the Colloquium
mailing list