DNA計算若干問題研究.pdf

1、本文探討了生物計算中最受關(guān)注的DNA計算中的一些算法及編碼問題。 在第一章中，首先介紹了一些相關(guān)的預(yù)備知識；其次，對生物計算，特別是DNA計算的不同研究方面及狀況進(jìn)行了簡要的總結(jié)分析，例如DNA計算的模型，解決NP完全問題的算法等。 在第二章中，提出了把參數(shù)算法應(yīng)用于生物計算，以減少生物計算的空間復(fù)雜度的思想。這一章首先給出了頂點(diǎn)覆蓋問題的參數(shù)算法，和這個參數(shù)算法用DNA計算模型實(shí)現(xiàn)的方法，并且得出這個算法以非常接近于1

2、的概率的輸出正確結(jié)果。 在第三章中，首先給出了在粘結(jié)模型下解決帶有數(shù)值參數(shù)的NP完全問題-劃分問題的生物算法，并分析了其正確性。在此基礎(chǔ)上，給出了背包問題相應(yīng)的算法。本章的最后，還給出了一個可以進(jìn)行連續(xù)加法運(yùn)算的，主要使用剪切和連接操作的方法。 第四章首先總結(jié)了兩種判定編碼是否是具有良好性質(zhì)的標(biāo)準(zhǔn)。除了減少錯誤發(fā)生的概率，還應(yīng)該考慮什么樣的碼能夠支持DNA計算大規(guī)模并行性的優(yōu)勢。定義了自由碼子集的概念，并分析