SGER: Algorithmic Issues at the Nano Scale

自组装是一个小的“组件”遵循简单的组合规则形成复杂结构的过程。DNA自组装被广泛认为是纳米技术、纳米机器人和分子计算的重要工具。特别是DNA自组装，以及一般的纳米技术，提供了重大的算法挑战。本项目将在这一领域探索两个令人兴奋的方向：1.在纳米尺度上的误差校正。2.分子机器的模型和算法。智力上的优点：在纳米尺度上纠错所需要的工具和技术与纠错码所需要的工具和技术明显不同。例如，错误和纠错机制受到纳米尺度下热力学定律的约束，以及纠正错误所需的任何“计算”必须使用相同的潜在错误倾向物理机制进行的约束。虽然在某些情况下特定的纠错机制现在是已知的，但普遍的理解一直是难以捉摸的。许多实验小组已经开发出基本的（但非常有前途的）基于DNA的分子机器。对这些机器的建模还处于探索阶段。广泛的影响：纳米级的纠错将有助于完成复杂的任务，如计数，生长预定尺寸的晶体（不大，不小），形状识别等，使用固有的易错DNA自组装（或其他技术）具有很高的精度。这将是一个新的工程基础，有点像发动机和半导体，具有重要的直接和不可预见的用途。此外，分子机器可以作为传感器、信号载体、致动器或药物输送机制。毫无疑问，实现这些目标的大部分艰苦工作将由实验者完成（并且正在完成）。但PI相信算法技术也将扮演重要的辅助角色。PI将组织一个非正式的阅读研讨会，学生们将深入探索这一领域。PI希望这次研讨会将提供宝贵的教育经验。PI还计划在书中写一篇文章，面向那些不是该领域专家的科学素养读者;这篇文章将强调纳米尺度上的算法问题。

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