基于表面的DNA计算模型解决排课表问题

单静怡，殷志祥

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

随着电子计算机的微处理能力接近极限，研究新的计算机结构成为现阶段的研究热点。通过许多学者对DNA 计算模型和DNA 计算可行性的研究［1－4］，使DNA 计算从理论到实践成为可能。DNA 计算主要是根据DNA 结构的特点，将问题变量映射为特定的寡聚核苷酸片段，进行退火杂交反应，利用DNA 具有存储海量信息的特点，在一定的判断准则和相应的生物操作下，得到问题的可行解。

微量点样技术［5］主要是用于制作基因芯片，是指将一些提前设计好的特殊的DNA 单链片段按照问题的要求依次排列并固定于物体表面上，利用DNA 的碱基互补配对原则与待测的DNA 单链片段进行杂交反应。然后利用相应的检测技术对结果进行观察并记录，通过多次反应，比较结果，最后得到问题的可行解。微量点样技术具有存储量大，并行性好等特点，对于研究规模较大的问题具有一定的优势。

1 排课表问题

排课表问题是指在一定的条件下，对有限的资源进行合理的分配，使得课时安排在满足问题要求的情况下，使用的课时数最少。在现实中，由于考虑到教师、班级以及课时等的不同情况，这样的排课表问题就是NP 问题。简单的一些排课表问题与0－1 规划问题的思想基本相同。许多学者提出以图的着色算法来解决排课表问题［6－8］。周康等在图着色算法的基础上，提出用闭环DNA 计算模型解决排课表问题［9］。文献［10］提出了用AcryditeTM分离技术建立DNA 模型解决简单排课表问题，在每次循环的过程中需要重新构建凝胶柱。本文在0－1 规划模型［11－12］基础上，提出了排课表问题的基于微量点样技术的表面DNA 计算模型，在这一过程中，不需要改变问题的初始点列，通过对每次结果进行记录和比较，就可得到满足问题要求的可行解。

根据0－1 规划问题的模型，可以用DNA 表面计算模型求解一类简单的排课表问题。假设有r名教师和s个班级，教师ri给班级sj上tij节课，要求在一定的约束条件下，用最少的课时设计课程表。

2 排课表问题的DNA 计算模型

这里，我们以一个简单的排课表实例为例构造DNA 计算模型。有3 名教师r1，r2和r3，4 个班级s1，s2，s3和s4，对应的课时情况T=［tij］为

在该问题中的条件为:一名教师只能在一个课时给一个班级上课。一个班级在一个课时只能参加一个课程。s1和s4只能在x1上课。s2只能在x2上课。r3只能在第二课时给s4上课。我们约定有足够的教室可用。

2.1 生物算法

简单的排课表问题可以用0－1 规划的思想来构造模型，其基本算法是:首先构造给定变量的相应的点列。根据问题的每一要求条件得到对应的可行点列，生成剩余的点列，检验剩余的点列，直到所有的点列被检验完，从而得到满足问题要求的可行解。它的生物算法可描述为:

1)生成对应问题不同变量的单链DNA 片段，利用微量点样技术，按照点阵的形式微量点样于物体表面(如玻片)，用两种不同颜色的荧光对相应变量的补链进行标记，把经过标记的单链DNA 片段制成探针。

2)在表面加入对应于每个变量的补链。含有该变量的点列将与对应的补链进行杂交并产生不同颜色的荧光，判断荧光的颜色是否符合要求，利用荧光成像技术记录符合要求的点列。

3)加热表面恢复单链的形式，用缓冲液冲洗掉被分解的探针。

4)重复进行(2)、(3)(对于(2)中已经判断为符合要求的点列不予考虑)，当所有的点列被检验完时，分析每次结果可得一个符合要求的课时安排。

2.2 编码和生物操作

对应于上述的实例，它的编码和生物操作如下:

1)生成单链DNA 片段s1，s2，s3，s4，单链DNA片段x1，x2，并生成补序列，如图1所示。并将用绿荧光(ABI)标记，将用蓝荧光(CY3TM)标记，把经过荧光标记的DNA 单链片段制作成探针。

图1 变量的编码图

