利用雙鏈DNA 編碼節(jié)點(diǎn)和質(zhì)粒求解的有向Hamilton 路徑問題

沈成才 甄 濤 廖 峰

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

0 前言

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

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

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

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

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

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

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

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

2）只保留起點(diǎn)是vin，終點(diǎn)是vout 的路徑。

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

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

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

1.2 算法及實(shí)現(xiàn)

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

例如頂點(diǎn)①的編碼為TATCGGATCGCGATC

ATAGCCTAGCGCTAG

頂點(diǎn)③的編碼為GCTATTCGAGACGTC

CGATAAGCTCTGCAG

頂點(diǎn)④的編碼為GGCTAGGTACGATCG

CCGATCCATGCTAGC

例如：各邊的編碼

①—③GGATCGCGATCGCTA

CTAGCGATAAGCTCT

③—④TTCGAGACGTCGGCT

GCAGCCGATCCATGC

①—③—④

GGATCGCGATCGCTATTCGAGACGTCGGCT

CTAGCGATAAGCTCTGCAGCCGATCCATGC

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

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

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

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

2 算法分析與討論

線性單鏈DNA 合成簡單、操作性強(qiáng)，但是單鏈DNA 穩(wěn)定性差，在反應(yīng)過程中容易發(fā)生錯(cuò)配，產(chǎn)生偽解，且其篩選方法是在擴(kuò)大生成的起點(diǎn)到終點(diǎn)路徑下進(jìn)行，并不能排除其他解，加大了后續(xù)測序難度。與線性DNA 相比，質(zhì)粒DNA 在限制酶剪切之后，又迅速連接成環(huán)狀分子，從而確保計(jì)算過程免受其他酶的干擾，計(jì)算準(zhǔ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é)點(diǎn)和質(zhì)粒DNA，以求獲得最短有向Hamilton 路徑。一方面，通過DNA 雙鏈對節(jié)點(diǎn)編碼，形成有雙鏈DNA 組成的各條有向邊。單鏈DNA 是平末端連接，DNA雙鏈則是黏性末端連接，且穩(wěn)定性好，有助于提高邊與邊的連接效率，減少在路徑生成過程中的分子間錯(cuò)配，從而提高準(zhǔn)確性；另一方面，從起點(diǎn)到終點(diǎn)路徑，先利用相應(yīng)引物進(jìn)行PCR 擴(kuò)增，使對應(yīng)的路徑大量增加，再用凝膠電泳將一些非起點(diǎn)到終點(diǎn)路徑而與目的片段相同大小的路徑分離出來，加大了測序難度。而利用質(zhì)粒進(jìn)行篩選時(shí)，質(zhì)?？梢蕴禺愋缘暮推瘘c(diǎn)到終點(diǎn)的路徑結(jié)合，然后對目的大小的重組質(zhì)粒進(jìn)行凝膠電泳分離，再進(jìn)一步擴(kuò)增，這樣便排除了非起點(diǎn)到終點(diǎn)路徑，可以有目的性地對可行解進(jìn)行集中分離，避免標(biāo)本在擴(kuò)增中的浪費(fèi)，使篩選效率得以提高。