生物DNA计算机

3.0 2025-01-06 8 4 25.19KB 7 页 10龙币

侵权投诉

No.1 Fugaku( 富岳 ) ，日本制造商：富士通，处理器核芯：7630848 个；峰值(Rmax)：

442010 TFlop/s，

No.2 Summit（美国），美国制造商：IBM，处理器核芯：2414592 个；峰值(Rmax)：

148600 TFlop/s

No.3 Sierra（美国），美国制造商：IBM，处理器核芯：1572480 个；峰值(Rmax)：

94640 TFlop/s

No.4 神威太湖之光（Sunway TaihuLight）中国，中国制造商：国家并行计算

机工程技术研究中心，处理器核芯：10649600 个；峰值(Rmax)：93015 TFlop/s

No.5 Selene （美国），美国制造商：Nvidia，处理器核芯：555520 个；峰值(Rmax)：

63460 TFlop/s，No.6 TH—2 天河二号（中国），中国制造商：国防科大，处理器核芯：

4981760 个；峰值(Rmax)：61445 TFlop/s

1 DNA 计算的理论、特点和问题

1994 年11 月美国计算机科学家 L．阿德勒曼（L．Adleman）在《科学》

上公布了 DNA 计算机的理论，并成功的运用 DNA 计算机解决了一个有向哈密

尔顿路径问题[1]。这一成果迅速在国际上产生了巨大反响[2]，同时也引起了

国内学者的关注[3]。

一些人相信，DNA 计算蕴含的理念可使计算的方式产生“进化”。另一些人则

看到 DNA 计算的理念将有助于揭示生命的本质与演化。总之，这一全新的计算

理论，将在数学与生命科学中产生极其深远而广大的影响。同时它也提出了一

系列值得我们深思的哲学性问题。

DNA 计算机目前尚处在理论研究阶段，一旦它在实用意义上获得成功，DNA

计算将彻底改变计算机硬件的性质。

在过去的半个世纪里，计算机完全就是物理芯片的同义词。但阿德勒曼 DNA

计算机则是一种化学反应计算机[4]。它的基本构想是：以 DNA 碱基序列作为

信息编码的载体，利用现代分子生物学技术，在试管内控制酶作用下的 DNA 序

列反应，作为实现运算的过程；这样，以反应前 DNA 序列作为输入的数据，反

应后的 DNA 序列作为运算的结果。

阿德勒曼具体应用哈密尔顿有向图这个经典 NPC 问题，详细描述了他的理论。

DNA 计算机的提出，产生于这样一个发现，即生物与数学的相似性：①生物体

异常复杂的结构是对由 DNA 序列表示的初始信息执行简单操作（复制、剪接）

的结果；②可计算函数 f（w）的结果可以通过在 w上执行一系列基本的简单函

数而获得。

阿德勒曼不仅意识到这两个过程的相似性，而且意识到可以利用生物过程来

模拟数学过程，更确切地说是，DNA 串可用于表示信息，酶可用于模拟简单的

计算。这是因为：① DNA 是由称作核苷酸的一些单元组成，这些核苷酸随着附

在其上的化学组或基的不同而不同。共有四种基：腺瞟吟、鸟瞟吟、胞嘧啶和

胸腺嘧啶，分别用A、G、C、T表示。

一些单个的核苷酸顺序连在一起形成DNA 链。单链DNA 可以看作是由符合

A、G、C、T组成的字符串。从数学上讲，这意味着我们可以用一个含有四个

字符的字符集∑＝A、G、C、T来为信息编码（电子计算机仅使用 0和1这两

个数字）。② DNA 序列上的一些简单操作需要酶的协助，不同的酶发挥不同的

作用。

起作用的有四种酶：a．限制性内切酶，主要功能是切开包含限制性位点的双

链DNA；b．DNA 连接酶，它主要是把一个 DNA 链的端点同另一个链连接在

一起；c．DNA 聚合酶，它的功能包括 DNA 的复制与促进DNA 的合成；d．

外切酶，它可以有选择地破坏双链或单链DNA 分子。

