分子信標在一類特殊的整數(shù)規(guī)劃問題中的應用

徐如解, 殷志祥, 唐 震, 楊 靜, 崔建中, 王夕遠

(1.安徽理工大學 數(shù)學與大數(shù)據(jù)學院,安徽 淮南 232001; 2.上海工程技術大學 數(shù)理與統(tǒng)計學院,上海 201620; 3.安徽理工大學 電氣與信息工程學院,安徽 淮南 232001; 4.淮南聯(lián)合大學 計算機系,安徽 淮南 232001)

隨著科技的發(fā)展,在應對海量的數(shù)據(jù)信息處理時,傳統(tǒng)計算已無法滿足要求,人們不得不開始探索新型的計算領域。自文獻[1]提出利用DNA計算解決有向Hamilton路徑以來,DNA計算受到越來越多研究人員的關注;文獻[2-4]介紹了幾種不同的DNA計算模型，著重介紹了DNA計算的廣泛應用性;文獻[5]利用DNA折紙術建立了動態(tài)與非門計算模型;文獻[6]利用DNA折紙術和雜交鏈式反應構建了一種新的求解背包問題計算模型。

分子信標是一種熒光標記的寡核苷酸鏈,通常用作光學探針，具有高靈敏度、易操作以及低檢測成本等優(yōu)點,因此廣泛地應用于DNA計算中。文獻[7]首次建立分子信標探針,分子信標探針作為一種新型的熒光探針廣泛地應用于實時PCR檢測[8]、熒光生物傳感器[9]及最大匹配問題等[10];文獻[11-13]介紹了分子信標在求解0-1整數(shù)規(guī)劃問題、臨床檢測凝血酶以及生物熒光的IFN-小波沖擊檢測方法中的應用,并指出利用分子信標模型求解此類問題具有高信息量和易操作化等優(yōu)點。

整數(shù)規(guī)劃問題是數(shù)學規(guī)劃問題中的一個重要分支,它要求全部或部分決策變量取值為整數(shù)，廣泛應用于多種問題,如線路設計、背包問題、分派問題等。文獻[14-17]介紹了幾種求解整數(shù)規(guī)劃問題最優(yōu)解的計算模型,這些模型的提出進一步說明了DNA計算獨特的優(yōu)勢;文獻[18]利用DNA折紙術完成了對一類特殊的整數(shù)規(guī)劃問題的求解,該方法具有高度的容錯性。

本文設計了一種固定在金(Au)表面上的分子信標模型,用于求解一類特殊的整數(shù)規(guī)劃問題。該模型將變量映射成Au表面上的分子信標,以不同的輸入鏈表示變量不同的取值,并根據(jù)熒光信號的顏色和明滅來展示和檢測規(guī)劃問題的結果。

1 分子信標和特殊整數(shù)規(guī)劃問題

1.1 分子信標模型

分子信標是一種熒光標記的寡核苷酸鏈，一般由環(huán)狀區(qū)、莖干區(qū)、熒光基團和淬滅基團3個部分組成。在分子信標的莖環(huán)結構中,環(huán)一般包含有15～30個脫氧核糖核苷酸,作為識別區(qū)與靶分子序列發(fā)生堿基互補配對;莖一般包含5～7個脫氧核糖核苷酸,并且相互配對形成莖的結構,同時,在3′端包含一個猝滅基團,在5′端包含一個熒光基團。

具體過程如圖1所示。

當維持發(fā)夾結構時,猝滅基團-熒光基團靠近會阻斷熒光信號的釋放;當檢測到互補的DNA靶分子時,DNA靶分子與分子信標中的識別區(qū)發(fā)生堿基互補配對,致使分子信標的發(fā)夾結構打開,熒光基團不再受猝滅基團的影響,從而出現(xiàn)熒光信號。

1.2 特殊的整數(shù)規(guī)劃問題

整數(shù)規(guī)劃問題是數(shù)學規(guī)劃的一個重要分支,下面給出整數(shù)規(guī)劃的一般形式。

max(min)u=c1x1+c2x2+…+cnxn;

(1)

其中:max(min)u為整數(shù)規(guī)劃問題的目標函數(shù);大括號中的所有式子是整數(shù)規(guī)劃的約束條件。對于約束條件中的bi,在計算過程中可以看作bi>0。

