CAREER: Research in Algorithmic Theory of Self-Assembly

自组装是简单物体自发组装成复合物的过程。它有望最终成为原子和分子水平上的重要技术。 可编程自组装研究的发展已经到了必须从数学上理解它才能充分利用这一新工具的阶段，本研究的目标是研究自组装的计算方面.本项目的目标包括：（1）解决瓦片装配模型中的具体问题，包括但不限于寻找最小瓦片集问题（MTSP）的近似算法和形状语言的特征化。(2)探索不同的自组装模型，这将给出一个更准确的抽象的实验结果，并将反映在分子/DNA计算的大规模并行。(3)研究算法自组装与经典计算理论之间的联系，特别是通信理论和资源受限的Kolmogorov复杂性。这个CAREER项目将把教学活动融入自组装的研究中。PI将提供分子计算和生物信息学等密切相关领域的研究生课程，本研究将采用主动学习的教学方法，希望能对了解自组装的工程能力，并向学生传播最新的研究信息。

Self-assembly is the process by which simple objects spontaneously assemble into complexes. It is expected to ultimately become an important technology at the level of atoms andmolecules. The development of researches in programmableself-assembly is reaching the stage that we haveto understand it mathematically in orderto take full advantage of this new tool.The goal of this research is to study the computational aspects of self-assembly. The objectives of this project includes: (1) Solving concrete problems in the Tile Assembly Model,including but not limited tofinding an approximation algorithm for the MinimumTile Set Problem (MTSP)and characterizing the shape languages.(2) Exploring different modelings of self-assembly, whichwill give a more accurate abstraction of the experimental results and will reflect the massive parallelism in molecular/DNA computing.(3) Studying the connections between the algorithmic self-assembly and the classical theoryof computation, especially the communication theoryand the resource-bounded Kolmogorov complexity.This CAREER project will integrate teaching activity into the research of self-assembly.The PI will offer graduate level courses in molecular computing and closely-related fields such as bioinformatics, and introduce the researchto undergraduate and graduate students in general theory courses.This project will adopt the active learning techniques in teaching.It is expected that the project will contribute to understandingthe engineering power of self-assembly, and to disseminatingthe current research information to students as well.