正是基于这四种酶的协作实现了 DNA 计算。

自阿德勒曼用 DNA 计算机解决了哈密尔顿有向图问题，随后很快便有人用

DNA 计算机相继解决了其他一些疑难问题（NPC 完全问题），如可满足性问

题等。与电子计算机相比，DNA 计算机有明显的优势。不过，这些还仅仅是利

用分子技术解决的几个特定问题，是为解决特定问题而进行的一次性实验。

DNA 计算机还没有一个固定的程式。由于问题的多样性导致所采用的分子生

物学技术的多样性，具体问题需要设计具体的实验方案。于是，便引出了两个

根本性的问题，阿德勒曼最早就意识到了它们：① DNA 计算机可以解决哪些问

题？确切地说，DNA 计算机是完备的吗？即通过操纵DNA 能完成所有的（图

灵机）可计算函数吗？②是否可设计出可编程序的 DNA 计算机？即是否存在类

似于电子计算机的通用计算模型——图灵机——那样的通用 DNA 系统（模型）？

目前，人们正处在对这两个根本性问题的研究过程之中。

在我们看来，这就类似于在电子计算机诞生之前的 20 世纪三四十年代——理

论计算机的研究阶段。如今，已经提出了多种DNA 计算模型，但各有千秋，公

认的DNA 计算机的“图灵机”还没有诞生。相对而言，一种被称为“剪接系统”的

DNA 计算机模型较为成功[5]。



由于 DNA 链可以比作在四字符集上的串，为 DNA 计算建模的自然方式就是

利用专门处理字符和字符串的形式语言理论。建模的关键就是要将实际的 DNA

重组抽象为数学上的剪接操作。实际的 DNA 重组，就是在前面所提到的四种

“工具酶”的作用下，对 DNA 链的切割和粘贴的组合过程。

其数学抽象称为剪接操作。大体可做如下描述：给定字符集∑（其元素为符

号）及其上的两个字符串x、y，利用剪接规则r剪接 x和y的过程可以分为：

①在由剪接规则r决定的位置上切割x和y；②分别将结果中 x的前段和 y的后

段、y的前段和 x的后段连在一起。∑ 的剪接规则 r是形如 α1#β1$α2#β2

的词，其中 α1、β1、α2、β2 是∑的串，＃和$是∑外的标记符。

我们称 z和w是根据剪接规则r＝α1#β1$α2#β2 剪接 x和y的结果，当且

仅当存在∑上的 x1、xƇ、y2、yƈ 使得

x=x1α1β1xƇ, y＝y2α2β2yƈ

且 z=x1α1β2yƈ, w=y2α2β1xƇ

并记作（x，y） →（z，w）。

α1β1 和α2β2 这两个串称为剪接位点；x和y称为剪接项。剪接规则r决定

了切割的位点和位置：第一项在α1 和β1 之间，第二项在α2 和β2 之间。值

得注意的是位点α1β1 和α2β2 会分别在x和y中出现多次，如果这样，选择

哪一个位点是不确定的。结果会造成对 x和y剪接的结果是（z，w）的一个集

合。



将剪接操作当作基本工具来构建一种生成机制，便形成了剪接系统。给定一

个字符串集A,A∑*,∑*为字符集∑上由连接操作生成的字符串的集合（∑*中的

元素为串），以及一个剪接现则集R（r∈R∑*＃∑*$∑*＃∑*），由此所生成

的东西是由如下方法得到的串组成；从集 A开始，在 A和已获得的串上重复使

用剪接规则。

另外，应该说明一点，通常剪接 x和y得到 z和w后，仍可以将 x和y当作

剪接项，与此相似，对新生成的 z和x也没有数量上的限制。但对某些串仅可

使用有限次。故在数学上不用集合来表示剪接项，而用多重集——在每个时刻

都应当记录每个串可用的个数。至此，可以给出剪接系统的一个简洁而又严格

的定义：剪接系统是一个四元组 r＝（∑、T、A、R），其中∑是一个字符集，

T ∑是终结字符集，A是∑*上的多重集，R是剪接规则的集合。



