家庭旅行商問題的三鏈DNA 計(jì)算模型

蔣天懌， 楊 靜

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

長(zhǎng)期以來，人們對(duì)于著名的NP-完全問題——旅行商問題（Traveling Salesperson Problem，TSP）的求解方法進(jìn)行了大量的研究，但家庭旅行商問題（Family Traveling Salesperson Problem，F(xiàn)TSP）是近期才被提出的。2013 年，Moran-Mirabal 等首次提出了FTSP 的定義[1]。2021 年，Bernardino 和Paias 提出了2 種元啟發(fā)式算法來求解FTSP[2]。

1994 年，Adleman 首次利用DNA 計(jì)算方法解決了7 頂點(diǎn)的Hamilton 路徑問題，開拓了DNA 計(jì)算的新紀(jì)元[3]。自1957 年Davies 等報(bào)道三鏈DNA 的存在以來，其就被用來解決一些問題，如背包問題、郵遞員問題等[4-5]。基于此，本文將嘗試?yán)萌淒NA 計(jì)算模型來解決FTSP。

1 三鏈DNA 結(jié)構(gòu)

1957 年，F(xiàn)elsenfield 等發(fā)現(xiàn)1 條人工合成的腺嘌呤核糖核苷酸的均聚物能和2 條人工合成的尿嘧啶核糖核苷酸的均聚物形成三鏈DNA 結(jié)構(gòu)[6]。三鏈在形成或分離過程中，不易錯(cuò)配或形成發(fā)夾結(jié)構(gòu)，且反應(yīng)前的數(shù)據(jù)池中皆為雙鏈，在常溫下即可操作實(shí)現(xiàn)，實(shí)驗(yàn)條件較為簡(jiǎn)單。因此，基于三鏈的DNA 計(jì)算而產(chǎn)生的錯(cuò)誤率和編碼的復(fù)雜度會(huì)大大降低，其可用來研究組合優(yōu)化問題中一些可能的或者可行的計(jì)算模型。

2 FTSP 問題

若使用圖論的語言，F(xiàn)TSP 可以描述如下：在無向完備圖G=（V∪{0}，E）中，0 是原點(diǎn)，V是除了原點(diǎn)0以外的所有頂點(diǎn)的集合，E是不同頂點(diǎn)i與j之間距離的集合，使得d（i，j）＞0，其中頂點(diǎn)i到j(luò)的距離和j到i的距離是一樣的，故d也可以稱為各邊的權(quán)值。在FTSP 中，具有N個(gè)頂點(diǎn)的頂點(diǎn)集合V被劃分為h個(gè)不同的族vk，其中k為族的索引，且vi∩vj=?（i≠j），其表明1 個(gè)族內(nèi)包含多個(gè)頂點(diǎn)，但1 個(gè)頂點(diǎn)只能屬于1 個(gè)族。記nk為各個(gè)族的頂點(diǎn)數(shù)，則頂點(diǎn)數(shù)。給定1 個(gè)有N個(gè)頂點(diǎn)的無向完備圖，需要訪問M（M≤N）個(gè)頂點(diǎn)，給定每個(gè)族mk中需要訪問的頂點(diǎn)個(gè)數(shù)，使得。最終目標(biāo)就是找到訪問M個(gè)頂點(diǎn)數(shù)的最小總路徑的往返。

3 FTSP 的三鏈DNA 算法實(shí)現(xiàn)

基于圖G=（V∪{0}，E），三鏈DNA 計(jì)算模型的算法步驟如下：

步驟1：對(duì)圖G的各點(diǎn)以及弧進(jìn)行精心DNA 編碼，將其所對(duì)應(yīng)的寡聚核苷酸片段充分混合，并加入緩沖液、DNA 連接酶使之進(jìn)行連接反應(yīng)，生成關(guān)于圖G的所有途徑。還需加入大量聚合酶和引物，不斷擴(kuò)增DNA 分子，使所有單雙鏈都以雙鏈的形式存在，以增加鏈的穩(wěn)定性。對(duì)反應(yīng)后的產(chǎn)物進(jìn)行聚合酶鏈?zhǔn)椒磻?yīng)（Polymerase Chain Reaction，PCR）擴(kuò)增，讓那些起止于原點(diǎn)的鏈成指數(shù)倍增加。保留這些DNA 鏈，進(jìn)行純化處理并分離，把最終所得雙鏈作為初始數(shù)據(jù)池。

