EAGER: Algorithmic aspects of molecular circuits and molecular machines

项目概要提案#:0947670PI: Ashish goel我们习惯于将DNA视为一种生物分子。然而，DNA，它的近亲RNA，以及其他相关的分子，如酶，也是工程的基石。把它们想象成？组合积木吗?它们不仅通过力学和几何，而且通过印在它们上面的化学序列，组合在一起并相互作用。这有许多革命性的潜在应用。这也提出了许多数学和算法问题，这些问题本身都很有趣，也为设计有用的实验技术提供了一个框架。PI建议在新兴领域进行研究？分子算法?也就是说，要在分子上实现的算法。这项研究将从分子机器和分子电路两大方向进行。这两个领域在主题上和技术上都有联系。我们将不断咨询本领域的实践者，使本研究的结果既新颖又有用。智力优势：分子算法需要的工具和技术与传统算法有很大的不同。我们不能假设构建块，如存储器，驱动器，传感器，晶体管，处理器等；更确切地说，这些通常是我们试图用更基本的原语来设计的东西，比如DNA杂交、酶促反应和迁移。因此，分子算法的进步可能需要新颖的数学技术，这将丰富编码理论、组合算法和概率分析的学科。广泛影响：分子机器已被提议作为传感器、致动器和药物传递机制。分子电路具有精细控制其他分子过程的潜力。发展这些想法的大部分艰苦工作是由实验家完成的。然而，像我们提议开发的理论工具在实现这一领域的全部潜力和决定最有希望的实验方向方面也发挥着重要作用。此外，分子算法可以在纳米尺度上促进复杂的任务，如计数、形状识别、精确控制晶体生长等。PI已经开发了一门分子算法课程，他将每两年更新并教授这门课程。此外，许多研究生将在这一重要领域获得宝贵的研究经验。

Project SummaryProposal #: 0947670PI: Ashish GoelWe are used to thinking of DNA as a biological molecule. However, DNA, its cousin the RNA, and other associated molecules such as enzymes, are also engineering building blocks. Think of them as ?combinatorial Legos? which fit together and inter-operate not just by mechanics and geometry but also using the chemical sequence imprinted on them. This has many revolutionary potential applications. This also poses many mathematical and algorithmic questions which are both interesting in their own right and also provide a framework to devise useful experimental techniques. The PI proposes to conduct research in the emerging field of ?molecular algorithms?, i.e., algorithms which are meant to be implemented on molecules. This study will proceed in two broad directions: molecular machines and molecular circuits. The two areas are linked both thematically and in terms of techniques. We will constantly consult with practitioners in this field, so that the results of this research are both novel and useful.Intellectual merit: Molecular algorithms require tools and techniques that are considerably different from traditional algorithms. We can not assume building blocks such as memories, actuators, sensors, transistors, processors etc; rather, these are often the things we are trying to devise using more basic primitives such as DNA hybridization, enzymatic reactions, and migration. Consequently, advances in molecular algorithms are likely to require novel mathematical techniques that will enrich the disciplines of coding theory, combinatorial algorithms, and probabilistic analysis.Broad impact: Molecular machines have been proposed as sensors, actuators, and drug delivery mechanisms. Molecular circuits have the potential to finely control other molecular processes. Much of the hard work in developing these ideas is being done by experimentalists. However, theoretical tools such as the one we propose to develop also have an important role to play in realizing the full potential of this area and in deciding upon the most promising experimental directions. In addition, molecular algorithms could facilitate sophisticated tasks such as counting, shape recognition, precisely controlled crystal growth etc. at nano-scales.The PI has developed a class in molecular algorithms which he will update and teach bi-annually. Also, many graduate students will receive valuable research experience in this important area.