利用雙鏈DNA 編碼節點和質粒求解的有向Hamilton 路徑問題

沈成才 甄 濤 廖 峰

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

0 前言

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

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

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

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

1 Hamilton 路徑的DNA 算法及算法實現

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

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

1）產生經歷有向圖節點的所有路徑。

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

3）保留只有n 個節點的路徑。

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

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

1.2 算法及實現

1.2.1 編碼設計 用30 bp 的DNA 雙鏈進行編碼；對關聯的各條邊編碼，取前節點的后半段序列作為邊的前半段編碼，取后節點的前半段序列作為邊的后半段編碼；將編碼的各邊通過化學合成法合成。

例如頂點①的編碼為TATCGGATCGCGATC

ATAGCCTAGCGCTAG

頂點③的編碼為GCTATTCGAGACGTC

CGATAAGCTCTGCAG

頂點④的編碼為GGCTAGGTACGATCG

CCGATCCATGCTAGC

例如：各邊的編碼

①—③GGATCGCGATCGCTA

CTAGCGATAAGCTCT

③—④TTCGAGACGTCGGCT

GCAGCCGATCCATGC

①—③—④

GGATCGCGATCGCTATTCGAGACGTCGGCT

CTAGCGATAAGCTCTGCAGCCGATCCATGC

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

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

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

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

2 算法分析與討論

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

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