0-1整数规划问题的巨磁电阻型DNA计算模型

殷志祥，杨珍琴

(安徽理工大学数学与大数据学院，安徽 淮南 232001)

1994年文献[1]利用DNA编码解决了Hamilton路径问题，也是首次分子生物学工具应用于NP完全问题；文献[2]利用接触网络G解决了SAT问题，与传统的电子计算机相比，具有更快的速度；文献[3]提出DNA表面计算，这种方法的优点是其可扩展性和潜在的自动化，为DNA计算的进一步研究做了铺垫；文献[4]对DNA表面计算的SAT问题进行了改进，具有成本低，操作时间短，可重复使用的表面和简单的实验步骤等优点；文献[5]利用三螺旋结构的DNA链，来解决0-1整数规划问题，从而对于一般整数规划和可满足性问题都可转化为0-1整数规划，利用三链DNA计算模型来解决；文献[6] 尝试将DNA计算应用于编程问题，利用基于表面的荧光标记技术解决了0-1规划问题的一般形式，具有编码简单，成本低，工作时间短等优点；文献[7] 基于微流体系统，提出了一种解决特殊0-1整数规划的DNA算法；文献[8]使用金纳米颗粒解决0-1规划问题；随后提出不同的DNA计算模型，解决了各类NP完全问题[9-13]。直到发现巨磁电阻传感器， 利用巨磁电阻解决了可满足性问题；文献[14]共同发现了一种超快速GMR型电阻材料-磷化铌，使巨磁电阻具有更大的应用前景。0-1规划问题与SAT(可满足性)问题是密切相关的[15-20]，是可满足性问题的推广。但DNA计算模型在求解NP完全问题时也存在所需的核苷酸分子数是指数的增加。

目前大多学者利用荧光标记杂交物，则对光信号检测设备要求高，使得信号分析变得困难。本文利用GMR型DNA芯片技术求解0-1整数规划问题，通过电信号方式输出，避免了荧光分析中的信号转换而引起的失真。

1 GMR型DNA芯片与0-1整数规划问题

1.1 GMR型DNA芯片

GMR型DNA芯片核心部分是使用大规模集成电路的微细加工技术，其检测步骤[22](见图1)如下：

第1步 把GMR传感器集成在一块基片上，为了避免分析过程中的溶液对芯片的腐蚀，在芯片表面覆盖一层保护层，在GMR型芯片表面固定DNA探针，然后将被生物素标记的待分析目标DNA链与探针进行充分杂交；

第2步 清洗未杂交的DNA链，将被抗生物素标识的纳米磁珠与DNA链键联，使抗生素一生物素结合，选择性的捕获磁性标记；利用磁分离器分离未参与标记的磁珠，通过芯片上的GMR传感器对芯片上纳米磁珠的检测，分析产生的信号强度、位置等信息。

图1 两步标记法示意图

1.2 0-1整数规划问题

0-1整数规划是整数规划的特殊情形，其变量xi仅取0或1，这时xi称为二进制变量，或0-1变量(如果xi不是仅取0或1，而是其它的非负整数，则可用二进制记数法将其用若干个0-1变量来替代)。0-1规划在整数规划中占有重要地位，一方面因为许多实际问题，例如指派问题、选地问题、送货问题都可归结为此类规划，另一方面任何有界变量的整数规划都与0-1规划等价，用0-1规划方法还可以把多种非线性规划问题表示成整数规划问题，一般形式为

max(min)z=c1x1+c2x2+…+cnxn

特殊形式为

max(min)z=c1x1+c2x2+…+cnxn

(*)

2 计算模型

2.1 基本算法

下面给出(*)对应的0-1整数规划问题算法步骤：

步骤1 生成给定问题的变量取值为0或1的所有可能组合；

步骤2 利用每一约束条件剔除非解；

步骤3 生成剩余的解；

步骤4 重复进行步骤2，3。排除所有的非解，得到问题的所有可行解；

步骤5 比较各可行解对应的目标函数值，得到最优解。程序框图如图2所示。

图2 0-1整数规划问题的DNA计算模型步骤图

2.2 生物算法

对于n个变量x1，x2，…，xn，m个约束条件的0-1整数规划问题，其GMR型DNA芯片计算的算法步骤如下：

步骤1 合成代表变量的DNA序列。首先合成3n种短的寡聚核苷酸片段，并分成3组：

1)第一组中n种DNA片段被表示为变量x1，x2，…，xn；

步骤2 合成0-1整数规划问题的所有可能解数据库。利用T4连接酶连接3n种寡聚核苷酸片段，构造出2n种DNA链，对每条DNA链的5′端用巯基修饰，并固定在GMR型DNA芯片表面上；

步骤3 将代表第k(k

步骤4将被生物素标识的磁珠加到GMR型芯片上充分反应后，利用磁分离器分离未参与标记的磁珠，在生物素一抗生素共价键的作用下，选择性的捕获磁性标记；

步骤5 若k=m，则停止算法程序，输出0-1整数规划问题的所有可能解；反之，令k=k+1转到步骤2。

3 GMR型DNA芯片模型实例

现举例描述0-1整数规划问题的GMR型DNA计算模型。

minS=2x+3y+2z

表1 DNA编码

利用T4连接酶连接6种短的寡聚核苷酸片段以合成8种不同的DNA链，对每条DNA链的5′端用巯基修饰，并固定在GMR型DNA芯片表面上，如图3所示。

图3 表面固定图

步骤2 根据第一个约束条件，在表面加入核苷酸x，y，z对应的补链x′，y′，z′进行杂交，并用缓冲液清洗掉未杂交的核苷酸序列，加入纳米磁珠进行磁性标记，利用磁分离器分离未参与标记的磁珠，记录电阻的变化。对于本问题，只有位置8电阻未发生任何变化，后面不考虑位置8。加热表面解开双链，并冲洗去掉磁珠。(满足该约束条件的为1，2，3，4，见图4)

图4 对应第一个约束条件反应示意图

步骤3 根据第二个约束条件，在表面加入核苷酸x，z对应的补链x′，z′进行杂交，并用缓冲液清洗掉未杂交的核苷酸序列，加入纳米磁珠进行磁性标记，利用磁分离器分离未参与标记的磁珠，记录电阻的变化。加热表面解开双链，并冲洗去掉磁珠。(满足该约束条件的为2，4，5，7，见图5)

图5 对应第二个约束条件反应示意图

步骤4 根据第三个约束条件，在表面加入核苷酸y，z对应的补链y′，z′进行杂交，并用缓冲液清洗掉未杂交的核苷酸序列，加入纳米磁珠进行磁性标记，利用磁分离器分离未参与标记的磁珠，记录电阻的变化。加热表面解开双链，并冲洗去掉磁珠。(满足该约束条件的为2，3，6，7，见图6)

图6 对应第三个约束条件反应示意图

步骤5 记录满足约束方程的所有可行解，求出最优解。对于本问题，可行解是2，对应的编码变量值为(1，1，0)也是最优解，目标函数最小值为5。

4 结论

(1)结果输出方式不同。传统计算模型是以DNA链作为输出结果，本文的计算模型的输出结果是电信号，因此具有较好的灵敏度。

(2)检测方式不同。该模型将目标DNA链与GMR型芯片表面固定的DNA探针杂交，通过GMR传感器检测，因此具有信号检测简单，结果分析便捷等优势。

(3)尝试了将GMR型DNA芯片技术应用于DNA计算中，这是对现阶段DAN计算的一种探索。随着GMR型DNA计算模型研究的不断深入，该模型将具有解决更多NP完全问题将的能力。