單靜怡　殷志祥

摘要：考慮到教師、班級(jí)以及課時(shí)等的不同要求，復(fù)雜的排課表問題就屬于NP問題。為了使排課表問題更加簡捷，方便，提出了基于微量點(diǎn)樣技術(shù)的表面DNA計(jì)算模型。在實(shí)驗(yàn)中，通過對(duì)每次結(jié)果進(jìn)行記錄和比較，得到了滿足問題要求的可行解。不需要改變問題的初始點(diǎn)列，適于研究規(guī)模較大的問題。

關(guān)鍵詞：DNA表面模型；排課表問題；0-1規(guī)劃問題

中圖分類號(hào)：TP301.6 文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1672-1098（2014）01-0011-04

隨著電子計(jì)算機(jī)的微處理能力接近極限，研究新的計(jì)算機(jī)結(jié)構(gòu)成為現(xiàn)階段的研究熱點(diǎn)。通過許多學(xué)者對(duì)DNA計(jì)算模型和DNA計(jì)算可行性的研究[1-4]， 使DNA計(jì)算從理論到實(shí)踐成為可能。DNA計(jì)算主要是根據(jù)DNA結(jié)構(gòu)的特點(diǎn)，將問題變量映射為特定的寡聚核苷酸片段，進(jìn)行退火雜交反應(yīng)，利用DNA具有存儲(chǔ)海量信息的特點(diǎn)，在一定的判斷準(zhǔn)則和相應(yīng)的生物操作下，得到問題的可行解。

微量點(diǎn)樣技術(shù)[5]主要是用于制作基因芯片，是指將一些提前設(shè)計(jì)好的特殊的DNA單鏈片段按照問題的要求依次排列并固定于物體表面上，利用DNA的堿基互補(bǔ)配對(duì)原則與待測(cè)的DNA單鏈片段進(jìn)行雜交反應(yīng)。然后利用相應(yīng)的檢測(cè)技術(shù)對(duì)結(jié)果進(jìn)行觀察并記錄，通過多次反應(yīng)，比較結(jié)果，最后得到問題的可行解。微量點(diǎn)樣技術(shù)具有存儲(chǔ)量大，并行性好等特點(diǎn)，對(duì)于研究規(guī)模較大的問題具有一定的優(yōu)勢(shì)。

1排課表問題

排課表問題是指在一定的條件下，對(duì)有限的資源進(jìn)行合理的分配，使得課時(shí)安排在滿足問題要求的情況下，使用的課時(shí)數(shù)最少。在現(xiàn)實(shí)中，由于考慮到教師、班級(jí)以及課時(shí)等的不同情況，這樣的排課表問題就是NP問題。簡單的一些排課表問題與0-1規(guī)劃問題的思想基本相同。許多學(xué)者提出以圖的著色算法來解決排課表問題[6-8]。周康等在圖著色算法的基礎(chǔ)上，提出用閉環(huán)DNA計(jì)算模型解決排課表問題[9]。文獻(xiàn)[10]提出了用AcryditeTM分離技術(shù)建立DNA模型解決簡單排課表問題，在每次循環(huán)的過程中需要重新構(gòu)建凝膠柱。本文在0-1規(guī)劃模型[11-12]基礎(chǔ)上，提出了排課表問題的基于微量點(diǎn)樣技術(shù)的表面DNA計(jì)算模型，在這一過程中，不需要改變問題的初始點(diǎn)列，通過對(duì)每次結(jié)果進(jìn)行記錄和比較，就可得到滿足問題要求的可行解。

根據(jù)0-1規(guī)劃問題的模型，可以用DNA表面計(jì)算模型求解一類簡單的排課表問題。假設(shè)有r名教師和s個(gè)班級(jí)，教師ri給班級(jí)sj上tij節(jié)課，要求在一定的約束條件下，用最少的課時(shí)設(shè)計(jì)課程表。

2排課表問題的DNA計(jì)算模型

這里，我們以一個(gè)簡單的排課表實(shí)例為例構(gòu)造DNA計(jì)算模型。有3名教師r1，r2和r3，4個(gè)班級(jí)s1，s2，s3和s4，對(duì)應(yīng)的課時(shí)情況T=[tij]為

T=111001100011

