基于分子信標(biāo)的全錯(cuò)位排列問(wèn)題的DNA計(jì)算模型

聶 茜,殷志祥

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

基于分子信標(biāo)的全錯(cuò)位排列問(wèn)題的DNA計(jì)算模型

聶 茜,殷志祥

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

全錯(cuò)位排列問(wèn)題是組合數(shù)學(xué)的一個(gè)重要的問(wèn)題，將問(wèn)題轉(zhuǎn)化成范式的形式，利用分子信標(biāo)對(duì)滿足性問(wèn)題進(jìn)行求解，給分子信標(biāo)進(jìn)行編碼，對(duì)分子信標(biāo)的識(shí)別區(qū)被其補(bǔ)鏈雜交時(shí)進(jìn)行受力分析，設(shè)計(jì)分子信標(biāo)的莖桿，當(dāng)其識(shí)別區(qū)被其補(bǔ)鏈完全雜交時(shí)，莖桿被破壞打開(kāi)并產(chǎn)生熒光，從而給出全錯(cuò)位排列問(wèn)題的另一種DNA計(jì)算模型。

全錯(cuò)位排列問(wèn)題；分子信標(biāo)；DNA計(jì)算

自從電子計(jì)算機(jī)問(wèn)世以來(lái)，其對(duì)社會(huì)的發(fā)展起到了巨大的促進(jìn)作用。隨著科學(xué)技術(shù)的不斷進(jìn)步，電子計(jì)算機(jī)在解決如組合優(yōu)化問(wèn)題以及工程領(lǐng)域復(fù)雜問(wèn)題時(shí)已經(jīng)不能滿足需要?？茖W(xué)家們經(jīng)過(guò)努力探索，一種利用DNA進(jìn)行計(jì)算的DNA計(jì)算機(jī)應(yīng)運(yùn)而生。DNA分子計(jì)算具有高信息度，高并行性的特點(diǎn)，使得DNA計(jì)算機(jī)在計(jì)算速度及存儲(chǔ)容量上擁有絕對(duì)的優(yōu)勢(shì)。

分子信標(biāo)是一種核酸探針，它是由圓形的分子識(shí)別區(qū)，莖桿和連接熒光素及熒光淬滅分子的連接臂三個(gè)部分組成，能將核酸的序列結(jié)構(gòu)信息轉(zhuǎn)變?yōu)闊晒庑盘?hào)，具有較高的靈敏度和選擇性[1]?；诜肿有艠?biāo)的DNA模型是由殷志祥等在2003年首次提出的[2]。分子信標(biāo)DNA計(jì)算模型是對(duì)可滿足性問(wèn)題的約束變量進(jìn)行編碼，放置在分子信標(biāo)的識(shí)別區(qū)，通過(guò)識(shí)別區(qū)和靶序列雜交，根據(jù)莖桿是否被破壞而線性展開(kāi)判斷可滿足性問(wèn)題的的子句是否滿足。具體生化反應(yīng)如圖1所示。

1 全錯(cuò)位排列問(wèn)題的數(shù)學(xué)模型

全錯(cuò)位排列問(wèn)題又稱為“裝錯(cuò)信封問(wèn)題”，由Danid Bernoulli提出來(lái)的。描述的是n封不同的信全部錯(cuò)裝到n個(gè)不同的信箱的裝法有幾種。此問(wèn)題又稱為匹配問(wèn)題或不動(dòng)點(diǎn)排列問(wèn)題，是組合優(yōu)化中一個(gè)重要的問(wèn)題[3]。用數(shù)學(xué)的語(yǔ)言描述為:集合{1,2，… ,n}的全錯(cuò)位排列是指沒(méi)有一個(gè)數(shù)字在它自然數(shù)序上，即ij≠j(1≤j≤n)[4]。該問(wèn)題的一般解法是利用遞歸關(guān)系求解或真假值行列式求解等。下面給出的DNA計(jì)算模型以含有3個(gè)元素的集合{1,2,3}的錯(cuò)排問(wèn)題為例。

圖1 分子信標(biāo)作用示意圖

2 全錯(cuò)位排列問(wèn)題的分子信標(biāo)模型的滿足性問(wèn)題。

經(jīng)過(guò)分析，可發(fā)現(xiàn)問(wèn)題存在3個(gè)原子命題[5]：

(1)x:數(shù)字1排在第二個(gè)位置上；

(2)y:數(shù)字2排在第一個(gè)位置上；

(3)z:數(shù)字3排在第一個(gè)位置上。

(1)數(shù)字1在第二個(gè)位置上，則數(shù)字3不在第二個(gè)位置上；

(2)數(shù)字2在第一個(gè)位置上，則數(shù)字3不在第一個(gè)位置上；

(3)數(shù)字1在第三個(gè)位置上，則數(shù)字2不在第三個(gè)位置上。

則問(wèn)題轉(zhuǎn)化為如下公式

(1)

2.1 算法設(shè)計(jì)

(1)基本算法[6]

步驟1：列出范式所含變量取值為0，1的所有可能的組合。

步驟2：利用范式的第一個(gè)項(xiàng)，排除不滿足該項(xiàng)的0,1組合。

步驟3：對(duì)滿足該范式的0,1組合進(jìn)行標(biāo)記。