步驟2：在每個(gè)頂點(diǎn)補(bǔ)鏈的單鏈5′端添加1 個(gè)聚酯纖維，再標(biāo)記生物素。使這些單鏈和抗原蛋白質(zhì)在含有腺苷5′-（3-硫代三磷酸）四鋰鹽（Adenosine5′-3-thiotriphosphate tetralithiumsalt，ATPγS）溶液里混合，生成核蛋白細(xì)狀體，作為模板，構(gòu)造DNA 探針。

步驟3：將頂點(diǎn)探針混合到數(shù)據(jù)池中，將與對(duì)應(yīng)雙鏈結(jié)合生成3 鏈。利用分離操作將沒有生成3 鏈的雙鏈除去，并利用鏈（霉）親和素的高度親和力將所有含有此頂點(diǎn)的3 鏈分離出來，再形成雙鏈，此時(shí)數(shù)據(jù)池中的雙鏈一定含有此頂點(diǎn)。

步驟4：根據(jù)約束條件，重復(fù)步驟2 和3，對(duì)數(shù)據(jù)池中的鏈逐步篩選，可得所需的DNA 鏈，即可行解。

步驟5：對(duì)步驟4 產(chǎn)物進(jìn)行瓊脂糖漿凝膠電泳。切割出長(zhǎng)度最短的鏈，并進(jìn)行測(cè)序，選出代表最優(yōu)解的鏈，輸出結(jié)果，即FTSP 的最優(yōu)旅行路線。

4 實(shí)例分析

4.1 實(shí)例

為了說明三鏈DNA 計(jì)算模型的有效性和正確性，本文給出了1 個(gè)小規(guī)模實(shí)例burma14，該實(shí)例來自TSPLIB，各城市分布坐標(biāo)如圖1 所示。其中N=13，n1=4，n2=5，n3=4，m1=m2=m3=2，0→1→2→13→6→12→7→0 為滿足條件的可行路線。接下來就根據(jù)前文所提到的算法實(shí)現(xiàn)所對(duì)應(yīng)的生化操作。

圖1 無向完備示意圖G

4.2 實(shí)例操作

1）DNA編碼

為規(guī)范算法表達(dá)，其編碼方式如下：

對(duì)各點(diǎn)進(jìn)行等碼長(zhǎng)編碼：

其中qk是用來區(qū)分不同族的頂點(diǎn)，令以原點(diǎn)為起點(diǎn)的編碼為#A0B0，以原點(diǎn)為終點(diǎn)的編碼為A0B0#。

對(duì)弧進(jìn)行不等碼長(zhǎng)編碼：

2）生成初始數(shù)據(jù)

利用上述編碼生成初始數(shù)據(jù)，首先通過幾步生化反應(yīng)得到從原點(diǎn)開始并返回原點(diǎn)的解：

