基于分治的子集积问题DNA计算机算法

基于分治的子集积问题DNA计算机算法

0　引言

分治法是一种较为传统的算法，这种算法在中国流行了许多年，时至今日这种算法依然被很多专业人士所运用。而DNA算法是近些年才在中国国内兴起的。尽管DNA算法在国内发展的时间还很短暂，但因为DNA算法有着巨大的优势，所以DNA算法越来越受到专业人士的青睐。本文将把这两种算法综合运用，从而来解答子集积的问题。

1　DNA计算、分治法同时用于子集积问题中的现实意义

分治法通常包含三个步骤：第一个步骤是把需要解答的问题看作是母问题，把母问题分解成一个个规模较小的子问题，第二个步骤是把小规模的子问题一个个解决掉，第三个步骤是把已经解决了的所有子问题统统合并起来，最后得出母问题的答案。而DNA算法的本质是：由于DNA能很好地做到并行计算，所以把DNA工具当成是计算的工具，充分借助DNA的运行能力来解决一些问题。目前，分治法被当作是传统算法，DNA这种算法被当成是现代算法，而本文就是要把这两种算法结合从而诞生一种全新的算法，并将其用于子集积问题的实际解答中。

2　阿德尔曼—立顿模型的基本内容

现实中，DNA计算时对阿德尔曼—立顿模型的利用率是最高的。所以，本文先来介绍下阿德尔曼—立顿这种模型的基本内容。这种模型是由生物学家立顿结合生物学家阿德尔曼的研究成果而提出的。生物学家立顿认为阿德尔曼—立顿模型包括6个基本步骤。

第一个步骤简称为抽取步骤。假定有一个试管，该试管用字母Q表示，还有一个DNA单链，该DNA单链用字母R表示。那么抽取步骤有-（Q,R）和+（Q,R）两种。假如某DNA链中包含了R单链，那么这个DNA链便属于+（Q,R）中。假如某DNA链中并不包含R单链，那么这个DNA链便属于-（Q,R）中。

第二个步骤简称为合并步骤。假定有两个不同的试管，这两个不同的试管分别用字母Q1和Q2来表示。合并步骤是指：把Q1试管和Q2试管中的内容合并起来放到同一根试管中，同时要保证无论Q1还是Q2中的分子链都不能有任何改变。

第三个步骤简称为检测步骤[3]。假定有一个试管，该试管用字母Q表示。Q试管中有一个及以上的DNA链，那么结果便返回英文YES，否则结果便返回英文NO。

第四个步骤简称为复制步骤。假定有一个试管，该试管用字母Q表示。对Q试管做2次复制的基本操作，则将产生Q1和Q2，同时Q试管被清空。

第五个步骤简称为添加步骤。假定有一个试管，该试管用字母Q表示，还有一个DNA单链，该DNA单链用字母R表示。添加步骤是指：把R单链分别添加到Q试管中每个DNA链的尾部位置。

第六个步骤简称为读取步骤。假定有一个试管，该试管用字母Q表示。读取步骤是指：把Q试管中全部的DNA链进行0/1信息的读取。

3　基于分治的子集积问题DNA计算机算法

3.1DNA计算用于子集积问题中的计算框架

本文认为DNA计算、分治法同时用于子集积问题中的计算框架包含了如下的步骤：（1）假定有两根不同的试管，这两根不同试管分别用字母Q1和Q2来表示。假定有两个子集积，这两个子集积分别用字母V1和V2来表示。第一步是把V1、V2中的全部子集以DNA链的方式分别表示于Q1、Q2试管中。QL用以表示DNA链的基本形式[1]。（2）当V1、V2中的全部子集以DNA链的方式分别表示于Q1、Q2试管中之后，对Q1和Q2试管中的全部DNA链做乘法运算，得到的便是V1和V2每个子集对应的子集积。（3）对Q1中的全部DNA链做除法运算，得到的便是Q1中全部子集积跟L商的全部DNA链。（4）借助并行数据的常用搜索器（N位）进行搜索，搜索的目的是比较Q1和Q2中的全部DNA链。找出Q1中商以及Q2中积完全相同的链，这些完全相同的链便是整个子集积问题的最后答案。

3.2DNA计算用于子集积问题中的子算法设计

本文认为子算法的基本设计思路共有以下几个步骤：

（1）假定有一个试管，该试管用字母Q表示。利用上述谈到的抽取步骤对Q试管做两次抽取的操作，得出Q1和Q2。Q1中商信息的首位用字母Cn,1来表示，那么Cn,1（Qn，1）的值为1。Q2中商信息的首位也用字母Cn,1来表示，那么Cn,1（Qn，1）的值为0。把Q1中商信息的前面5位（32种）用不同试管分别装取。

