地圖著色問題的DNA計算

馬　瑩，方　歡

安徽理工大學理學院,安徽淮南，232001

?

地圖著色問題的DNA計算

馬瑩，方歡

安徽理工大學理學院,安徽淮南，232001

提出了將地圖著色問題轉化為頂點著色問題，然后把頂點著色問題轉化為求最大獨立集問題。最大獨立集問題的解法采用改進的粘貼DNA計算，即全信息化的DNA粘貼計算。DNA粘貼計算設計了主鏈和存儲鏈，而且在生物計算中采用并行處理。最后給出了一個實例,詳細說明了地圖著色問題的解法，得出了最終的解。

DNA計算；粘貼計算；地圖著色問題；頂點著色；最大獨立集

1994年，Adleman首次用DNA計算解決有向圖的哈密頓問題[1]，此后許多研究者對DNA計算進行研究。粘貼模型是由Roweis等人于1996年提出的一種DNA計算模型[2]，給出了圖的最大團與最大獨立集粘貼DNA計算模型[3]，特別是許進教授的文獻[4-5]對DNA粘貼計算的研究有很大的意義。文獻[6]把地圖著色問題轉化成可滿足性問題，并采用多級分離裝置來實現，文獻[7]采用分子信標表面技術實現地圖著色問題的DNA計算，文獻[8]給出了圖的最小頂點覆蓋問題的DNA計算，文獻[9] 給出了最大匹配問題的粘貼DNA算法。文獻[10] 用微流控DNA計算解決圖著色問題的DNA算法。本文提出了全信息化的DNA粘貼計算模型。

1　基于DNA計算的粘貼模型

1.1粘貼模型

粘貼模型的DNA分子的編碼是一種單鏈和雙鏈混合的序列，存儲混合物由兩種類型的單鏈組成：一種是存儲鏈，另一種是粘貼鏈。一個存儲鏈含有K個不重疊區域的單鏈DNA分子，其中不重疊區域有M個堿基；粘貼鏈也是單鏈DNA分子，可以設計M個堿基的粘貼鏈與存儲鏈中的DNA單鏈分子恰好構成互補。……