最小连通图问题的DNA表面计算

摘要：现在探讨一种基于芯片的DNA表面计算与电子计算机杂合计算的方法，用于完全问题的计算.该芯片模型通过相应数据库的设计来排布数据，依据不同的问题进行算法设计，在通用的计算芯片表面进行计算反应，计算所得芯片图像，通过专门设计的图像处理计算软件利用计算机进行进一步计算，可以直接得到相应问题的完全解.与以往的DNA计算方法相比，DNA表面计算芯片方法可以将问题的指数运算转化成单项式运算，具有操作简单，不依靠酶反应过程，假阳性率低等优点，并可通过软件与电子计算机相结合，充分发挥DNA 计算的并行计算优势和电子计算机的快速数据处理能力的优势，实现良好的杂合.

关键词：最小连通问题 Adleman-Lipton模型 DNA表面计算

中图分类号：Q811.211 文献标识码：A 文章编号：1007-9416（2013）01-0216-02

目前，DNA计算机相对于电子计算机有两点不足：（1）DNA计算需要以指数级增长的DNA分子数。但事实上如此之大的DNA链数日难以被满足；（2）DNA计算中的平均错误率的存在。比如不正确的杂交、可能发生的寡核苷酸的内部二次结构等都会降低最后结果的可靠性。这两个缺点限制了DNA计算解决大型复杂问题的能力。而DNA表面计算是克服这上述缺点的一种有效办法。它具有方便样本处理、减少了样本处理中的丢失、减少了寡核苷酸间的干扰、方便了实验中每一步中的DNA分子的纯化。通过化学反应用不同的活化试剂在载体表面键合上各种各样的活性基团，以便与配基共价结合，形成具有不同生物特异性的亲和载体，用来固定不同的活性生物分子，如蛋自质、核酸等。通过这种方法固定在载体表面上的DNA分子，具有能够承受在表面上进行的各种加热、清洗及其它生化反应操作的能力。

DNA表面计算方法具体描述如下：

（1）分析完全问题，其完全数据池中的数据转化可用0和1按序表达的方式。

（2）将完全问题的完全数据池转化为序列数据库。个变量的完全问题，其完全数据池包含个数据，每个数据由个变量的0或1两种状态按序组成。将这样的完全数据池制作成阵列数据库，将数据库中的每个阵列由个分单元构成，每个分单元代表完全数据池中的一个数据，即分单元与数据之间可寻址，每个分单元由4个点组成，则整个阵列包含64个取值为0或1的点，则排布为点阵。6个变量的完全问题的阵列由64个分单元构成，每个分单元由6个点组成，则整个阵列包含384个取值为0或1的点，可排布为点阵。

（3）将阵列数据库中的阵列转化为DNA计算芯片。将完全问题阵列中的数据映射为寡核苷酸序列并排布在芯片上，映射关系如下：

1）个变量，每个变量有0和1两种状态，则共有中状态，分别一一对应为种不同的寡核苷酸序列。例如三个变量，则，，，，，六种状态分别一一对应为6种不同的寡核苷酸序列。

2）阵列中每个分单元由个0或1按序构成，则按序索引中规定的对应关系，从而将每个分单元对应于依序排列的个寡核苷酸序列，每个序列成为芯片上的一个点；

（4）根据完全问题的类型，设计相应的DNA芯片计算算法，编写专用的图像处理和后续计算软件。

（5）对给定的芯片算法，将预定合成的有标记的寡核苷酸链混合，与DNA计算芯片发生杂交反应，得到杂交图像。标记物可以是荧光，同位素，化学反应的底物等等，输出的杂交图像可以是荧光图像，同位素图像，化学发光图像等等，也可以是电学信号。

（6）采用针对一类问题算法设计的专用软件处理得到的杂交图像，进行计算，寻址，得到该类问题的全解。

如果一个图中任意两个顶点都可以用一条道路把这两个点连接，则这样的图称为连通图。用电子计算机判断一个图是不是连通的并且把能连接所有顶点并且包含最少边的最小连通图迅速找出来，在顶点和边数比较多的情况下，并不是件容易的事情；这就是一个典型的问题。而现在我们就可以用新的表面计算快速地来解决这个问题。而若是一个图是连通的，必须能满足三点：

（1）对于交于同一点的几条边来说，应保证其中至少一条在连通图中存在，才能使这点在连通图中存在。

（2）对于最小的连通图，不能有环出现，因此要把存在环的情况剔除。

