NP-完全問題的質(zhì)粒DNA計算模型的研究.pdf

1、作為本文的研究對象，質(zhì)粒DNA計算模型的結構和功能上的優(yōu)越性使得質(zhì)粒DNA計算模型具有很強的生命力和活力，因此對質(zhì)粒DNA計算模型的深入研究是有意義的。在質(zhì)粒DNA計算中，DNA編碼問題具有核心和關鍵的作用。按照DNA編碼在DNA計算不同階段的作用，將質(zhì)粒DNA計算編碼問題細化為：質(zhì)粒DNA計算編碼的設計問題和質(zhì)粒DNA計算編碼集合的計算問題。
　　 通常人們提到的DNA計算編碼問題就是指DNA編碼集合的計算問題。將DNA計算編

2、碼問題進行細化是必要的，這是因為：有利于DNA計算的理論和應用的發(fā)展；DNA編碼的設計問題本身有其獨特的內(nèi)容值得總結，其理論也需要完善；DNA計算的第一步就必須同時解決DNA編碼的設計問題和DNA編碼集合的計算問題。
　　 質(zhì)粒DNA計算編碼的設計問題在以往的DNA編碼理論中討論較少，因此，以質(zhì)粒DNA計算編碼的設計問題作為研究的重點內(nèi)容具有一定的創(chuàng)新性。論文的結構大致分兩個部分，首先討論了質(zhì)粒DNA計算模型的理論基礎，然后以質(zhì)

3、粒DNA計算在NP-完全問題中的應用為背景解決了質(zhì)粒DNA計算編碼的設計問題，這是文中重點部分。具體內(nèi)容如下。
　　 從質(zhì)粒DNA計算模型的物質(zhì)基礎和生化實驗基礎兩個方面討論了質(zhì)粒DNA計算模型的可靠性和可行性，研究表明質(zhì)粒DNA計算模型有堅實的理論基礎。同時，對質(zhì)粒DNA計算的編碼問題進行了分類，并提出了將質(zhì)粒DNA計算的編碼問題細化為質(zhì)粒DNA計算編碼的設計問題和質(zhì)粒DNA計算編碼集合的計算問題，充實了質(zhì)粒DNA計算的編碼問

4、題的內(nèi)涵。
　　 以質(zhì)粒DNA計算在NP-完全問題中的應用為背景總結了這些應用實例的DNA編碼。同時，也發(fā)現(xiàn)了質(zhì)粒DNA計算的最大特點就是DNA編碼的靈活性。由于不同的DNA編碼，其生化實驗有差異，解決實際問題的種類也有差異，因此，我們將不同的DNA編碼歸納為不同的質(zhì)粒DNA計算模型，本文共總結了5類質(zhì)粒DNA計算模型。由于質(zhì)粒DNA計算模型由質(zhì)粒DNA分子及其生化實驗組成，且質(zhì)粒DNA計算模型的典型生化實驗是：插入實驗和刪除實

5、驗，因此分別對這些模型的質(zhì)粒DNA的編碼和各模型的典型生化實驗進行了總結。
　　 基本的質(zhì)粒DNA計算模型的編碼上每個信息位只能存放一條DNA編碼信息。質(zhì)粒DNA計算模型推廣Ⅰ和Ⅲ的編碼上每個信息位可以存放多個DNA編碼信息。質(zhì)粒DNA計算模型推廣Ⅱ的編碼上每個信息位為兩段DNA編碼，每段DNA編碼可以存放多個DNA編碼信息。質(zhì)粒DNA計算模型推廣Ⅳ的編碼上質(zhì)粒DNA的長度的不定的。對生化實驗，插入實驗和刪除實驗只有與分離和合并