在該問題中的條件為：一名教師只能在一個(gè)課時(shí)給一個(gè)班級(jí)上課。一個(gè)班級(jí)在一個(gè)課時(shí)只能參加一個(gè)課程。s1和s4只能在x1上課。s2只能在x2上課。r3只能在第二課時(shí)給s4上課。我們約定有足夠的教室可用。

21生物算法

簡單的排課表問題可以用0-1規(guī)劃的思想來構(gòu)造模型，其基本算法是：首先構(gòu)造給定變量的相應(yīng)的點(diǎn)列。根據(jù)問題的每一要求條件得到對(duì)應(yīng)的可行點(diǎn)列，生成剩余的點(diǎn)列，檢驗(yàn)剩余的點(diǎn)列，直到所有的點(diǎn)列被檢驗(yàn)完，從而得到滿足問題要求的可行解。它的生物算法可描述為：

1） 生成對(duì)應(yīng)問題不同變量的單鏈DNA片段，利用微量點(diǎn)樣技術(shù)，按照點(diǎn)陣的形式微量點(diǎn)樣于物體表面（如玻片），用兩種不同顏色的熒光對(duì)相應(yīng)變量的補(bǔ)鏈進(jìn)行標(biāo)記，把經(jīng)過標(biāo)記的單鏈DNA片段制成探針。

2） 在表面加入對(duì)應(yīng)于每個(gè)變量的補(bǔ)鏈。含有該變量的點(diǎn)列將與對(duì)應(yīng)的補(bǔ)鏈進(jìn)行雜交并產(chǎn)生不同顏色的熒光，判斷熒光的顏色是否符合要求，利用熒光成像技術(shù)記錄符合要求的點(diǎn)列。

3） 加熱表面恢復(fù)單鏈的形式，用緩沖液沖洗掉被分解的探針。

4） 重復(fù)進(jìn)行（2）、（3）（對(duì)于（2）中已經(jīng)判斷為符合要求的點(diǎn)列不予考慮），當(dāng)所有的點(diǎn)列被檢驗(yàn)完時(shí)，分析每次結(jié)果可得一個(gè)符合要求的課時(shí)安排。

22編碼和生物操作

對(duì)應(yīng)于上述的實(shí)例，它的編碼和生物操作如下：

2） 用6～9個(gè)原子的連接臂將DNA單鏈s1，s2，s3，s4和x1，x2按照問題的要求，以點(diǎn)陣形式固定到表面上，根據(jù)每位教師給不同班級(jí)的上課情況，排成8行、3列，當(dāng)教師不給某班級(jí)上課，或班級(jí)上課不限制在規(guī)定的教室時(shí)，該處排列為空，如圖2所示，第1，2，3列分別表示教師r1，r2，r3的課時(shí)情況。因?yàn)辄c(diǎn)樣排列是可尋址的，所以該方法在理論上是可行的。

圖2所有課時(shí)情況的點(diǎn)樣示意圖

3） 在表面加入s1，x1對(duì)應(yīng)的DNA探針，探針與s1，x1雜交并產(chǎn)生不同顏色的熒光，如圖3所示。由于教師r1只能在教室x1上課，利用熒光成像技術(shù)觀察并記錄符合條件的解（符合條件的為第1列）。即可得教師r1可以在教室x1給班級(jí)s1上課。加熱表面恢復(fù)單鏈的形式，用緩沖液沖洗掉被分解的探針。同理，在表面加入s2，x2對(duì)應(yīng)的DNA探針，探針與s2，x2雜交并產(chǎn)生不同顏色的熒光，如圖4所示。利用熒光成像技術(shù)觀察并記錄符合條件的解（符合條件的為第1，2列）。第1列已經(jīng)被考慮過，不再考慮，可得教師r2可以在教室x2給班級(jí)s2上課。加熱表面恢復(fù)單鏈的形式，用緩沖液沖洗掉被分解的探針。按照同樣的方法，在表面加入s3對(duì)應(yīng)的DNA探針，探針與s3雜交并產(chǎn)生熒光，如圖5所示。利用熒光成像技術(shù)觀察并記錄符合條件的解（符合條件的為第1，2，3列），第1、2列已經(jīng)被考慮過，不再考慮，從而可得教師r3可以給班級(jí)s3上課。加熱表面恢復(fù)單鏈的形式，用緩沖液沖洗掉被分解的探針。在這一循環(huán)中，所有的列均被被檢驗(yàn)過，可得第一個(gè)課時(shí)安排為{r1s1，r2s2，r3s3}。