（3）对于个点的图来说，其连通图连接的边数应为条边。因此要选出边为的链。满足以上三点的情况即是无权值的最小连通图问题的解。例如：求下图的最小连通图：城市间可以修建，，，，，，，八条管道，每条管道的总成本一样，问有多少种修建方法使这些城市都连接起来，且管道数目最少（如图1）：

用DNA表面计算芯片计算此问题的模型和步骤如下：

（1）此问题包括8条边，即八个变量。首先定义一种完全数据池的映射策略：1）边分别用，，，，，，，表示。2）定义任一条边有两种赋值，当该条边在图中的边的子集时，则取值为1，否则取值为0。3）将边的子集映射为由1和0组成的数据，顺序依次为。例如：边的集合映射为二进制数101100000。

（2）在以上的映射策略下，8条边的图的完全数据池含个数据。将八条边在阵列中的每个分单元做如下位置对应，以便寻址：

将完全数据池排布为如下阵列：

（3）八个顶点的2种状态采用如下的寡核苷酸序列进行编码（如表1）：

将以上的无权连通图问题编码的寡核苷酸序列依照以上的阵列形式点样排布在芯片上，得到的点阵。采用可以与反应的基底，环氧基等修饰的玻片固定寡核苷酸链。

（4）对无权连通图问题设计相应的DNA芯片计算算法如下：

1）给定已配置好的可明确寻址的寡核苷酸芯片，以交于同一点的两条边，的寡核苷酸链投放在DNA芯片进行杂交，采集到第一幅图像，然后进行解链，再用交于同一点的三条边，，的寡核苷酸链再与DNA芯片进行杂交，再采集到图像2；再进行解链-杂交循环，直到图中所有的交点杂交图像都采集到。然后采用所有边赋值为0的序列进行杂交。

2）给定已配置好的可明确寻址的寡核苷酸芯片，以组成环的三条边，，的寡核苷酸链投放在DNA芯片进行杂交，然后进行解链，在以组成环的三条边，，的寡核苷酸链投放在DNA芯片进行杂交，再进行解链-杂交循环，同样，采集到另外两组环，，以及，，，的杂交图像。

3）对所有的杂交图像利用专用的图像处理计算软件进行处理，对无权连通图问题，专用图像处理计算软件的编程原则为：对前六幅图像，首先依据数据库将图像划分为矩阵方格，然后对每个方格做杂交亮点检测。当方格中我们要求的所在位置至少有一处有亮点时，输出为1。否则输出值为0，这样前六幅杂交图像将抽象为一个由0和1组成的抽象矩阵，依据数据库将图像划分为矩阵方格，然后对每个方格做亮点测试，得到相应的无权连通图问题问题的解，共有23个解，它们分别是：

；；；

；；；

；；；

；；；

；；；

；；；

；；

；；。这与通过电子计算机指数级时间内计算得到的结果完全一致，而利用表面计算则只需要多项式时间内即可。而且这种方法比电子计算机手段更为方便，迅速，简洁，更加清晰明了，具有较好的应用价值。

参考文献

[1]Adleman L.M. Molecular Computation of Solution to Combinatorial Problems.Science， 1994；266；1021--1024.

[2]Lipton R.J.. DNA solution of HARD computational problems. Science， 1995； 268； 542--545.

[3]Chang W.L.， Guo， M. Y. . Solving the set cover problem and the problem of exact cover by 3-sets in the Adleman-Lipton model. BioSystems， 2003； 72； 263--275.

[4]李源，方辰，欧阳颀.最大团问题DNA计算机进化算法.科学通报，2004； 49；439--443.

[5]Xiao D.M.， Li W.X.， Zhang， Z.Z.， He L.. Solving maximum cut problem in the Adleman-Lipton model. BioSystems，2005；82； 203—207.

[6]Lee J.Y.， Shin， S.Y. et al.. Solving traveling salesman problems with DNA molecules encoding numerical values. BioSystems，2004；78；39--47.

[7]高琳，马瑞年，许进.有向最短哈密尔顿路问题的DNA算法.系统工程与电子技术2002；24（8）；102--105.

[8]丁永生，邵世煌，任立红.DNA计算与软计算.北京：科学出版社，2002：5--9.

[9]许进，王淑栋，潘林强译.G. Paun G. Rozenberg A. Salomaa. DNA计算 ---- 一种新的计算模式.北京：清华大学出版社，2004：3---29.

[10]王兆才，肖冬梅，贺林.旅行商问题的DNA算法.计算机工程与应用，2006，30：52—55.

[11]Wang Z.C.，Li W.X.，Xiao D.M..Solving the Traveling Salesman Problem in the Adleman-Lipton model. Applied Mathematics and computation，2006；5；102—105.