SGER: Algorithmic Issues at the Nano Scale

自组装是小的“组件”遵循简单的组合规则形成复杂结构的过程。DNA自组装被广泛认为是纳米技术、纳米机器人和分子计算的关键工具。特别是DNA的自组装，以及纳米技术，在算法上提出了重大的挑战。本项目将探索该领域的两个令人兴奋的方向：1。纳米尺度的误差校正。分子机器的模型和算法。智力优势：纳米级的纠错似乎需要与纠错代码所需的工具和技术有很大不同。例如，误差和误差修正机制受到纳米尺度热力学定律的约束，以及纠正误差所需的任何“计算”必须使用相同的潜在容易出错的物理机制来执行的约束。虽然特定的纠错机制在某些情况下是已知的，但一般的理解是难以捉摸的。许多实验小组已经开发出了基本的（但非常有前途的）基于DNA的分子机器。这些机器的建模还处于初步阶段。对这些机器进行建模的探索性研究可能会导致有趣且具有挑战性的算法问题。广泛影响：纳米尺度的纠错将促进复杂的任务，如计数，生长预先指定尺寸的晶体（不大，不小），形状识别等，使用固有的容易出错的DNA自组装（或其他技术），具有很高的精度。这将是一个新的工程原始，有点像发动机和半导体，具有重要的即时和不可预见的用途。此外，分子机器可以作为传感器、信号载体、致动器或药物输送机制。毫无疑问，实现这些目标的大部分艰苦工作将由实验学家来完成（并且正在完成）。但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