4） 在第二次循環(huán)過程中，為滿足問題要求的條件，先在表面加入s4，x1對(duì)應(yīng)的DNA探針，探針與s4，x1雜交并產(chǎn)生不同顏色的熒光（見圖6）。

圖6 加入y4，a后的反應(yīng)示意圖

由于s4只能在教室x1上課，利用熒光成像技術(shù)觀察并記錄符合條件的解（符合情況的為第3列），可得教師r3可以在教室x1給班級(jí)s4上課。加熱表面恢復(fù)單鏈的形式，用緩沖液沖洗掉被分解的探針。同理，檢驗(yàn)剩下的點(diǎn)列，排除第一次循環(huán)過程中已經(jīng)考慮過的點(diǎn)列，檢驗(yàn)剩下的點(diǎn)列，如圖4～圖5所示。這一循環(huán)，可以得到第二課時(shí)的安排{r1s2，r2s3，r3s4}。

5） 在第三次循環(huán)中，只剩下第1列中的s3沒有被安排在課時(shí)表中。在表面加入s3對(duì)應(yīng)的DNA探針，探針與s3雜交并產(chǎn)生熒光，如圖5所示。利用熒光成像技術(shù)觀察并記錄符合條件的解（符合情況的為第1，2，3列），由于第2，3列的s3已經(jīng)在前兩次循環(huán)中出現(xiàn)，于是可知教師r1可以給班級(jí)s3上課。這樣，所有的點(diǎn)列被檢驗(yàn)完。這一循環(huán)，可以得到第三課時(shí)的安排{r1s3}。

23實(shí)驗(yàn)分析

在該實(shí)驗(yàn)中，根據(jù)熒光顏色確定課時(shí)安排，經(jīng)過3次循環(huán)可獲得一個(gè)可行的課程安排，實(shí)驗(yàn)結(jié)果如表1。從表中可以看到，最少需要3個(gè)學(xué)時(shí)完成課程，課時(shí)安排分別為{r1s1，r2s2，r3s3}， {r1s2，r2s3，r3s4}，{r1s3}。

表1滿足教學(xué)要求的課時(shí)安排

教師安排第一課時(shí)第二課時(shí)第三課時(shí)

教師r1r1s1r1s2r1s3

教師r2r2s2r2s3

教師r3r3s3r3s4

在簡單排課表問題中，如果tij≥2，即教師ri需要給班級(jí)sj上至少兩節(jié)課時(shí)，可添加班級(jí)sj1，sj2，…，sjm，使m=tij-1，將T增加m行，使其只含0，1，最后用該問題的模型來計(jì)算。如果要求教室數(shù)量有限，則依據(jù)教室的數(shù)量限制每個(gè)循環(huán)的班級(jí)數(shù)。

3結(jié)論與討論

本文在0-1規(guī)劃模型基礎(chǔ)上，提出了排課表問題的基于微量點(diǎn)樣技術(shù)的表面DNA計(jì)算模型。該方法具有存儲(chǔ)量大，并行性好等特點(diǎn)，將適于研究規(guī)模較大的問題。因?yàn)榕耪n表模型是用地址陣列來表示的，具有較好的可靠性，理論上是可行的。

參考文獻(xiàn)：

[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，F(xiàn)RUTO 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]陳執(zhí)中. DNA微陣列技術(shù)的研究應(yīng)用進(jìn)展[J]. 藥物生物技術(shù)， 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]李敬文， 于自強(qiáng). 基于立方體染色的排課表模型[J]. 計(jì)算機(jī)工程， 2010， 36（24）： 281-283.

[9]周康， 同小軍， 劉文斌. 排課表問題的閉環(huán)DNA計(jì)算模型的算法[J].計(jì)算機(jī)應(yīng)用， 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]殷志祥. 圖與組合優(yōu)化中的DNA計(jì)算[M]. 北京：科學(xué)出版社， 2004： 100-105.

[12]孫俠， 殷志祥， 李勇， 等. 全錯(cuò)位排列問題的基于芯片的DNA計(jì)算模型[J]. 大學(xué)數(shù)學(xué)， 2010， 26（5）： 79-81.