定义了 DNA 计算的数学模型后，便可以来回答前面提出的 DNA 计算的完备性

与通用性问题。在计算机科学中，众所周知的丘奇一图灵论点深刻地刻画了任

何实际计算机的计算能力——任何可计算函数都是可由图灵机计算的函数（一

般递归函数）。现已证明：剪接系统是计算完备的，即任何可计算函数都可以

用剪接系统来计算。

换句话说就是，任何图灵机可计算的函数都可以由这种 DNA 计算模型来计算。

反之亦然。这就回答了DNA 计算机可以解决哪些问题——全部图灵机可计算问

题。

对于第二个问题——是否存在基于剪接的可编程计算机——也有了肯定的答

案：对每个给定的字符集 T，都存在一个剪接系统，其公理集和规则集都是有

限的，而且对于以 T为终结字符集的一类系统是通用的。

这就是说，理论上存在一个基于剪接操作的通用可编程的 DNA 计算机。程序

由往通用计算机公理集中添加的字符串组成。程序会有多个，而可利用的公理

集合有无穷多个。这些计算机使用的生物操作只有合成、剪接（切割一连接）

和抽取。

理论上 DNA 计算机具有现代电子计算机同样的计算能力，但它具有的巨大

潜力（功能）却是电子计算机不可比拟的：DNA 计算机运算速度极快，其几天

的运算量就相当于计算机问世以来世界上所有计算机的总运算量；它的贮存容

量非常大，1立方分米的DNA 溶液可以存储 1万亿亿位二进制的数据，超过目

前所有计算机的存储容量；它的能量消耗只有一台普通计算机的十亿分之一。

如此优越的分子计算机当然是激动人心的。然而它离开发、实际应用还有相

当的距离，尚有许多现实的技术性问题需要去解决。如生物操作的困难，有时

轻微的振荡就会使DNA 断裂；有些 DNA 会粘在试管壁、抽筒尖上，从而就在

计算中丢失了。尽管DNA 计算机面对着许许多多的质疑，但它的提出者阿德勒

曼教授依然是极其乐观的：DNA 计算机刚刚提出，尚在胚胎时期，与发展了半

个世纪的电子计算机相比，确实相形见细。

在他看来，提出 DNA 计算机并不就是要与电子计算机竞争。首先，分子计算

的观念拓宽了人们对自然计算现象的理解，特别是生物学中基本算法的理解。

另外，DNA 计算的观念向现有的计算机科学和数学提出了挑战，相信它所蕴涵

的理念可以使计算的方式发生进化。

DNA 计算理论是目前西方发达国家的一个研究热点，有些困难已经通过新

的程序设计技术（无须等待生物技术的发展），采用概率算法及修改数学问题

等传统的解决方案得以解决。

人们大都相信，分子计算的实际应用在未来是可行的。另外，要知道，类似

合成杂交、抽取等所有生物操作的问题，都已被大自然中的生物系统所涉及，

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 龙币 4人已下载

立即下载

摘要：

No.1Fugaku(富岳)，日本制造商：富士通，处理器核芯：7630848个；峰值(Rmax)：442010TFlop/s，No.2Summit（美国），美国制造商：IBM，处理器核芯：2414592个；峰值(Rmax)：148600TFlop/sNo.3Sierra（美国），美国制造商：IBM，处理器核芯：1572480个；峰值(Rmax)：94640TFlop/sNo.4神威太湖之光（SunwayTaihuLight）中国，中国制造商：国家并行计算机工程技术研究中心，处理器核芯：10649600个；峰值(Rmax)：93015TFlop/sNo.5Selene（美国），美国制造商：Nvi...

展开>> 收起<<

生物DNA计算机.docx

共7页,预览3页

还剩页未读，继续阅读

声明：本站是提供个人知识管理的网络存储空间，所有内容均由用户发布，不代表本站观点。请注意甄别内容中的联系方式、诱导购买等信息，谨防诈骗。如发现有害或侵权内容，请点击侵权投诉。

生物DNA计算机

相关推荐

开通VIP享超值会员特权

相关内容

热门标签

举报选择: