学术报告(Ming-Yang Kao)

主题：  Algorithmic DNA Self-Assembly

报告人：   Prof. Ming-Yang Kao

Northwestern University, USA

时间：  2008年10月16日下午15：30

地点：  蒙民伟楼311室

Abstract：

Self-assembly is a process by which simple objects autonomously assemble into complexes. This phenomenon is common in nature but is not yet well understood from mathematical and programming perspectives. It is believed that self-assembly technology will ultimately permit the precise fabrication of complex nanostructures. There are many kinds of self-assembly. Of particular interest is DNA self-assembly. Double and triple crossover DNA molecules have been designed to act as four-sided building blocks, called tiles, for DNA self-assembly. Experimental work has been done to show the effectiveness of using these tiles to assemble crystals and perform computation. Based on such building blocks, researchers have considered the power of the tile self-assembly model.

The tile assembly model extends the theory of Wang tilling of the plane by adding a natural mechanism for growth. Informally, the model consists of a set of four sided Wang tiles whose sides are each associated with a type of glue. The bonding strength between two glues is determined by a glue function. A special tile in the tile set is denoted as the seed tile. Assembly takes place by starting with the seed tile and attaching copies of tiles from the tile set one by one to the growing seed whenever the total strength of attraction from the glue function meets or exceeds a fixed threshold called the temperature.

Algorithmic DNA self-assembly is both a form of nanotechnology and a model of DNA computing. As a computational model, algorithmic DNA
self-assembly first encodes the input of a computational problem into DNA patterns and shapes; and then manipulates these structures to produce new DNA structures that encode the desired output of the computational problem. As a nanotechnology, the goal of algorithmic DNA self-assembly is to design tiles with carefully chosen glue types on their four sides. Tiles are said to be of different types if their sides have different glue types. Useful tile types are nontrivial to design but relatively easy to duplicate in large quantity. A key design challenge for algorithmic DNA self-assembly is to use only a small number of different tile types to assemble a target nanostructure.

This talk will survey recent results in algorithmic DNA self-assembly and discuss future research directions.

Short Bio:

Ming-Yang Kao is a Professor of Computer Science at Northwestern University and serves as the Head of the Division of Computing, Algorithms, and Applications in the Department of Electrical Engineering and Computer Science. He has published extensively in the design, analysis, and applications of algorithms. His research interests include discrete optimization, bioinformatics, computational finance, computational economics, and DNA self-assembly. He is the Editor-in-Chief of Algorithmica and the Encyclopedia of Algorithms.