Step 1生成從原點(diǎn)開始并返回原點(diǎn)的初始數(shù)據(jù)（1-1）（1-2）（1-3）（1-4）（1-5）（1-6）（1-7）（1-8）Merge（P，Q）Linkaging（P）Amplification（P）PCR（P，{#A0B0，A0B0#}）Separation（P，{#A0B0}，T0）Discard（P）Separation（P，{A0B0#}，T0）Discard（T0）；

操作（1-1）是將含有點(diǎn)vi和弧vivj的大量寡聚核苷酸片段分別儲(chǔ)存在管P和管Q，并混合，即P=P∪Q且Q=?。（1-2）和（1-3）表示加入緩沖液、引物、聚合酶等，生成穩(wěn)定結(jié)構(gòu)的雙鏈DNA。（1-4）是對(duì)反應(yīng)后的產(chǎn)物進(jìn)行PCR 擴(kuò)增，使得起止于原點(diǎn)#A0B0、A0B0#的DNA 鏈成指數(shù)倍增加。操作（1-5）—（1-8）則表明進(jìn)行純化處理，先將含有#A0B0的DNA鏈保留在臨時(shí)管T0中，丟棄管P，再將臨時(shí)管T0中含有A0B0#的DNA鏈保留在管P中，丟棄臨時(shí)管T0。至此，已將所有起止于原點(diǎn)，以雙鏈形式存在的DNA 鏈為初始數(shù)據(jù)，并將其保留在管P中，即管P中包含了圖G的所有解。

3）篩選經(jīng)過所有族的解

Step 2篩選出經(jīng)過所有族的解（2-1）（2-2）（2-3）（2-4）For k=1 to k=h Separation（P，{qk}，T0）；Discard（P）；Copy（T0，P）；Discard（T0）；End

此時(shí)有些鏈不滿足約束條件，因此，Step 2 利用For 循環(huán)進(jìn)一步處理：（2-1）和（2-2）表示將的探針放入初始數(shù)據(jù)池中，與含有qk的雙鏈生成3 鏈，并將其存儲(chǔ)到臨時(shí)管T0中。與磁珠混合后，得到含有qk的雙鏈DNA，（2-3）—（2-4）則是純化處理。重復(fù)此步驟h次后，可以篩選出未通過所有族的解并剔除。

4）篩選每個(gè)族經(jīng)過2 個(gè)點(diǎn)的解

類似地，構(gòu)造各個(gè)頂點(diǎn)vi的探針，并生成3 鏈。如Step 3 所示是1 個(gè)嵌套循環(huán)。在內(nèi)循環(huán)中，（3-1）和（3-2）是將管P中生成關(guān)于Ai qk Bi三鏈的雙鏈存儲(chǔ)到臨時(shí)管T0中，如果在該雙鏈中存在2 處三鏈結(jié)構(gòu)，則表明該族經(jīng)過了2 個(gè)頂點(diǎn)。然后將3 鏈分離，重新形成雙鏈，（3-3）和（3-4）是純化處理。重復(fù)h步后，最終管P中的所有雙鏈都經(jīng)過了每個(gè)族的2 個(gè)頂點(diǎn)。

Step 3篩選出每個(gè)族只經(jīng)過2 個(gè)點(diǎn)的解（3-1）For k=1 to k=h For i=1 to i=N Separation（P，{AiqkBi}，T0）；（3-2）（3-3）（3-4）If T0=2 Discard（P）；Copy（T0，P）；Discard（T0）；Else（3-5）Continue；End End

5）篩選經(jīng)過同一頂點(diǎn)1 次的解

由于頂點(diǎn)可能被多次訪問，還需進(jìn)一步篩選。運(yùn)用上一步所構(gòu)造的探針，以每個(gè)頂點(diǎn)為單位，將管P中生成關(guān)于Ai qk Bi的三鏈存儲(chǔ)到臨時(shí)管T0中，如果存在2 處三螺旋結(jié)構(gòu)，表明同一頂點(diǎn)經(jīng)過2次，將臨時(shí)管T0丟棄；否則，重新形成雙鏈，并進(jìn)行純化處理。重復(fù)N 次后，可篩除經(jīng)過同一頂點(diǎn)2 次的解。

6）選出最優(yōu)解

經(jīng)過上述步驟，已刪除所有不符合約束條件的解，只需在所剩的解中選擇最優(yōu)解。對(duì)其進(jìn)行凝膠電泳，切割下長(zhǎng)度最短的雙鏈并測(cè)序，即可找到最優(yōu)解的DNA鏈：#A0B0w0，1A1q1B1w1，2A2q1B2w2，13A13q3B13w13，7A7q2B7w7，10A10q3B10w10，8A8q2B8w8，0A0B0#，與之對(duì)應(yīng)的最優(yōu)路線為：0→1→2→13→7→10→8→0。

4.3 復(fù)雜度評(píng)估

步驟1 和步驟2 分別是編碼設(shè)計(jì)和生成初始數(shù)據(jù)，而步驟3 到步驟5 則是在逐步篩選可行解，最后是選出最優(yōu)解。綜上所述，以上6 步的總復(fù)雜度為：

為了解決FTSP，本文提出了一種簡(jiǎn)單的編碼規(guī)則和并行能力較強(qiáng)的三鏈DNA 計(jì)算模型，可在O（Nh）復(fù)雜度內(nèi)找到最優(yōu)解。三鏈模型在理論層面已經(jīng)解決了不少多項(xiàng)式復(fù)雜程度的非確定性問題（Non-deterministic Polynomial，NP）問題，隨著生物技術(shù)的發(fā)展和完善，未來可使其成為解決更復(fù)雜大數(shù)據(jù)問題的方法之一，進(jìn)一步提高模型的有效性和通用性。