（責(zé)任編輯：李麗，范君）

4） 在第二次循環(huán)過程中，為滿足問題要求的條件，先在表面加入s4，x1對(duì)應(yīng)的DNA探針，探針與s4，x1雜交并產(chǎn)生不同顏色的熒光（見圖6）。

圖6 加入y4，a后的反應(yīng)示意圖

由于s4只能在教室x1上課，利用熒光成像技術(shù)觀察并記錄符合條件的解（符合情況的為第3列），可得教師r3可以在教室x1給班級(jí)s4上課。加熱表面恢復(fù)單鏈的形式，用緩沖液沖洗掉被分解的探針。同理，檢驗(yàn)剩下的點(diǎn)列，排除第一次循環(huán)過程中已經(jīng)考慮過的點(diǎn)列，檢驗(yàn)剩下的點(diǎn)列，如圖4～圖5所示。這一循環(huán)，可以得到第二課時(shí)的安排{r1s2，r2s3，r3s4}。

5） 在第三次循環(huán)中，只剩下第1列中的s3沒有被安排在課時(shí)表中。在表面加入s3對(duì)應(yīng)的DNA探針，探針與s3雜交并產(chǎn)生熒光，如圖5所示。利用熒光成像技術(shù)觀察并記錄符合條件的解（符合情況的為第1，2，3列），由于第2，3列的s3已經(jīng)在前兩次循環(huán)中出現(xiàn)，于是可知教師r1可以給班級(jí)s3上課。這樣，所有的點(diǎn)列被檢驗(yàn)完。這一循環(huán)，可以得到第三課時(shí)的安排{r1s3}。

23實(shí)驗(yàn)分析

在該實(shí)驗(yàn)中，根據(jù)熒光顏色確定課時(shí)安排，經(jīng)過3次循環(huán)可獲得一個(gè)可行的課程安排，實(shí)驗(yàn)結(jié)果如表1。從表中可以看到，最少需要3個(gè)學(xué)時(shí)完成課程，課時(shí)安排分別為{r1s1，r2s2，r3s3}， {r1s2，r2s3，r3s4}，{r1s3}。

表1滿足教學(xué)要求的課時(shí)安排

教師安排第一課時(shí)第二課時(shí)第三課時(shí)

教師r1r1s1r1s2r1s3

教師r2r2s2r2s3

教師r3r3s3r3s4

在簡單排課表問題中，如果tij≥2，即教師ri需要給班級(jí)sj上至少兩節(jié)課時(shí)，可添加班級(jí)sj1，sj2，…，sjm，使m=tij-1，將T增加m行，使其只含0，1，最后用該問題的模型來計(jì)算。如果要求教室數(shù)量有限，則依據(jù)教室的數(shù)量限制每個(gè)循環(huán)的班級(jí)數(shù)。

3結(jié)論與討論

本文在0-1規(guī)劃模型基礎(chǔ)上，提出了排課表問題的基于微量點(diǎn)樣技術(shù)的表面DNA計(jì)算模型。該方法具有存儲(chǔ)量大，并行性好等特點(diǎn)，將適于研究規(guī)模較大的問題。因?yàn)榕耪n表模型是用地址陣列來表示的，具有較好的可靠性，理論上是可行的。

參考文獻(xiàn)：

[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，F(xiàn)RUTO 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]陳執(zhí)中. DNA微陣列技術(shù)的研究應(yīng)用進(jìn)展[J]. 藥物生物技術(shù)， 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]李敬文， 于自強(qiáng). 基于立方體染色的排課表模型[J]. 計(jì)算機(jī)工程， 2010， 36（24）： 281-283.

[9]周康， 同小軍， 劉文斌. 排課表問題的閉環(huán)DNA計(jì)算模型的算法[J].計(jì)算機(jī)應(yīng)用， 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]殷志祥. 圖與組合優(yōu)化中的DNA計(jì)算[M]. 北京：科學(xué)出版社， 2004： 100-105.

[12]孫俠， 殷志祥， 李勇， 等. 全錯(cuò)位排列問題的基于芯片的DNA計(jì)算模型[J]. 大學(xué)數(shù)學(xué)， 2010， 26（5）： 79-81.

