DNA計(jì)算核酸編碼優(yōu)化及算法設(shè)計(jì).pdf

1、DNA計(jì)算是一種以DNA分子作為計(jì)算介質(zhì),以生物化學(xué)反應(yīng)作為計(jì)算工具的一種新型計(jì)算方法。憑借著極大的存儲(chǔ)密度和高度并行性,這種基于生物分子的計(jì)算模式,在求解復(fù)雜的組合優(yōu)化NP完全問題時(shí)顯示出了極大潛力。DNA計(jì)算首先是對核酸序列進(jìn)行編碼,將現(xiàn)實(shí)問題映射到核酸分子上,然后通過生物試驗(yàn)獲得代表問題解的核酸分子。核酸編碼質(zhì)量的優(yōu)劣決定了DNA計(jì)算的效率,核酸編碼數(shù)量的多少?zèng)Q定了DNA計(jì)算可求解問題的規(guī)模,因此核酸編碼是DNA計(jì)算研究中的重要課

2、題。本文研究了DNA計(jì)算中核酸編碼理論及其算法的設(shè)計(jì),主要研究工作如下:
　　(1)DNA計(jì)算中編碼質(zhì)量、編碼數(shù)量、序列長度與DNA計(jì)算的可靠性、有效性、可擴(kuò)充性密切相關(guān),選取適當(dāng)?shù)腄NA編碼約束及約束強(qiáng)度是提高DNA計(jì)算設(shè)計(jì)效率的關(guān)鍵,DNA編碼問題是一個(gè)極具挑戰(zhàn)性的多目標(biāo)組合優(yōu)化問題。
　　本文首先分析了各編碼約束對編碼質(zhì)量的影響,進(jìn)而對DNA編碼的約束條件進(jìn)行歸類。通過將DNA編碼問題和圖的最大獨(dú)立集問題進(jìn)行類比,對D

3、NA編碼問題的復(fù)雜性進(jìn)行了分析。對基于漢明距離和基于最小自由能這兩類DNA編碼方法進(jìn)行了類比和研究,分析了兩類方法限制核酸非特異性雜交的完備性及計(jì)算量,為DNA計(jì)算編碼方法的選擇及其參數(shù)的確定提供了理論支持。
　　(2)DNA分子雜交二級結(jié)構(gòu)的多樣性,使得計(jì)算其最小自由能的時(shí)間復(fù)雜度非常高,當(dāng)編碼約束條件較嚴(yán)格時(shí),很難在有效的時(shí)間內(nèi)設(shè)計(jì)出滿意數(shù)量的DNA序列。提高DNA分子二級結(jié)構(gòu)的預(yù)測精度和自由能的計(jì)算效率是熱力學(xué)DNA編碼算法

4、設(shè)計(jì)的難點(diǎn)和關(guān)鍵。
　　本文研究了DNA分子雜交自由能變化與雙鏈DNA分子二級結(jié)構(gòu)穩(wěn)定性的關(guān)系,提出了一種基于熱力學(xué)的啟發(fā)式隨機(jī)搜索 DNA序列設(shè)計(jì)算法,該算法采用Nearest-Neighbors熱力學(xué)模型,通過對DNA分子雜交的二級結(jié)構(gòu)進(jìn)行預(yù)測,選擇滿足用戶設(shè)定的最小自由能約束的DNA序列,從而有效避免了DNA計(jì)算中DNA分子的非特異性雜交。同其它隨機(jī)搜索DNA序列設(shè)計(jì)算法相比,該算法首先排除不滿足解鏈溫度的候選DNA序列,然

5、后用貪婪算法計(jì)算DNA序列的自由能,并逐步將不滿足自由能約束的候選序列轉(zhuǎn)化為可行解,提高了DNA序列的設(shè)計(jì)效率。通過和其它算法提供的DNA序列進(jìn)行比較和分析,證實(shí)了算法可產(chǎn)生熱力學(xué)性質(zhì)更穩(wěn)定的DNA序列,驗(yàn)證了算法的有效性。
　　(3)當(dāng)前各種DNA序列設(shè)計(jì)算法適用的編碼約束有限,對不同的DNA計(jì)算模型不具備通用性;并且難以高效的設(shè)計(jì)出滿足約束的最大DNA序列集合,無法求解大規(guī)模的DNA計(jì)算問題實(shí)例。
　　本文針對DNA編碼

6、設(shè)計(jì)的這些難點(diǎn),提出了隱枚舉核酸序列設(shè)計(jì)算法,以提高DNA計(jì)算的可擴(kuò)充性,求解更大規(guī)模的計(jì)算問題。通過將編碼約束轉(zhuǎn)換為整型線性規(guī)劃的條件不等式對DNA序列進(jìn)行約束,靈活適用于各種編碼約束,可滿足各種DNA計(jì)算模型對DNA編碼的不同要求。算法使用剪枝策略高效的搜索4n解空間,找出滿足約束條件的最大的DNA序列集合。最后通過和遺傳算法、多目標(biāo)進(jìn)化算法、模板映射、模擬退火和動(dòng)態(tài)規(guī)劃等算法進(jìn)行比較和分析,證明了本文提出的隱枚舉核酸序列設(shè)計(jì)算法產(chǎn)

7、生的DNA編碼質(zhì)量更加穩(wěn)定可靠,具有極強(qiáng)的擴(kuò)充性,適用于各種核酸試驗(yàn)的DNA分子設(shè)計(jì)要求,可以高效的產(chǎn)生滿足編碼約束的最大的DNA序列集合。
　　(4)最后,將隱枚舉核酸編碼算法應(yīng)用于求解61個(gè)頂點(diǎn)的圖著色DNA計(jì)算實(shí)例。使用隱枚舉DNA編碼算法設(shè)計(jì)出了滿足組合約束、熱力學(xué)約束共129條DNA序列,通過分子生物學(xué)實(shí)驗(yàn)方法,成功求解出61個(gè)頂點(diǎn)3著色DNA計(jì)算實(shí)例,通過DNA測序證明得到了代表圖著色問題解的DNA分子,驗(yàn)證了本文編碼