SGER: Algorithmic Issues at the Nano Scale

项目摘要自组装是指小“部件”遵循简单的组合规则形成复杂结构的过程。DNA自组装被广泛认为是纳米技术、纳米机器人和分子计算的关键工具。尤其是DNA自组装，以及一般的纳米技术，都带来了巨大的算法挑战。本项目将在这一领域探索两个令人兴奋的方向：1.纳米级的纠错。分子机器的模型和算法。智能优点：纳米级的纠错似乎需要与纠错码显著不同的工具和技术。例如，错误和纠错机制在纳米尺度上受到热力学定律的约束，以及纠正错误所需的任何“计算”必须使用相同的潜在容易出错的物理机制的约束。虽然特定的纠错机制在某些情况下是已知的，但普遍的理解还不是很清楚。许多实验小组已经开发出基本的(但非常有希望的)基于DNA的分子机器。这些机器的建模还处于初步阶段。对这些机器建模的探索性研究可能会引发有趣和具有挑战性的算法问题。广泛的影响：纳米级的纠错将促进复杂的任务，如使用固有的容易出错的DNA自组装(或其他技术)以极高的精度进行计数、生长预先指定大小的晶体(不能更大)、形状识别等。这将是一种新的工程原始，有点像发动机和半导体，具有重要的直接和不可预见的用途。此外，分子机器还可以充当传感器、信号载体、执行器或药物输送机制。毫无疑问，实现这些目标的大部分艰苦工作将由实验者完成(并且正在完成)。但PI相信算法技术也将发挥重要的辅助作用。PI将组织一个非正式的阅读研讨会，学生们将在其中深入探索这一领域。国际和平协会希望这次研讨会能提供有益的教育经验。PI还计划在Book上写一篇文章，面向不是该领域专家的具有科学素养的读者；文章将突出纳米级的算法问题。

Project SummarySelf-assembly is the process by which small "components" follow simplecombination rules to form intricate structures. DNA Self-assembly is widelybelieved to be a key tool for nano-technology, nano-robotics, and molecularcomputation. DNA self-assembly in particular, and nano-technology in general,offer significant algorithmic challenges. This project will explore twoexciting directions in this field:1. Error correction at the nano scale.2. Models and algorithms for molecular machines.Intellectual merit: Error correction at the nano scale appears to requiretools and techniques that are significantly different from those required forerror correcting codes. For instance, errors and error correction mechanismsare bound by thermodynamic laws at the nano scale, as well as by the constraintthat any "computation" required to correct an error must be carriedout using the same underlying error prone physical mechanism. While specificerror correction mechanisms are now known in certain cases, a generalunderstanding has been elusive.Many experimental groups have developed rudimentary (but very promising)DNA based molecular machines. Modeling of these machines is in a preliminarystage. Exploratory research in modeling these machines is likely tolead to interesting and challenging algorithmic questions.Broad impact: Error correction at the nano scale will facilitate sophisticatedtasks such as counting, growing crystals of pre-specified sizes (nolarger, no smaller), shape recognition etc. with great precision using inherentlyerror-prone DNA self-assembly (or other technologies). This would bea new engineering primitive, somewhat like the engine and the semiconductor,with important immediate as well as unforeseen uses. Also, molecularmachines may act as sensors, signal carriers, actuators, or drug deliverymechanisms. Undoubtedly, much of the hard work in achieving these goalswill be done (and is being done) by experimentalists. But the PI believesthat algorithmic techniques will also play an important supporting role.The PI will organize an informal reading seminar where students willexplore this area in depth. The PI hopes that this seminar will provide avaluable educational experience. The PI also plans to write an article in abook intended for scientifically literate readers who are not experts in thisfield; the article will highlight algorithmic issues at the nano scale.1