2)用6～9 个原子的连接臂将DNA 单链s1，s2，s3，s4和按照问题的要求，以点阵形式固定到表面上，根据每位教师给不同班级的上课情况，排成8 行、3 列，当教师不给某班级上课，或班级上课不限制在规定的教室时，该处排列为空，如图2所示，第1，2，3 列分别表示教师r1，r2，r3的课时情况。因为点样排列是可寻址的，所以该方法在理论上是可行的。

图2 所有课时情况的点样示意图

图3 加入后的反应示意图

图4 加入后的反应示意图

图5 加入后的反应示意图

4)在第二次循环过程中，为满足问题要求的条件，先在表面加入对应的DNA 探针，探针与s4，x1杂交并产生不同颜色的荧光(见图6)。

图6 加入后的反应示意图

由于s4只能在教室x1上课，利用荧光成像技术观察并记录符合条件的解(符合情况的为第3列)，可得教师r3可以在教室x1给班级s4上课。加热表面恢复单链的形式，用缓冲液冲洗掉被分解的探针。同理，检验剩下的点列，排除第一次循环过程中已经考虑过的点列，检验剩下的点列，如图4～图5所示。这一循环，可以得到第二课时的安排{r1s2，r2s3，r3s4}。

5)在第三次循环中，只剩下第1 列中的s3没有被安排在课时表中。在表面加入对应的DNA探针，探针与s3杂交并产生荧光，如图5所示。利用荧光成像技术观察并记录符合条件的解(符合情况的为第1，2，3 列)，由于第2，3 列的s3已经在前两次循环中出现，于是可知教师r1可以给班级s3上课。这样，所有的点列被检验完。这一循环，可以得到第三课时的安排{r1s3}。

2.3 实验分析

在该实验中，根据荧光颜色确定课时安排，经过3 次循环可获得一个可行的课程安排，实验结果如表1。从表中可以看到，最少需要3 个学时完成课程，课时安排分别为{r1s1，r2s2，r3s3}，{r1s2，r2s3，r3s4}，{r1s3}。

表1 满足教学要求的课时安排

在简单排课表问题中，如果tij≥2，即教师ri需要给班级sj上至少两节课时，可添加班级sj1，sj2，…，sjm，使m= tij－1，将T 增加m行，使其只含0，1，最后用该问题的模型来计算。如果要求教室数量有限，则依据教室的数量限制每个循环的班级数。

3 结论与讨论

本文在0－1 规划模型基础上，提出了排课表问题的基于微量点样技术的表面DNA 计算模型。该方法具有存储量大，并行性好等特点，将适于研究规模较大的问题。因为排课表模型是用地址阵列来表示的，具有较好的可靠性，理论上是可行的。

［1］ADLEMAN L M.Molecular computation of solutions to combinatorial problems［J］.Science，1994，266(11):1 021－1 023.

［2］GARZON M，DEATON R.Codeword design and information encoding in DNA ensembles［J］.Natural Computing，2004，3:253－292.

［3］LIU Q H，WANG L M，FRUTO A G，et al.DNA computing on surfaces［J］.Nature，2000，403(13):175－179.

［4］WU H Y.AN improved surface－based method for DNA computation［J］.Biosystems，2001，59(1):1－5.

［5］陈执中.DNA 微阵列技术的研究应用进展［J］.药物生物技术，2001，8(6):357－359.

［6］WERRA D.An introduction to timetabling［J］.European Journal of Operations Research，1985，19:151－162.

［7］ABRAMSON D.Constructing school timetables using simulated annealing:Sequential and parallel algorithms［J］.Management Science，1991，37:98－113.

［8］李敬文，于自强.基于立方体染色的排课表模型［J］.计算机工程，2010，36(24):281－283.

［9］周康，同小军，刘文斌.排课表问题的闭环DNA 计算模型的算法［J］.计算机应用，2007，27(4):991－993.

［10］ZHIXIANG YIN，MIN CHEN.Apply AcryditeTM Gel Separation to Solve Time－ Table Problem［C］//TELKOMNIKA Indonesian Journal of Electrical Engineering 2012，10(5):1 111－1 116.

［11］殷志祥.图与组合优化中的DNA 计算［M］.北京:科学出版社，2004:100－105.

［12］孙侠，殷志祥，李勇，等.全错位排列问题的基于芯片的DNA 计算模型［J］.大学数学，2010，26(5):79－81.