崔建中

(淮南联合大学 实训中心，安徽 淮南 232038)

0 引言

逻辑门是集成电路上的基本组件，是构建计算机的基础。逻辑门可以组合成逻辑电路进行复杂的逻辑运算。

摩尔定律指出集成电路上可容纳的晶体管数目约每隔18 个月便会增加一倍，性能也将提升一倍。由于一方面DNA 分子海量信息的存储能力；另一方面，两条单链DNA 可以依据简单的碱基互补配对规则形成稳定的双链DNA，且反应可以高度并行地进行。上述特点使得DNA 计算很有可能取代硅介质计算机并实现计算的途径。

本方从DNA 计算、逻辑门在DNA 计算中的生物实现两个方面做一下简要的介绍，文中阐述了Winfree 等人的最新研究成果，并对他们的方法应用于大规律逻辑运算时的优、缺点进行了讨论。

1 DNA 计算

1994年，美国加利福尼亚大学的Adleman 博士提出利用DNA（脱氧核糖核酸）对一个图论中的NP-完全问题-有向图的Hamilton 路问题进行编码，借助连接、变性、复性、PCR 扩增、电泳等生物操作可以求解出这一问题[1]。

经过二十多年的发展，关于DNA 计算领域的研究成果非常丰富。特别是近年来DNA 自组装的研究引起了学者们的兴趣，并取得了很多的研究成果。DNA 自组装是指以DNA 分子为基本材料，通过分子间的碱基氢键、范德华力等微作用力自发缔结成结构稳定的聚集体或超分子结构。1963年，Wang[2]提出了“Wang Tile”的概念，并指出Wang Tile 可以通过自组装过程，在二维平面形成周期性格局，而且该过程被证明具有图灵机等价的计算能力，然而直至20 世纪90年代，DNA自组装技术才变为现实。……