DNA Computation on Surfaces

表面 DNA 计算

• 批准号: 9613799
• 负责人: Max Lagally
• 金额: $ 90万
• 依托单位: University of Wisconsin-Madison
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1996
• 资助国家: 美国
• 起止时间: 1996-09-01 至 1999-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9613799&HistoricalAwards=false
• 关键词: DNA; Computation; Surfaces

(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.***

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