AMMCS-2013 Plenary Talk

Nanocomputations by DNA Self-Assembly

Lila Kari

Abstract: Self-assembly, the process by which objects autonomously come together to form complex structures, is ubiquitous in the physical world: Atoms bind to each other to form molecules, molecules may form crystals or macromolecules, cells interact to form biological organisms. Recent experimental research in DNA self-assembly demonstrated its potential for the parallel creation of a large number of nanostructures, including some encoding computations. This suggests exciting applications of self-assembly to circuit fabrication, nanorobotics, DNA computation, smart-drug design, and amorphous computing.

A systematic study of self-assembly as a computational process has been initiated by Adleman and Winfree. The individual components are therein modelled as square tiles on the infinite two-dimensional plane. Each side of a tile is covered by a specific "glue", and two adjacent tiles will bind to each other iff they have matching glues on their abutting edges. Tiles that stick to each other may form various two-dimensional structures such as squares, rectangles, counters, or may cover the entire plane.

In this talk I will describe the potential of the self-assembly of "DNA tiles" for nanocomputations. In addition, I will explore generalizations of the original model that add the possibility of having negative, "repelling", glues, as well as compare the computational power of deterministic versus non-deterministic self-assembly.

Lila Kari is Professor in the Department of Computer Science at The University of Western Ontario. She received her M.Sc. in 1987 from the University of Bucharest, Romania, and her Ph.D. in 1991 for her thesis "On Insertions and Deletions in Formal Languages", for which she received the Nevanlinna Prize for the best mathematics thesis in Finland. Author of more than 170 peer reviewed articles, Professor Kari is regarded as one of the world's experts in the area of biomolecular computation, that is using biological, chemical and other natural systems to perform computations. She has served as Steering Committee Chair for the DNA Computing conference series, as Steering Committee member for the Unconventional Computation conference series, as well as on the Scientific Advisory Committee of the International Society for Nano-Scale Science and Engineering.

Lila Kari serves on the editorial boards of the journals Theoretical Computer Science, Natural Computing and Universal Computer Science, and as section editor for molecular computing for the Natural Computing Handbook (Springer). She has additionally served as a member of the Board of Directors of the FIELDS Institute for Research in Mathematical Sciences, the UK EPSRC peer review college, on the NSERC grant selection committee on computing and information systems and the NSERC Herzberg-Brockhouse-Polanyi Prize joint selection committee. At the University of Western Ontario she has received numerous awards, including the Florence Bucke Science Prize and the Faculty of Science Award for Excellence in Undergraduate Teaching. From 2002 to 2011 she was Canada Research Chair in Biocomputing, and her current research focusses on theoretical aspects of bioinformation and biocomputation, including models of cellular computation, nanocomputation by DNA self-assembly and Watson-Crick complementarity in formal languages.