McGill University - School of Computer Science

Computational Geometry Seminar

Everybody is welcome.
DATE: Wednesday, October 21st, 1998
TIME: 16:00-17:00
PLACE: McConnell 320
TITLE: DNA computing in vitro and in vivo.
SPEAKER: Lila Kari, University of Western Ontario
Biomolecular computing is a new computational paradigm that employs (bio)molecule manipulation to solve computational problems, while at the same time exploring natural processes as computational models. The excitement generated by the first successful experiment (Adleman, 1994) was due to the fact that computing with biomolecules (mainly DNA) offered an entirely new way of performing and looking at computations. The main idea was that data could be encoded in DNA strands, and molecular biology techniques could be used to execute computational operations.

This talk addresses the issues of the computational power of DNA computing in vitro and in vivo.

Firstly, I present a mathematical model of DNA computing based on insertions and deletions, which turns out to have universal computational power. As insertions and deletions are implementable by using site-specific mutagenesis, this opens one possible way of designing ``test-tube'' programmable DNA computers.

Secondly, I show that guided homologous recombinations that take place during gene rearrangement in ciliated protozoans have the computational power of a Turing machine. This indicates that in principle a unicellular organism has the capacity to perform at least any computation carried out by an electronic computer.

Besides the novelty of the approach, biomolecular computing has the potential to outperform electronic computers. For example, DNA computations may use a billion times less energy than an electronic computer, while storing data in a trillion times less space. Moreover, computing with DNA is highly parallel: in principle there could be billions or trillions of DNA molecules undergoing chemical reactions, that is, performing computations, simultaneously.

This is a joint seminar with the Centre for Nonlinear Dynamics in Physiology and Medicine.
This information is available at http://cgm.cs.mcgill.ca/~therese/seminar.
Direct questions, comments, additions to and removals from the mailing list, and suggestions for speakers to Therese Biedl at therese@cgm.cs.mcgill.ca.