沈成才 甄 濤 廖 峰

（北京師范大學(xué)克拉瑪依附屬學(xué)校 新疆克拉瑪依 83400）

0 前言

DNA計算以DNA 堿基序列作為信息編碼的載體，利用現(xiàn)代分子生物學(xué)技術(shù)，在試管內(nèi)控制酶的作用下進行DNA 的序列反應(yīng)，作為實現(xiàn)運算的過程，以反應(yīng)前DNA 序列作為輸入數(shù)據(jù)，完成運算后，從反應(yīng)后的產(chǎn)物及溶液中得到全部的解空間。由于DNA 計算具有高度的并行性和較大的存儲量，可以大規(guī)模并行處理和組合運算，解決算法研究領(lǐng)域的某些難解問題，如Hamilton 路徑問題（Hamilton Path Problem，HPP）。Hamilton 路徑是指在有向圖中開始于起點，結(jié)束于終點，且一次性經(jīng)過所有節(jié)點的最短路徑。用寡聚核苷酸片段編碼圖的頂點和邊，放入溶液進行生化反應(yīng)，生成表示隨機路徑的DNA，再通過PCR、凝膠電泳、親和純化等操作，完成解的產(chǎn)生和最終解的分離，如果有經(jīng)過圖的所有頂點一次且只經(jīng)過一次的最短DNA 序列，則得到Hamilton 路徑，否則就不存在。Hamilton 路徑在互聯(lián)網(wǎng)、交通網(wǎng)、通訊網(wǎng)、集成電路、DNA 計算機及國民經(jīng)濟各行各業(yè)等都有重要的應(yīng)用前景［1］。

Adleman 利用DNA 編碼等分子生物技術(shù)解決了有向圖中的Hamilton 路，Nobuhiko Morimoto 等給出了該問題的表面計算方式，Masanori Arita 等基于雙鏈DNA 比單鏈DNA 結(jié)構(gòu)穩(wěn)定且不易形成二級結(jié)構(gòu)，設(shè)計了一種雙鏈DNA 分子的HPP 模型，劉文斌、許進提出賦權(quán)Hamilton 路徑的DNA計算模型［2］。高琳等人通過編碼合成ssDNA（Single Strand DNA）片段研究基于分子生物技術(shù)的有向最短哈密爾頓路問題的DNA 算法，也有一些研究基于質(zhì)粒DNA 計算模型的DNA 計算、Hamilton 圈問題的DNA算法等［3］。

可見，Hamilton 路徑問題的研究大多建立在以單鏈DNA 編碼節(jié)點的方式上。而對于Hamiltion路徑問題，DNA 計算在可行解的生成過程中，錯誤雜交、頂點較多等因素，較多的單鏈寡聚核苷酸片斷可能會形成發(fā)夾結(jié)構(gòu)，產(chǎn)生大量“偽解”，制約模型的應(yīng)用規(guī)模；另外，DNA 計算所應(yīng)用的生物技術(shù)也存在著誤差，例如PCR 技術(shù)中的聚合酶的堿基錯配率，隨著循環(huán)次數(shù)的增加，帶有錯配堿基的拷貝數(shù)增加，偶爾一些非酶的非受控制的支路的反應(yīng)，甚至包括DNA 鏈的動力分解，均增大了最優(yōu)解輸出的難度［4］。

為了減少錯配的可能，提高篩選Hamilton 最短路徑的有效性，本研究以具有黏性末端的改造質(zhì)粒DNA 作為框架，利用雙鏈DNA 編碼節(jié)點，對生成的各種路徑進行篩選，保留Hamilton 最短路徑。

1 Hamilton 路徑的DNA 算法及算法實現(xiàn)

1.1 問題描述 設(shè)圖G 是一個有向圖，其指向輸入和輸出頂點分別為vin 和vout。如果一條從vin 到vout 路包含G 的每個頂點一次且僅有一次的一條有向路P 稱為有向Hamilton 路問題，簡稱HPP 問題。

有向Hamilton 問題的非確定性解法步驟如下：

1）產(chǎn)生經(jīng)歷有向圖節(jié)點的所有路徑。

2）只保留起點是vin，終點是vout 的路徑。

3）保留只有n 個節(jié)點的路徑。

4）保留那些進入有向圖中所有節(jié)點至少一次的路徑。

5）如果有任何路徑保留下來，則存在Hamilton 路徑。否則，不存在［5］。

1.2 算法及實現(xiàn)

1.2.1 編碼設(shè)計 用30 bp 的DNA 雙鏈進行編碼；對關(guān)聯(lián)的各條邊編碼，取前節(jié)點的后半段序列作為邊的前半段編碼，取后節(jié)點的前半段序列作為邊的后半段編碼；將編碼的各邊通過化學(xué)合成法合成。

