DNA Computation on Surfaces

(1)这个多学科项目致力于通过操纵表面上的DNA链，在分子水平上发展计算。Adleman的一项基于dna计算的实验演示(a)改变了人们对计算是什么的看法，(b)在分子水平上提供了前所未有的计算能力的潜力，(c)在化学、计算机科学和材料科学中提出了根本性的新研究问题。这个项目代表了对这些问题的一致攻击，涉及化学家、材料科学家和计算机科学家之间的密切合作。(2)本研究将有助于回答dna计算的两个主要问题。首先，分子水平上的计算是否有潜力提供比当前技术可预见的推断大几个数量级的计算能力？第二，这种类型的计算是否适合解决np困难问题（远远超出当前技术极限的问题）？(3)巨大计算能力的潜力在于利用DNA链对信息进行编码，并以大规模并行的方式对这些链进行操作，涉及多达2^70（2的70次方）条不同的链。这个项目的前提是，表面化学是达到这个规模的关键技术。通过这种方法，DNA链被固定在表面上，因此在操纵DNA的化学过程中，比通过Adleman的基于试管的方法可以实现的控制程度要大得多。虽然基于表面的化学是最近组合化学进展的基础，但该项目是第一个充分利用基于表面的DNA链操作来进行DNA计算的项目。(4)扩大当前的表面化学以达到基于dna计算的要求，需要在材料科学和化学的界面上进行高质量的研究。纳米级形貌和表面化学组成的改进是确保获得高密度信息和进行可靠化学操作的关键。良好的表面附着化学和化学“操作”或酶促过程的控制也得到了广泛的发展。这个项目将在表面化学领域取得重大进展，并为预测基于表面的DNA计算的极限提供坚实的基础。(5)基于dna的计算的最终目标是对NPhard问题的最优解进行大规模并行搜索。然而，基于dna的计算与传统技术之间的差异要求为这种范式开发全新的算法。调节潜在的前所未有的并行性（多达2^70个并发操作）是非常缓慢和容易出错的操作本身的本质。研究了NPhard问题解空间生成和搜索的新策略。这些策略体现了合理的算法原则，可以应用于一系列问题。采用分析和仿真相结合的方法，在选定的应用中测试了这些策略的有效性。这项工作提供了解决NPhard问题的新方法，这些问题虽然是为假设的基于DNA的计算机设计的，但对于大规模并行计算范例（除了这里研究的基于DNA的范例）来说是有价值的。(6)因此，这个综合性的项目将从化学和算法的角度深入了解基于dna的计算的潜力和局限性

(1) This multi-disciplinary project concentrates on developing computation at the molecular level, via manipulation of DNA strands on surfaces. An experimental demonstration of DNA-based computation by Adleman(a) has changed the view of what computation is, (b) offers the potential for unprecedented computing power at the molecular level, and (c) raises fundamentally new research problems in chemistry, computer science, and material science. This project represents a concerted attack on these problems which involves close collaboration between chemists, material scientists, and computer scientists.(2) This research will help answer two major questions on DNAcomputation. First, does computation at the molecular level have the potential to provide computing power that is orders of magnitude greater than foreseeable extrapolations of current technology? Second, is this type of computation suited to solving NP-hard problems (problems that are well beyond the limits of current technology?(3) The potential for huge computing power rests on the use of DNA strands to encode information and the manipulation of these strands in a massively parallel fashion, involving as many as 2^70 (2 to the 70th power) distinct strands. The premise of this project is that surface-based chemistry is a critical technology in approaching this scale. With this approach, DNA strands are immobilized on a surface, thus allowing a much greater degree of control in chemical processes that manipulate the DNA than is achievable via the test tube based methodology of Adleman. While surfacebased chemistry is the basis for recent strides in combinatorial chemistry, this project is the FIRST to fully exploit surface-based manipulation of DNA strands for the purposes of DNA computation.(4) Scaling up current surface chemistry to approach the requirements of DNA-based computation requires high-quality research at the interface of materials science and chemistry. Improvements in the nanoscale morph ology and chemical makeup of the surface is key to ensuring that a high density of information can be obtained and reliable chemical manipulations performed. Good surface attachment chemistry and control of chemical ``operations'' or enzymatic processes are also extensively developed. This project should result in significant advances in the state of- the-art in surface chemistry and should provide a solid basis for predicting the limits of surfacebased DNA computation.(5) An eventual goal of DNA-based computation is to perform massivelyparallel searches for optimal solutions of NPhard problems. However, the differences between DNAbased computation and conventional technology require that radically new algorithms be developed for this paradigm. Tempering the potential for unprecedented parallelism (up to 2^70 simultaneous operations) is extremely slow and errorprone nature of the operations themselves. Novel strategies for generating and searching solution spaces for NPhard problems are investigated. These strategies embody sound algorithmic principles that can be applied to a range of problems. Using a combination of analysis and simulations, the effectiveness of these strategies are tested on selected applications. This work provides new ways of attacking NPhard problems that, while designed for a hypothetical DNA based computer, are valuable for massively parallel computing paradigms, other than the DNA-based paradigm studied here.(6) Thus this comprehensive program will provide a deep understanding of the potential and limitations of DNAbased computation, from both the chemical and algorithmic viewpoints.***