當bi<0時,不等式兩邊同時乘以-1,就能夠使得bi成為大于0的數(shù)。

本文基于分子信標的作用機制,對下述一類特殊的整數(shù)規(guī)劃問題給出了一種新的求解算法。

max(min)u=c1x1+c2x2+…+cnxn;

(2)

下面給出該類特殊整數(shù)規(guī)劃問題的推導過程。(3)式給出整數(shù)規(guī)劃中變量x取值分別為-1、0、1的一般形式:

max(min)u=c1x1+c2x2+…+cnxn；

(3)

對(3)式中的任意一個約束條件,as1x1+as2x2+…+asnxn≤(=,≥)bs,s∈[1,m],如果令xj=xj1,j∈[1,n],那么(3)式中的任意一個約束條件都可以分解為:

max(min)u=c1x1+c2x2+…+cnxn;

(4)

其中：當asj>0時,λasj=1;當asj=0時,λasj=0;當asj<0時,λasj=-1。這個分解形式中,系數(shù)|asj|≠0,1變量可以分解成|asj|個相等的變量xs1,xs2,…,xs|asj|。且系數(shù)λasj的存在可以保證系數(shù)asj在分解前后正負符號不變。由此分解得到一個特殊的整數(shù)規(guī)劃問題。

max(min)u=c1x1+c2x2+…+cnxn;

(5)

2 分子信標求解特殊整數(shù)規(guī)劃問題

2.1 固定在Au表面上的分子信標模型的構建

根據(jù)分子信標的作用原理,本文提出了一種固定在Au表面的分子信標模型。該模型中,Au表面用于固定分子信標鏈,并且取代了分子信標3′端處的猝滅基團,這是由于Au表面對某些熒光基團具有猝滅能力[19]。3種DNA分子鏈的設計及其具體的反應原理如圖2所示。

從如圖2a可以看出,分子信標是一個DNA發(fā)夾結構,組成部分為:5′-a-b-a*-3′,其中區(qū)域b是分子信標的識別區(qū)域,區(qū)域a和a*堿基互補配對形成分子信標的莖。在莖的5′端連接有一個二硫化物(S),莖的3′端連接有綠色的熒光素(λem=520 nm)。輸入鏈IA是DNA單鏈,組成部分為:3′-a*-b*-a*-5′。輸入鏈IB也是DNA單鏈,組成部分為:3′-a-b*-a-5′。在DNA鏈的3′端帶有一個Cy5(一種紅色熒光,λem=694 nm),且輸入鏈IB的5′端攜帶有分子信標莖3′端綠色熒光素的猝滅基團。同時,a-a*、b-b*遵循沃森克里克堿基互補配對原則,因此輸入鏈IA和IB都可以打開分子信標的發(fā)夾結構。

從如圖2b可以看出,當沒有輸入鏈IA和IB存在時,信標分子3′端存在的綠色熒光基團仍然停留在Au表面附近,此時沒有熒光信號產生,代表變量取值為0;當輸入鏈IA存在時,分子信標將會打開發(fā)夾結構。此時分子信標3′端的綠色熒光基團遠離Au表面,從而釋放綠色熒光信號,代表變量取值為1;當輸入鏈IB存在時,分子信標將會打開發(fā)夾結構。

輸入鏈IB的5′端的猝滅基團與分子信標3′端的綠色熒光基團結合,綠色熒光猝滅,從而只能觀察到來自輸入鏈IB上Cy5的紅色熒光信號,代表變量取值為-1。

根據(jù)上述固定在Au表面的分子信標模型反應示意圖,本文設計了一種固定在Au表面的分子信標模型,用于求解(2)式這一類特殊的整數(shù)規(guī)劃問題。具體思路是:首先將約束條件中的n個變量x1,x2,…,xn設計成n種分子信標固定在Au表面上。其次對于任意一個變量xi(i=1,2,…,n),設計出2種不同的輸入鏈IAi和IBi,通過添加不同的輸入鏈IAi和IBi來表示變量的不同取值。即當xi=0時,不添加輸入鏈IAi和IBi,無熒光信號產生;當xi=1時,向試管中添加輸入鏈IAi,試管中有綠色熒光信號產生;當xi=-1時,向試管中添加輸入鏈IBi,試管中有紅色熒光信號產生。最后根據(jù)熒光信號的結果來判斷解的可行性。以約束條件x1+x2+x3≥2為例,如圖3所示。圖3中,i=1,2,3。約束條件中有3個變量,因此在Au表面上固定3個分子信標,分別表示變量x1、x2、x3,當變量x1、x2、x3分別取0,1,-1時,向試管中加入輸入鏈IA2和IB3,有一個紅色熒光和一個綠色熒光信號產生,即輸出結果為0(≤2),因此(0,1,-1)不是約束條件x1+x2+x3≥2的可行解。