（2）在第2a步骤中，第二位信息共有4种可能，第三位信息共有8种可能，第四位信息共有16种可能，第五位信息共有32种可能。这几位信息的不同可能用不同试管来分别装取。执行2a步骤的时候，一共需要做两次执行操作。第一次执行的时候，设定j的值为2，k的值为3。第二次执行的时候，设定j的值为2，k的值为5。

（3）在第2b步骤中的首次执行中，再对Q试管做两次抽取的操作，得出Q3和Q4。Q3中商信息的首位用字母Cn,1来表示，那么Cn,1（Qn，1）的值为1，Cn,2（Qn，2）的值也为1。Q4中商信息的首位也用字母Cn,1来表示，那么Cn,1（Qn，1）的值为1，Cn,2（Qn，2）的值为0。

（4）在第2b步骤中的二次执行中，再对Q试管做两次抽取的操作从而得出Q5和Q6。Q5中商信息的首位用字母Cn,1来表示，那么Cn,1（Qn，1）的值为0，Cn,2（Qn，2）的值也为1。Q6中商信息的首位也用字母Cn,1来表示，那么Cn,1（Qn，1）的值为0，Cn,2（Qn，2）的值为0。

（5）当上述4个步骤都完整执行以后，那么j=2这个循环的全过程便圆满结束。Q3、Q4、Q5、Q6试管分别把试管中的前面两位信息存储起来。然后，再执行j的值分别取3、取4、取5时的操作，这样便能获得前五位的全部信息，而前五位的全部信息一共是32种。

（6）在上面5个步骤完毕之后，便能分别获得前五位的和信息以及差信息（32种）。第6个步骤是对这32种情况进行具体的比较。第6个步骤具体分成6a、6b、6c三种步骤。在第6a步骤中，主要判定Q131、Q231两者是不是都存在DNA链。假如两者都有DNA链的存在，那么在第6b的步骤中便把Q131、Q231两者分别读出。这时，到6c步骤的时候便结束循环。如若不然，则反复做循环的有关操作，一直到k的值取62为止。

3.3DNA计算、分治法同时用于子集积问题中的具体计算方式

把DNA计算、分治法同时用于子集积问题中的具体计算共有以下几个步骤：

（1）将Init（Q1，☒q）和Init（Q2，☒q）分别执行，同时把V1、V2中的全部子集以DNA链的方式分别表示于Q1、Q2试管中。

（2）把V1、V2中的全部子集以DNA链的方式按照value（Q1，☒q,n）、value（Q2，☒q,n）的原则表示出来。

（3）对V2中的全部DNA链做乘法运算以求得子集的和。把QL也用DNA链的基本形式来表示。

（4）求出Q跟L间子集积的商。

（5）找出Q1中商以及Q2中积完全相同的链，这些完全相同的链便是整个子集积问题的最后答案。

以上5个步骤的解读：第一步具体做了三个方面的操作：一是q个复制；二是2q个添加；三是q个合并。第二步也做了三个方面的操作：一是2nq个添加；二是q个抽取；三是q个合并。第三步做的操作有：n☒q☒O个添加、n☒q☒O个添加、n☒q☒O合并。第四步做的操作是n个添加。第五步做的操作有：n☒q☒O个添加、n☒q☒O个添加、n☒q☒O合并。所以，最终生物操作的总数量表示为：n☒q☒O+LOn。

现实中，由于算法总共用到的试管数量是62，所以试管数可以用O（1）来表示。链的最长长度用n☒q☒O来表示。算法中，集合V共计q个元素，由于引入了分治法，所以集合V被分成了两个☒q的集合V1与集合V2。在Init（Q1，☒q）和Init（Q2，☒q）的执行中，集合V1、V2分别生成了数量为 2q/2的DNA链。而在此后的运算中，便再也没有其它DNA链生成。所以，DNA链数量为O（2q/2）[2]。

4　结束语

综上，本文首先阐述了DNA计算、分治法同时用于子集积问题中的现实意义。其次，本文简要阐述了DNA算法中最流行的模型（阿德尔曼—立顿模型）的基本内容。再次，本文较为细致地阐述了在解答子集积问题时把DNA算法、分治法结合使用的具体算法。

参考文献：

[1]潘果，李肯立，刘万方等.基于分治法的子集积问题DNA计算机算法研究[J].计算机工程与科学，2011（20）：23-36.

[2]李肯立，姚凤娟，李仁发等.基于分治法的背包问题DNA计算机算法研究[J].计算机研究与发展，2011（10）：3-10.

[3]李肯立，徐进，李仁发等.基于分治法的子集问题DNA计算机算法研究[J].计算机学报，2013（15）：22-26.

2014年院级科研项目（Wzywt201421/23）。

项目基金：安徽省高等学校质量工程教学研究项目（2013jyxm319）；

作者简介：吕嫄（1983-），女，安徽芜湖人，讲师，主要从事数据挖掘方向研究。