全錯位排列問題的DNA計算模型

胡娟

【摘 要】組合數學中的一個很重要問題全錯位排列問題其應用非常廣，利用0-1規劃可將此問題轉化為可滿足性問題，通過DNA分子之間產生的發夾結構，利用瓊脂糖凝膠可得到滿足問題的可行解，便于求解三元以上的全錯位排列。

【關鍵詞】全錯位排列問題；DNA計算；凝膠電泳

中圖分類號： TP301.6 文獻標識碼： A 文章編號： 2095-2457（2018）19-0101-002

DOI：10.19694/j.cnki.issn2095-2457.2018.19.045

DNA Computational Model for Error Permutation Problem

HU Juan

（The Foundation department of Huainan Vocational Technical College，Huainan Anhui 232001，China）

【Abstract】A very important problem in combinatorial mathematics is that the problem of total dislocation arrangement is very widely used. Using 0-1 programming， this problem can be converted into a satisfying problem through the hairpin structure generated between DNA molecules. A feasible solution to satisfy the problem can be obtained by agarose gel， and it is convenient to solve the total dislocation arrangement above three yuan.

【Key words】

0 引言

作為一種新型的計算方法，DNA計算的基本方法是將要解決的問題轉化為DNA編碼，再利用DNA分子的結構特點和不同核苷酸中四種堿基配對，通過各種生物酶及生化反應來得到所求問題的解。DNA計算最早是在1994年，Adleman博士用DNA計算解決了哈密頓有向路問題。它的運算速度及超大的存儲量是目前計算機無法比擬的。也正因為如此，越來越多的學者用它解決了一個有一個NP完全問題。如最大團問題，最小覆蓋問題及郵路一致性問題都用DNA計算得到了很好的解決。

目前DNA的實現方式走過了三個階段：初級階段---試管；過渡階段---表面；成功階段---芯片。對于組合數學的一個非常重要的問題全錯位排列問題，也有不少學者給出過解決方法，本文采用DNA計算模型來解決全錯位排列問題，此方法更便于求解三元以上的全錯位排列問題。

1 全錯位排列問題

全錯位排列問題最初是由著名的數學家伯努利提出的，作為組合數學中的一個重要的問題，它又被著名的數學家歐拉稱其為“錯裝信封問題”。此問題大意為：有一個人寫了n封不同的信，他用n個不同的信封來裝這些信，問他把這些信全都裝錯的裝法有多少種？后來此問題又被數學家用數學語言描述為：對于一個n元集合{1，2，...，n}來說，若它的全排列i1i2...in滿足條件ij≠j（1？燮j？燮n），則稱其此全排列為集合{1，2，...，n}的一個錯排。簡單說為第一個元素不能在第一位，第二個元素不能在第二位，第n個元素不能在第n位的全排列。目前做的較多的為三元集合的錯排問題。算法也有很多，有分類求解法，遞推關系求解法和多項式求解法。

下面我們以含有3元集合1，2，3的全錯位排列為例，求出其所有全錯位排列，問題即為對于數字1，2，3來說，數字1，2，3都不能在自己原來位置上的全排列。分析此問題用下列記號[2]：若第二位排數字1，記為a；若第一位排數字2，記為b；若第一位排數字3，記為c。則其否命題記為a'，b'，c'，對此問題根據0-1規劃將其可以轉化成可滿足性問題：如果數字1不在第二位上，那么數字3在第二位上；如果數字2在第一位上，那么數字3便不能在第一位上；如果數字1在第三位上，那么數字2便不能在第三位上。從而可以得到下面的范式：

現在即要求出滿足上式的所有可能解就可得出問題的解。

2 DNA計算的算法及其操作過程

2.1 基本算法

（1）利用0-1規劃對所給問題的變量取值為0，1，生成其所有可能的組合；

（2）為了保留可行解，依次利用范式中的約束條件排除非可行解；

（3）從而得到剩余的可行解；

（4）重復（2）（3），排除掉所有非可行解，得到滿足范式中的約束條件可行解。

2.2 DNA編碼

對于含有的3元集合的全錯位排列問題，第一步先合成初始6種DNA鏈，用a，b，c和a'，b'，c'表示，其特殊補鏈用表示（如圖1所示）。其中a，b，c對應的值表示為1，a'，b'，c'表示0。第二步由a，b，c和a'，b'，c'合成8種DNA片段放入數據池中，由三部分表示，前一部分是不參與反應，中間部分為a，b，c和a'，b'，c'的前四個堿基的補，后面部分為a，b，c和a'，b'，c'的后四個堿基的補（如圖2所示）。

（4）試管中即為滿足范式的所有解。通過檢驗可知該問題的解為：101和010，即231和312為3元集合1，2，3全錯位排列。

3 結論

本文就組合數學中的一個很重要問題全錯位排列問題給出DNA計算模型，利用0-1規劃將此問題轉化為可滿足性問題，通過DNA分子之間產生的發夾結構，利用瓊脂糖凝膠得到滿足問題的可行解，由于操作中只用到了瓊脂糖凝膠電泳，減小了實驗過程中的誤差，提高了求解的準確性和可操作性，便于求解3元以上的全錯位排列。

【參考文獻】

[1]劉建軍，劉芹英.歐拉對經典組合學的貢獻[J]自然科學史研究，2003（4）：361-367.

[2]孫俠，殷志詳等.全錯位排列問題的基于表面的DNA計算模型[J].生物數學學報，2009，24（3）：513-517.

[3]方剛，張社民，朱巖等，基于三鏈核酸的DNA計算[J].生物信息學，2009，7（3）：181-185.

[4]宋勃生，殷志詳等DNA自主裝的可滿足性問題模型[J].小型微型計算機系統2011，9（32）：1872-1875.

[5]Even S，Ltai A，Shamir A.On the complexity of time table and multi-commodity flow，problems[J].Siam Journal on Computing，1976，5（4）：691-703.

[6]ZHIXIANG YIN，MIN CHEN.Apply AcryditeTM Gel Separation to Solve Time–Table Problem[C]//Telkomnika Indonesian Journal of Electrical Engineering 2012，10（5）：1111-1116.

[10]Pillay N，Banzhaf W.A study of heuristic combinationa for hyperheuristic systems for the uncapacitated examination timetabling problem[J].European Journal of Operational Research，2009，197（2）：482-491.

[7]孫俠，殷志詳，趙前進等.基于三鏈DNA結構的全錯位排列問題算法[J].滁州學院學報，2012，2（14）：18-20.