綜上所述,對于含有n個變量、m個約束方程的整數(shù)規(guī)劃問題,給出(2)式這類整數(shù)規(guī)劃計算模型的具體算法步驟。

(1) 根據(jù)問題中n個變量,每個變量取-1、0或1,給出問題的所有可能解(x1,x2,…,xn)的組合,共3n個可能解,取3n個試管。

(2) 根據(jù)第1個約束條件中n個變量,首先設計出n種分子信標固定在同一個Au表面上,并置于試管中;然后根據(jù)可能解(x1,x2,…,xn)的取值,向試管中加入不同的輸入鏈。具體地,對于任一個變量xi(i=1,2,…,n),通過添加不同的輸入鏈IAi和IBi表示變量的不同取值。即當xi=0時,不添加輸入鏈IAi和IBi;當xi=1時,向試管中添加輸入鏈IAi;當xi=-1時,向試管中添加輸入鏈IBi。

最后根據(jù)熒光信號判斷出第一個約束條件的可行解。

(3) 重復步驟(2),直到完成規(guī)劃問題中所有約束條件,最后保留的可行解就是滿足所有約束條件的可行解。

(4) 分別計算出各可行解對應的目標函數(shù)值并進行比較,最終判斷出最優(yōu)解。

2.2 實例分析

下面以一個包含3個變量、3個子句的整數(shù)規(guī)劃問題來介紹具體的操作過程。

minz=2x1+3x2+2x3;

(6)

(1) 問題中含有3個變量,共有33=27個可能解。分別為:(-1,-1,-1)、(-1,-1,0)、(-1,-1,1)、(-1,0,-1)、(-1,0,0)、(-1,0,1)、(-1,1,-1)、(-1,1,0)、(-1,1,1)、(0,-1,-1)、(0,-1,0)、(0,-1,1)、(0,0,-1)、(0,0,0)、(0,0,1)、(0,1,-1)、(0,1,0)、(0,1,1)、(1,-1,-1)、(1,-1,0)、(1,-1,1)、(1,0,-1)、(1,0,0)、(1,0,1)、(1,1,-1)、(1,1,0)、(1,1,1)。取27個試管進行接下來的生物操作。

(2) 對第1個約束條件x1+x2+x3≥1,設計出3種編碼不同的分子信標固定在Au表面,分別表示變量x1、x2、x3。對變量x1設計出2種輸入鏈IA1、IB1,對變量x2設計出2種輸入鏈IA2、IB2,對變量x3設計出2種輸入鏈IA3、IB3。

部分可能解(-1,-1,-1)、(-1,0,1)、(1,1,-1)、(1,1,0)的示意圖如圖4所示。

對于可能解(-1,-1,-1),向試管中加入輸入鏈IB1、IB2、IB3,試管中出現(xiàn)3個紅色熒光信號,表示輸出結果為-3,小于1,故(-1,-1,-1)不是第1個約束條件的可行解;對于可能解(-1,0,1),向試管中加入輸入鏈IB1、IA3,試管中出現(xiàn)一個綠色熒光和一個紅色熒光信號,表示輸出結果為0,小于1,故(-1,0,1)不是第1個約束條件的可行解;對于可能解(1,1,-1),向試管中加入輸入鏈IA1、IA2、IB3,試管中出現(xiàn)2個綠色熒光和1個紅色熒光信號,表示輸出結果為1,不小于1,故(1,1,-1)是第1個約束條件的可行解;對于可能解(1,1,0),向試管中加入輸入鏈IA1、IA2,試管中出現(xiàn)2個綠色熒光信號,表示輸出結果為2,大于1,故(1,1,0)是第1個約束條件的可行解。27個可能解在第1個約束條件下是否是可行解的情況見表1所列。

