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

单静怡　殷志祥

摘要：考虑到教师、班级以及课时等的不同要求，复杂的排课表问题就属于NP问题。为了使排课表问题更加简捷，方便，提出了基于微量点样技术的表面DNA计算模型。在实验中，通过对每次结果进行记录和比较，得到了满足问题要求的可行解。不需要改变问题的初始点列，适于研究规模较大的问题。

关键词：DNA表面模型；排课表问题；0-1规划问题

中图分类号：TP301.6 文献标志码：A

文章编号：1672-1098（2014）01-0011-04

随着电子计算机的微处理能力接近极限，研究新的计算机结构成为现阶段的研究热点。通过许多学者对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]为

T=111001100011

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

21生物算法

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

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

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

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

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

22编码和生物操作

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

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

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

3） 在表面加入s1，x1对应的DNA探针，探针与s1，x1杂交并产生不同颜色的荧光，如图3所示。由于教师r1只能在教室x1上课，利用荧光成像技术观察并记录符合条件的解（符合条件的为第1列）。即可得教师r1可以在教室x1给班级s1上课。加热表面恢复单链的形式，用缓冲液冲洗掉被分解的探针。同理，在表面加入s2，x2对应的DNA探针，探针与s2，x2杂交并产生不同颜色的荧光，如图4所示。利用荧光成像技术观察并记录符合条件的解（符合条件的为第1，2列）。第1列已经被考虑过，不再考虑，可得教师r2可以在教室x2给班级s2上课。加热表面恢复单链的形式，用缓冲液冲洗掉被分解的探针。按照同样的方法，在表面加入s3对应的DNA探针，探针与s3杂交并产生荧光，如图5所示。利用荧光成像技术观察并记录符合条件的解（符合条件的为第1，2，3列），第1、2列已经被考虑过，不再考虑，从而可得教师r3可以给班级s3上课。加热表面恢复单链的形式，用缓冲液冲洗掉被分解的探针。在这一循环中，所有的列均被被检验过，可得第一个课时安排为{r1s1，r2s2，r3s3}。

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

图6 加入y4，a后的反应示意图

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

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

23实验分析

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

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

教师安排第一课时第二课时第三课时

教师r1r1s1r1s2r1s3

教师r2r2s2r2s3

教师r3r3s3r3s4

在简单排课表问题中，如果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.

（责任编辑：李丽，范君）

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

图6 加入y4，a后的反应示意图

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

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

23实验分析

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

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

教师安排第一课时第二课时第三课时

教师r1r1s1r1s2r1s3

教师r2r2s2r2s3

教师r3r3s3r3s4

在简单排课表问题中，如果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.

（责任编辑：李丽，范君）

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

图6 加入y4，a后的反应示意图

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

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

23实验分析

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

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

教师安排第一课时第二课时第三课时

教师r1r1s1r1s2r1s3

教师r2r2s2r2s3

教师r3r3s3r3s4

在简单排课表问题中，如果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.

（责任编辑：李丽，范君）