（責(zé)任編輯：李麗，范君）

4） 在第二次循環(huán)過程中，為滿足問題要求的條件，先在表面加入s4，x1對(duì)應(yīng)的DNA探針，探針與s4，x1雜交并產(chǎn)生不同顏色的熒光（見圖6）。

圖6 加入y4，a后的反應(yīng)示意圖

由于s4只能在教室x1上課，利用熒光成像技術(shù)觀察并記錄符合條件的解（符合情況的為第3列），可得教師r3可以在教室x1給班級(jí)s4上課。加熱表面恢復(fù)單鏈的形式，用緩沖液沖洗掉被分解的探針。同理，檢驗(yàn)剩下的點(diǎn)列，排除第一次循環(huán)過程中已經(jīng)考慮過的點(diǎn)列，檢驗(yàn)剩下的點(diǎn)列，如圖4～圖5所示。這一循環(huán)，可以得到第二課時(shí)的安排{r1s2，r2s3，r3s4}。

5） 在第三次循環(huán)中，只剩下第1列中的s3沒有被安排在課時(shí)表中。在表面加入s3對(duì)應(yīng)的DNA探針，探針與s3雜交并產(chǎn)生熒光，如圖5所示。利用熒光成像技術(shù)觀察并記錄符合條件的解（符合情況的為第1，2，3列），由于第2，3列的s3已經(jīng)在前兩次循環(huán)中出現(xiàn)，于是可知教師r1可以給班級(jí)s3上課。這樣，所有的點(diǎn)列被檢驗(yàn)完。這一循環(huán)，可以得到第三課時(shí)的安排{r1s3}。

23實(shí)驗(yàn)分析

在該實(shí)驗(yàn)中，根據(jù)熒光顏色確定課時(shí)安排，經(jīng)過3次循環(huán)可獲得一個(gè)可行的課程安排，實(shí)驗(yàn)結(jié)果如表1。從表中可以看到，最少需要3個(gè)學(xué)時(shí)完成課程，課時(shí)安排分別為{r1s1，r2s2，r3s3}， {r1s2，r2s3，r3s4}，{r1s3}。

表1滿足教學(xué)要求的課時(shí)安排

教師安排第一課時(shí)第二課時(shí)第三課時(shí)

教師r1r1s1r1s2r1s3

教師r2r2s2r2s3

教師r3r3s3r3s4

在簡單排課表問題中，如果tij≥2，即教師ri需要給班級(jí)sj上至少兩節(jié)課時(shí)，可添加班級(jí)sj1，sj2，…，sjm，使m=tij-1，將T增加m行，使其只含0，1，最后用該問題的模型來計(jì)算。如果要求教室數(shù)量有限，則依據(jù)教室的數(shù)量限制每個(gè)循環(huán)的班級(jí)數(shù)。

3結(jié)論與討論

本文在0-1規(guī)劃模型基礎(chǔ)上，提出了排課表問題的基于微量點(diǎn)樣技術(shù)的表面DNA計(jì)算模型。該方法具有存儲(chǔ)量大，并行性好等特點(diǎn)，將適于研究規(guī)模較大的問題。因?yàn)榕耪n表模型是用地址陣列來表示的，具有較好的可靠性，理論上是可行的。

參考文獻(xiàn)：

[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，F(xiàn)RUTO 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]陳執(zhí)中. DNA微陣列技術(shù)的研究應(yīng)用進(jìn)展[J]. 藥物生物技術(shù)， 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]李敬文， 于自強(qiáng). 基于立方體染色的排課表模型[J]. 計(jì)算機(jī)工程， 2010， 36（24）： 281-283.

[9]周康， 同小軍， 劉文斌. 排課表問題的閉環(huán)DNA計(jì)算模型的算法[J].計(jì)算機(jī)應(yīng)用， 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]殷志祥. 圖與組合優(yōu)化中的DNA計(jì)算[M]. 北京：科學(xué)出版社， 2004： 100-105.

[12]孫俠， 殷志祥， 李勇， 等. 全錯(cuò)位排列問題的基于芯片的DNA計(jì)算模型[J]. 大學(xué)數(shù)學(xué)， 2010， 26（5）： 79-81.

（責(zé)任編輯：李麗，范君）