NANO: Collaborative Research: Algorithmic error-correction in biologically inspired self-assembly and computation

自组装是小的“部件”自发形成错综复杂的集合体结构的过程。DNA自组装是纳米技术、纳米机器人和分子计算的关键工具。更广泛地说，生物有机体是执行遗传物质DNA中编码的算法的自组织化学系统。生物学因此提供了明确的证据，证明自主的化学系统可以被编程，并且它们可以在大范围内可靠地发挥作用--生物有机体可以由多达1024个分子成分组成！最近人工分子系统合成的实验进展表明，通过编程分子自组装来执行基本逻辑是可能的。这些实验还表明，错误的发生是扩大DNA自组装和生物启发计算的主要障碍。这个项目将设计算法工具和分析技术，用于生物启发的自组装和计算系统中的纠错和错误抑制。我们希望我们的研究将促进复杂的任务，如计数，增长预先指定大小(不大于或不小于)的分子组件，以及使用纳米级固有的容易出错的生物分子操作来识别复杂的化学信号。为了设计和分析我们的纠错机制，我们将使用既足够现实、有用又足够抽象的高级模型，以便进行分析。我们模型的基本元素将是DNA碎片、转录电路和DNA杂交催化剂。因此，我们的研究将以大分子的组装和计算为目标，例如DNA的长链，而不是蛋白质和氨基酸等较小的分子。我们还将根据我们的研究开发课程材料，这些材料将在加州理工大学和斯坦福大学教授。

Self-assembly is the process by which small ``components'' spontaneously form intricate aggregate structures. DNA self-assembly is a key tool for nano-technology, nano-robotics, and molecular computation. More generally, biological organisms are self-organized chemical systems that carry out algorithms encoded in the genetic material, DNA. Biology thus provides clear proof that autonomous chemical systems can be programmed, and that they can function reliably on a grand scale -- biological organisms can be composed of as many as 1024 molecular components!Recent experimental advances in the synthesis of artificial molecular systems have demonstrated that it is possible to program molecular self-assembly to carry out rudimentary logic. These experiments also suggested that the occurrence of errors is a major obstacle to scaling up DNA self-assembly and biologically inspired computation. This project will devise algorithmic tools and analysis techniques for error-correction and error-suppression in biologically inspired self-assembling and computational systems. It is our hope that our research will facilitate sophisticated tasks such as counting, growing molecular assemblies of pre-specified sizes (no larger, no smaller), and pattern recognition of complex chemical signals using inherently error-prone biomolecular operations at the nano-scale.In order to design and analyze our error-correction mechanisms, we will use high level models which are both sufficiently realistic to be useful and sufficiently abstract to be amenable to analysis. The basic elements of our models will be DNA tiles, transcriptional circuits, and DNA hybridization catalysts. Thus, our research will target assembly of and computation with large molecules such as long chains of DNA rather than smaller molecules such as proteins and amino acids.We will also develop course material on the basis of our research which will be taught at Caltech and at Stanford.