例如頂點①的編碼為TATCGGATCGCGATC

ATAGCCTAGCGCTAG

頂點③的編碼為GCTATTCGAGACGTC

CGATAAGCTCTGCAG

頂點④的編碼為GGCTAGGTACGATCG

CCGATCCATGCTAGC

例如：各邊的編碼

①—③GGATCGCGATCGCTA

CTAGCGATAAGCTCT

③—④TTCGAGACGTCGGCT

GCAGCCGATCCATGC

①—③—④

GGATCGCGATCGCTATTCGAGACGTCGGCT

CTAGCGATAAGCTCTGCAGCCGATCCATGC

1.2.2 質(zhì)粒DNA 的構(gòu)建 質(zhì)粒是染色體外能夠獨立復(fù)制，穩(wěn)定遺傳的一種環(huán)狀雙鏈分子，包含復(fù)制子、選擇性記號和克隆位點。根據(jù)Hamilton 路徑的長度，選用容量合適的質(zhì)粒，通常選用PBR322型或PUC 系列載體。利用限制性內(nèi)切酶對質(zhì)粒DNA切割，形成2 個分別與Hamilton 路徑中的起點和終點邊編碼相互補的黏性末端。然后對其進行擴增，測其長度標注為n。由于其具有能和起點邊和終點邊編碼相互補且唯一互補的黏性末端，所以通過質(zhì)?？梢赃x出從起點到終點的所有路徑，排除了其他可能路徑。

1.2.3 路徑生成 使外源DNA 與質(zhì)粒載體發(fā)生一系列連接反應(yīng)，生成各條有向路徑。通過合成擴增大量的編碼片段，可以獲得從起點到終點的所有可能路徑。

1.2.4 電泳分離重組質(zhì)粒 各條路徑會和載體質(zhì)粒發(fā)生結(jié)合而形成閉環(huán)DNA 分子，也有部分載體未發(fā)生結(jié)合而成開環(huán)。可以通過與標準目的重組質(zhì)粒進行電泳條帶對比分析進行篩選，利用瓊脂糖凝膠電泳分離重組質(zhì)粒。

1.2.5 PCR 與測序 通過利用構(gòu)建載體時的限制性內(nèi)切酶對重組質(zhì)粒進行切割；將插入的路徑切割下來，并進行PCR 擴增，有利于進一步篩選。最后，通過對路徑中的堿基序列測定，分離出經(jīng)各節(jié)點一次的路徑，即為最短Hamilton 路徑。

2 算法分析與討論

線性單鏈DNA 合成簡單、操作性強，但是單鏈DNA 穩(wěn)定性差，在反應(yīng)過程中容易發(fā)生錯配，產(chǎn)生偽解，且其篩選方法是在擴大生成的起點到終點路徑下進行，并不能排除其他解，加大了后續(xù)測序難度。與線性DNA 相比，質(zhì)粒DNA 在限制酶剪切之后，又迅速連接成環(huán)狀分子，從而確保計算過程免受其他酶的干擾，計算準確性高且穩(wěn)定。質(zhì)粒始終是雙鏈結(jié)構(gòu)，不會形成發(fā)夾結(jié)構(gòu)，方便切割操作，便于使用凝膠電泳技術(shù)檢測結(jié)果。復(fù)制和轉(zhuǎn)錄過程中，DNA 不被分裂成長的單鏈，而是DNA的少部分被打開并被相關(guān)蛋白質(zhì)周密地控制，阻止無法預(yù)料到的退火形式［6］。

因此，本研究利用雙鏈DNA 編碼節(jié)點和質(zhì)粒DNA，以求獲得最短有向Hamilton 路徑。一方面，通過DNA 雙鏈對節(jié)點編碼，形成有雙鏈DNA 組成的各條有向邊。單鏈DNA 是平末端連接，DNA雙鏈則是黏性末端連接，且穩(wěn)定性好，有助于提高邊與邊的連接效率，減少在路徑生成過程中的分子間錯配，從而提高準確性；另一方面，從起點到終點路徑，先利用相應(yīng)引物進行PCR 擴增，使對應(yīng)的路徑大量增加，再用凝膠電泳將一些非起點到終點路徑而與目的片段相同大小的路徑分離出來，加大了測序難度。而利用質(zhì)粒進行篩選時，質(zhì)?？梢蕴禺愋缘暮推瘘c到終點的路徑結(jié)合，然后對目的大小的重組質(zhì)粒進行凝膠電泳分離，再進一步擴增，這樣便排除了非起點到終點路徑，可以有目的性地對可行解進行集中分離，避免標本在擴增中的浪費，使篩選效率得以提高。