由表1可知,滿足第1個約束條件的可行解有10個,分別記為:1(-1,1,1)、2(0,0,1)、3(0,1,0)、4(0,1,1)、5(1,-1,1)、6(1,0,0)、7(1,0,1)、8(1,1,-1)、9(1,1,0)、10(1,1,1)。

表1 27個可能解的輸出結果

(3) 對于第2個約束條件x1+x3≥2,有2個變量,使用步驟(2)中設計的分子信標表示變量x1、x3以及變量x1設計的2種輸入鏈IA1、IB1和變量x3設計的2種輸入鏈IA3、IB3。由于第2個約束條件只含x1、x32個變量,因此只考慮這2個變量。考慮到2(0,0,1)和4(0,1,1);5(1,-1,1)、7(1,0,1)和10(1,1,1);6(1,0,0)和9(1,1,0)中x1、x3變量取值相同。因此只考慮1(-1,1,1)、2(0,0,1)、3(0,1,0)、5(1,-1,1)、6(1,0,0),取值分別為:1(-1,1)、2(0,1)、3(0,0)、5(1,1)、6(1,0)。對于解1(-1,1)向試管中加入輸入鏈IB1、IA3,試管中出現(xiàn)1個紅色熒光和1個綠色熒光信號,表示輸出結果為0;對解2(0,1)向試管中加入輸入鏈IA3,試管中出現(xiàn)1個綠色熒光信號,表示輸出結果為1;對于解3(0,0)向試管中不加入任何鏈,即沒有任何熒光信號,表示輸出結果為0;對于解5(1,1)向試管中加入輸入鏈IA1、IA3,試管中出現(xiàn)2個綠色熒光信號,表示輸出結果為2;對于解6(1,0)向試管中加入輸入鏈IA1,試管中出現(xiàn)一個綠色熒光信號,表示輸出結果為1。

具體操作如圖5所示。

由此可知,在滿足第1個約束條件的可行解中,5(1,1)滿足第2個約束條件。因此,滿足前2個約束條件的可行解為:5(1,-1,1)、7(1,0,1)、10(1,1,1)。由于第3個約束條件不涉及變量x1,僅需考慮x2、x3的取值。x2、x3的取值分別為:5(-1,1)、7(0,1)、10(1,1)。繼續(xù)步驟(2),結果如圖6所示。

對于解5(-1,1)向試管中加入輸入鏈IB2、IA3,試管中出現(xiàn)1個紅色熒光和1個綠色熒光信號,表示輸出結果為0;對于解7(0,1)向試管中加入輸入鏈IA3,試管中出現(xiàn)1個綠色熒光信號,表示輸出結果為1;對于解10(1,1)向試管中加入輸入鏈IA2、IA3,試管中出現(xiàn)2個綠色熒光信號,表示輸出結果為2。

(4) 第5組解(1,-1,1)和第7組解(1,0,1)是滿足所有約束條件的可行解,將可行解帶入目標函數(shù)并進行比較,可求得目標函數(shù)最小值為4。

3 結 論

本文利用分子信標構建了一種固定在Au表面的分子信標模型,該模型用于求解一類特殊的整數(shù)規(guī)劃問題，具有傳統(tǒng)分子信標的優(yōu)點。

(1) 運算過程中沒有對酶的要求,可以降低實驗成本。

(2)利用熒光信號的顏色和明滅判斷解的可行性,可提高檢測結果的準確性和實用性。

(3) 操作簡單,易于實現(xiàn),比一般的計算模型更容易觀察和檢測問題的解。

除此之外,與傳統(tǒng)的分子信標計算模型相比,本文設計的固定在Au表面的分子信標模型具有獨特的優(yōu)勢。首先,利用Au表面不僅可以固定分子信標鏈,而且Au表面對熒光團具有猝滅能力,可以取代猝滅基團,極大程度上降低實驗成本;其次,將分子信標固定在Au表面上,這種設計允許反復清洗過程;最后,之前發(fā)展的分子信標模型一般都用于溶液的檢測,這種方式限制了分子信標在活體生物醫(yī)學研究和生物傳感中大規(guī)模的應用,而本文設計的固定在Au表面的分子信標模型,不僅可以保持分子信標原有的性質不變,而且可用于大規(guī)模的檢測,大大提高了分析效率,更便于應用在疾病監(jiān)測、醫(yī)藥檢測中。進一步的工作可改進該模型使之能夠應用于更一般的整數(shù)規(guī)劃問題。