基于表面的DNA計(jì)算模型解決排課表問(wèn)題

單靜怡，殷志祥

(安徽理工大學(xué)理學(xué)院，安徽 淮南 232001)

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

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

1 排課表問(wèn)題

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

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

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

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

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

2.1 生物算法

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

1)生成對(duì)應(yīng)問(wèn)題不同變量的單鏈DNA 片段，利用微量點(diǎn)樣技術(shù)，按照點(diǎn)陣的形式微量點(diǎn)樣于物體表面(如玻片)，用兩種不同顏色的熒光對(duì)相應(yīng)變量的補(bǔ)鏈進(jìn)行標(biāo)記，把經(jīng)過(guò)標(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í)安排。

2.2 編碼和生物操作

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

1)生成單鏈DNA 片段s1，s2，s3，s4，單鏈DNA片段x1，x2，并生成補(bǔ)序列，如圖1所示。并將用綠熒光(ABI)標(biāo)記，將用藍(lán)熒光(CY3TM)標(biāo)記，把經(jīng)過(guò)熒光標(biāo)記的DNA 單鏈片段制作成探針。

圖1 變量的編碼圖

2)用6～9 個(gè)原子的連接臂將DNA 單鏈s1，s2，s3，s4和按照問(wèn)題的要求，以點(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 加入后的反應(yīng)示意圖

圖4 加入后的反應(yīng)示意圖

圖5 加入后的反應(yīng)示意圖

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

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

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

5)在第三次循環(huán)中，只剩下第1 列中的s3沒(méi)有被安排在課時(shí)表中。在表面加入對(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}。

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

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

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

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

3 結(jié)論與討論

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

［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］周康，同小軍，劉文斌.排課表問(wèn)題的閉環(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ò)位排列問(wèn)題的基于芯片的DNA 計(jì)算模型［J］.大學(xué)數(shù)學(xué)，2010，26(5):79－81.