传递闭包问题的DNA计算

摘要：DNA计算是计算机科学和分子生物学相互结合，相互渗透而产生的新计算模式，在解决一些复杂的问题上，尤其是NP—完全问题上具有一定的优势，提供了新的解决途径。首先介绍DNA计算的基本原理，其次详细介绍传递闭包问题的DNA算法 ，对图中顶点用DNA片段进行编码，将这些DNA片段放入溶液中进行生化反应，通过基本的生物操作及生物酶完成解的产生，并最终筛选出传递闭包问题的所有解。最后介绍DNA计算的研究和一些尚待解决的问题。

关键词：DNA计算 ；传递闭包； NP完全问题

中图分类号：TP30 文献标识码：A文章编号：1009-3044（2012）28-6771-02

1 概述

计算机技术被认为是20世纪三大科学革命之一，电子计算机为人类社会的发展起到了巨大的促进作用。然而，随着科学技术的不断发展，出现了许多新领域中的复杂难解问题，这些问题用普通的电子计算机很难解决，其原因就是电子计算机的运算速度慢和存储空间小。因此，以DNA计算模型为背景而产生的所谓新一代计算机，即DNA计算机应运而生。DNA计算在近几年来倍受科学界的关注，尤其是在解决NP—完全问题上提供了新的方法。

自从Adleman 博士于1994年开创性地用DNA计算实现了7个顶点的有向图的哈密顿问题以来，国际上对DNA计算引起了巨大的轰动。离散数学是数学的一个分支，在离散数学应用的领域中，主要集中在对传递闭包问题，图着色问题和主范式问题的求解上。自从Watson和Crick在1953年发现了DNA之后，人们发现和发展了许多操作DNA的方法，这些发现和发展不仅使我们能够利用DNA作为信息载体，而且使我们能够通过分子生物技术对DNA进行可空操作以实现某些算法。

2 DNA计算的基本原理

DNA计算的基本思想是：利用DNA特殊的双螺旋结构和碱基互补配对规律进行信息编码，把要运算的对象映射成DNA分子键，在生物酶的作用下，生成各种数据池（data pool），然后按照一定的规则将原始问题的数据运算高度并行地映射成DNA分子键的可控的生化过程。最后，利用分子生物技术如聚合链反应PCR，超声波降解，亲和层析，克隆，诱变，分子纯化，电池，磁珠分离等，检测所需要的运算结果。DNA计算的核心问题是将经过编码的DNA链作为输入，在试管内或其他载体上经过一定时间完成控制的生物化学反应，以此来完成运算，使得从反应后的产物中能够得到全部的解空间。

DNA计算的本质就是利用大量不同的核酸分子杂交，产生类似于某种数学过程的一种组合的结果，并根据限定条件对其进行筛选。对DNA序可进行的操作是用生物酶来完成的。

3 传递闭包的DNA算法

3.1 传递闭包问题

文中我们考虑的图是有向简单图。形式上，传递闭包求解的问题是这样的：给定有向图G=（V，E），设R是定义在非空集合A上的一个二元关系，R的传递闭包是A上的关系t（R），使得t（R）满足以下条件：（1）[tR]具有传递性 （2）[R⊆tR]（3）对A上任何包含R的传递关系R，恒有[R⊆tR]。由定义可知，实际上就是找这样的[tR]，向集合R中添加最少的元素（序偶）并使得R具有传递性的集合[tR]。

下面讨论求解传递闭包问题的DNA算法。根据传递闭包的定义，我们可以将传递闭包的算法简单概括如下：

3.2 DNA算法的生物实现

如图1所示，

在非空集合[A=V1，V2，V3，V4]上定义了一个二元关系R，并且[R=V1，V2，V1，V3，V2，V3，V3，V4]。那么求解关系R的传递闭包[tR]的生物实现如下：

步骤 1 假定我们可获得长20个核苷酸的随机单链DNA序列， [V]代表DNA串[V]的逆补。先将图中各个顶点[Vi]用一个任意的20个碱基单链DNA片段来代替，[Vij]弧分别用[Vi]顶点的后10个碱基的互补碱基和[Vj]顶点的前10个碱基的互补碱基构成的DNA片段来代替。在适当的温度下，[Waston-Crick]补很容易产生，所以可用[Vi]及[Vi]方便的构成了路径[Vki]和[Vij]的连接。通过连接酶反应，我们将获得许多随机路径。

假定所选代表顶点1，3，4的序列如下：

可通过以上序列构造边[V13]和[V34]，得[V13=CATATAGGCTCGATAAGCTC]

以此类推，可得到图中随机路径编码的DNA分子，即初始数据池。

4 结束语

传递闭包问题是离散数学中的一个重要内容，因此，学者们都在寻求其解法。传统的算法有[Warshall]算法，平方法，列标号法

等。这些方法在解决传递闭包问题时都有缺陷和不足，比如计算量大，运算速度慢，结果不够精确等，而用DNA方法来解决此类问题就比较方便和简单。当然，DNA计算在数学应用领域中还存在一些尚待解决的问题，比如编码问题等。

由于DNA分子计算尚处于胚胎发育时期，在一定程度上还不够完善。尽管如此，目前国际上对DNA分子的前景信心十足，对于目前存在的种种不足，人们正在努力完善。

参考文献：

[1] Adleman L M.Molecular Computation of Solutions to Combinatorial problem[J]Science，1994：266a（11）：1021-1023.

[2] Xu Jin，ZHANG Lei.DNA Computer Principle，Advances and Difficulties（II）[J].ChinesenJournal of Computers

[3] Lipton R J.DNA Solution of Computation Problem[J].Science，1995.

[4] Sakamoto K，Gouzu H，Komiya Ketal.Molecular computation by DNA hairpin formation[J].Scinence，2000.

[5] 殷志祥，张家秀.图论中的DNA计算模型[J].系统工程与电子技术，2007（7）.

[6] 殷志祥.图与组合优化中的DNA计算[M].北京：科学技术出版社，2004.

[7] 张鸿雁.基于DNA计算的聚类算法研究[D].济南：山东师范大学，2011.

[8] 朱越.基于DNA的连续优化算法[J].计算机工程与应用，2011，47（22）：48-52.

[9] 殷脂，叶春明，温蜜.最小自由能约束的DNA编码设计研究[J].计算机工程与应用，2010，46（12）：25-27.

[10] 张凯，耿修堂，肖建华，等.DNA计算中核酸序列设计方法比较研究[J].计算机学报，2008，31（12）：2150-2154.

推荐访问： 传递 计算 DNA

---