步驟4：重復(fù)進(jìn)行步驟2、步驟3，直到范式中所有的項(xiàng)都被檢查完畢為止。

步驟5：讀出滿足該范式的所有0,1組合。如果存在，說(shuō)明該范式是可滿足的。反之，如果不存在，則說(shuō)明該范式是不可滿足的。

(2)生物算法

步驟1：制作(雜交)表示一個(gè)給定范式包含變量取值為0,1的所有可能組合的分子信標(biāo)。

步驟2：通過(guò)分子信標(biāo)的識(shí)別區(qū)在被其互補(bǔ)的鏈雜交時(shí)產(chǎn)生的張力拉開(kāi)分子信標(biāo)的莖桿而產(chǎn)生的熒光判斷不滿足范式中的第一項(xiàng)的分子信標(biāo)。

步驟3：加熱解鏈(對(duì)于步驟2已經(jīng)判斷為不滿足的分子信標(biāo)不在考慮)，清洗掉所有雜交的補(bǔ)。然后進(jìn)行退火，使得已經(jīng)打開(kāi)的分子信標(biāo)再次復(fù)位。

步驟4：重復(fù)進(jìn)行步驟2步驟3，直到范式中的所有項(xiàng)都被檢查完為止。

步驟5：讀出不滿足該范式的0,1組合，從而可以得到滿足該范式的0,1組合。如果存在，說(shuō)明該范式是可滿足的。反之，如果不存在，則說(shuō)明該范式是不可滿足的。

2.2 編碼和生物操作

對(duì)于含有3個(gè)變?cè)獂,y,z和3個(gè)子式的公式(1)的滿足性問(wèn)題，將求解過(guò)程分為以下五步[7]：

編碼如下圖：

x:TTGGACCAy:TGGTATGGz:TCTCAGAG

x′:AACCTGGTy′:ACCATACCz′:AGAGTCTC

圖2 表示所有解的分子信標(biāo)示意圖

(3)對(duì)第二步的產(chǎn)物加熱，使得雙鏈解開(kāi)并清洗，清洗后再退火，使得打開(kāi)的分子信標(biāo)的莖桿再次雜交形成雙鏈結(jié)構(gòu)，從而形成與上一步相同的分子信標(biāo)，對(duì)于已經(jīng)判定為不滿足條件的分子信標(biāo)就不再考慮。

3 小結(jié)

本文給出了組合優(yōu)化問(wèn)題中一個(gè)重要的問(wèn)題全錯(cuò)位排列問(wèn)題的基于分子信標(biāo)的DNA計(jì)算模型。通過(guò)將問(wèn)題的求解轉(zhuǎn)化為求解可滿足性問(wèn)題的解，使得求解簡(jiǎn)單方便，減少錯(cuò)誤的出現(xiàn)。DNA計(jì)算作為一種新型求解模式，值得我們向更深層次的方向繼續(xù)探索。

[1] 馬立人，蔣中華.生物芯片[M].北京：化學(xué)工業(yè)出版社，1999:1-15.

[2] 殷志祥,張風(fēng)月，許進(jìn).基于分子信標(biāo)的DNA計(jì)算[J].生物數(shù)學(xué)學(xué)報(bào)，2003,18(4)：497-501.

[3] 劉建軍，劉芹英. 歐拉對(duì)經(jīng)典組合學(xué)的貢獻(xiàn)[J].自然科學(xué)史研究，2003,22(4)：361-367.

[4] 孫俠，殷志祥，許進(jìn). 全錯(cuò)位排列問(wèn)題的一種改進(jìn)的表面的DNA計(jì)算模型[J].生物數(shù)學(xué)學(xué)報(bào)，2012,27(2)：297-301.

[5] 孫俠，殷志祥，張家秀.全錯(cuò)位排列問(wèn)題的基于表面的DNA計(jì)算模型[J].生物數(shù)學(xué)學(xué)報(bào)，2009,24(3)：513-517.[6] 殷志祥，許進(jìn). 分子信標(biāo)芯片計(jì)算在0-1整數(shù)規(guī)劃問(wèn)題中的應(yīng)用[J].生物數(shù)學(xué)學(xué)報(bào)，2007,22(3)：559-564.

[7] 殷志祥.圖與組合優(yōu)化中的DNA計(jì)算[M].北京：科學(xué)出版社，2004:74-86.

A DNA Computing Method on the Molecular Beacon for Error Permutation Problems

NIE Qian, YIN Zhi-xiang

(School of Science, Anhui University of Science and Technology, Huainan Anhui 232001, China)

Error permutation problem is an important problem in combinatorial mathematics. In this paper, the problem was transformed into a normal form, and the SAT problem was solved by using molecular beacon. Code for molecular beacon, the analysis of the stress on the recognition region of molecular beacon was carried out by the complementary hybridization. The stem length of the molecular beacon was designed. When the identification area was complementary hybridization, the stems were broken and open with fluorescence, so as to give another DNA computing model for error permutation problems.

the error permutation problem; molecular beacon; DNA computing

2016-04-28

國(guó)家自然科學(xué)基金資助項(xiàng)目(61170172)

聶茜(1992-)，女，安徽亳州人，在讀碩士，研究方向：DNA計(jì)算。

TP301.6

A

1672-1098(2016)06-0052-03