基于DNA計算的聚類算法研究.pdf

1、DNA計算作為較新興的跨學科技術在理論和技術上已經(jīng)有了很大的進展，在解決NP問題上有著很大的優(yōu)勢。它把數(shù)學和生物有機的結合起來，用生物工具來解答數(shù)學問題，其本質(zhì)就是利用大量不同的核酸分子雜交，產(chǎn)生類似某種數(shù)學計算過程的組合的結果，并對其進行篩選來完成。隨著當今信息化產(chǎn)業(yè)的發(fā)展迅速，大量的信息需要進行數(shù)據(jù)分析，聚類分析發(fā)揮著重要的作用。許多聚類算法都與圖有關，最典型的是層次聚類、網(wǎng)格聚類和圖聚類。本課題把聚類中的數(shù)據(jù)對象轉(zhuǎn)化成為圖中的節(jié)點

2、，那么簇的生成就轉(zhuǎn)化為節(jié)點的組合問題，進而把善于解決組合問題的DNA計算應用到聚類中去，在DNA計算應用中是新的嘗試，也為聚類分析提供了新的思路和方法。
　　本研究主要內(nèi)容包括：⑴有關DNA計算的概念類圖，包括各種類型的DNA分子類圖。通過分析DNA分子不同類型之間的關系以及轉(zhuǎn)化過程，建立它們之間的相互轉(zhuǎn)化關系類圖。通過該類圖可以明確某類型DNA分子是由另外哪種 DNA分子在什么條件下轉(zhuǎn)化而來的。⑵通過分析基本生化操作的過程，建立

3、關于雜交、連接、聚合、退火和電泳等常用生化操作的順序圖。利用順序圖可以清楚的了解生物反應的全過程，并可以應于計算機的模擬程序設計，為將來的計算機模擬實驗提供基礎。DNA計算的面向?qū)ο竺枋雠c建模不僅可以為計算機模擬生化反應提供編程基礎，還可以從計算機科學的角度了解 DNA計算的基本概念和相關技術，為DNA計算與軟計算的結合提供支持。⑶分析了聚類問題的本質(zhì)，將其轉(zhuǎn)化為可以采用DNA計算解決的組合優(yōu)化問題或者圖論問題。對于樣本數(shù)據(jù)對象的聚類就

4、是一種樣本數(shù)據(jù)的組合方式，這種組合方式保證了類內(nèi)的樣本數(shù)據(jù)之間的相似度高，而類之間的樣本數(shù)據(jù)相似度低，DNA計算可以獲得關于樣本數(shù)據(jù)的所有組合，然后再通過生化反應從中提取出最優(yōu)的聚類結果。⑷建立了聚類算法的DNA計算過濾模型和粘貼模型，過濾模型是在Adleman最小模型的基礎上建立的，是最常用，也是最簡單、易實現(xiàn)的DNA計算模型。粘貼模型現(xiàn)在最常應用于圖論問題，因此可以應用于由圖論問題表示的聚類分析。提出了一種新的思路:將網(wǎng)格轉(zhuǎn)化為“米

5、字圖”，在“米字圖”中求得候選節(jié)點的聚類，進而在理論上證明了將該問題轉(zhuǎn)化為哈密爾頓問題的可行性，證明了DNA計算進行網(wǎng)格聚類的可行性和正確性。⑸提出了基于DNA計算的層次聚類算法。在第四章中把層次聚類轉(zhuǎn)化為最小生成樹的問題，從而利用DNA計算來解決該問題。提出了聚類算法的DNA計算過濾模型和粘貼模型，同時給出了基于過濾模型的編碼方案和生化反應設計。⑹把DNA計算應用到網(wǎng)格聚類方法中。把單元格縮小為一個節(jié)點，網(wǎng)格的特殊結構就變成一種特殊的

6、“米字圖”。在五章中論文提出了基于“米字圖”的過濾模型和粘貼模型，并給出了基于過濾模型的四種不同的編碼方案和生物實驗設計。這四種編碼方案利用節(jié)點、邊、坐標的不同組合，各有其優(yōu)點和應用性，但在給出的通用過濾模型下都是可用的，可以使用同一個DNA計算算法，而生物實驗又是有區(qū)別的，因為生物實驗需要根據(jù)不同的編碼方案設計不同生物操作細節(jié)。粘貼模型的建立增加了網(wǎng)格聚類使用DNA計算機的可能，在芯片化和生物技術成熟后將得到更為廣泛的應用。⑺利用聚類

7、技術解決圖像聚類問題，對圖進行分割。提出了利用k-medoids算法進行圖像分割的DNA過濾模型，并給出了編碼方案和生物實驗設計。該編碼方案根據(jù)將圖像中的像素點看作是樣本數(shù)據(jù)點，灰度值看作是樣本數(shù)據(jù)點的屬性，設定一定的灰度值作為聚類的質(zhì)心，利用k-medoids的思想將坐標表示的像素點和與質(zhì)心灰度值的差進行組合，得到節(jié)點鏈和質(zhì)心鏈，將其放入試管中參與DNA計算反應。由于DNA存儲能力和并行反應特性，在處理大量數(shù)據(jù)集時比計算機會更加有效率

8、，該算法在面對圖像的百萬級像素時將顯現(xiàn)非常大的優(yōu)勢。⑻通過計算機模擬整個生化反應過程。實驗基于節(jié)點和邊編碼方案的網(wǎng)格聚類，通過模擬連接反應獲得所有可能解，再通過模擬生物實驗將聚類結果解出。該模擬程序完全按照 DNA計算的生物實驗原理，生成所有可能解，該實驗將花費大量的時間，因此聚類的數(shù)據(jù)量較小，但可以證明編碼方案的可行性和DNA計算算法的正確性。⑼利用并行計算算法模擬整個生化反應過程。由于并行反應時 DNA計算的巨大優(yōu)勢，所以實驗將連接

9、反應分配到每個DNA分子鏈上進行，該程序運行所獲得的運算時間就是包含最多節(jié)點的簇的聚類時間。該實驗從并行反應的角度驗證了DNA計算的并行優(yōu)勢，并應用于規(guī)模較大，形狀較復雜的數(shù)據(jù)集中，聚類效果同原聚類算法相同，而計算時間要比串行和原聚類時間少。⑽建立模型來證明其可行性。采用坐標的編碼方式，并改進了DNA連接過程的掃描方式，提高了計算機的模擬速度，實現(xiàn)起來較為簡單。本實驗可以很好的證明理論思想的可行性，并應用于較復雜的樣本數(shù)據(jù)點。在該實驗中

10、給出了一種模擬掃描鄰居節(jié)點的方法，該方法既可以節(jié)省掃描時間，又可以避免非解和重復鏈的生成。⑾與原有的CLIQUE算法做了比較，發(fā)現(xiàn)程序的運算時間只與候選節(jié)點的數(shù)量和結構有關，如果樣本數(shù)據(jù)點較為緊密，那么運算時間小，如果分散則運算時間長。聚類效果上和原有的聚類算法沒有任何差別。與Bakar提出的基于DNA計算的聚類算法比較，由于網(wǎng)格聚類的優(yōu)勢，使得聚類時間大大縮短，并且編碼設計上也具有一定的優(yōu)勢。⑿給出了一套生物實驗過程，包括編碼設計方案

11、、生物實驗算法以及生物實驗過程。詳細描述了如何利用DNA計算進行聚類分析的生化實驗操作步驟，并得到的預期效果。⒀算法復雜度的討論分為兩個方面:一個是在計算機模擬的基礎上對基于DNA計算的聚類算法進行了復雜度的討論，在計算機編程基礎上，討論按照計算機編程的思想分析DNA計算的時間復雜度；另一個是DNA計算算法的復雜度討論，討論了生化實驗的消耗和反應時間。⒁給出了一種生成符合熱力學約束條件的DNA短鏈的遺傳算法，用于模擬實驗。該算法可以生成

12、較短的一定數(shù)量的符合熱力學約束條件的DNA單鏈分子，可用于計算機模擬實驗和真正的生物實驗中。⒂將DNA計算應用到三種不同的領域中，分別是山東省17城市的區(qū)域劃分、乳腺癌患者的術后情況和圖像分割處理。采用層次聚類的方法對山東省的17個城市進行了聚類，通過模擬DNA計算獲得了聚類結果，可以將17個城市劃分為三個零售商的區(qū)域，區(qū)域內(nèi)的城市會有一條最短路徑相連，對物流和區(qū)域運輸都是有益的。利用網(wǎng)格聚類對UCI提供的真實醫(yī)學數(shù)據(jù)集進行了聚類，該數(shù)

13、據(jù)是三維數(shù)據(jù)，首先將數(shù)據(jù)降到二維，利用DNA計算獲得二維聚類結果，在取交集得到三維的聚類結果。將DNA計算應用到圖像分割中，處理了車牌辨識和手寫辨識兩幅圖片，并利用k-medoids算法對有背景的手寫辨識進行了三類分割，將圖像分割為背景、黑色和白色，更能清楚的辨識重要信息。
　　本文提出的新的基于DNA計算的聚類算法研究，為聚類算法研究提供新的工具，同時為DNA計算開辟新的應用鄰域。隨著數(shù)據(jù)庫的越來越龐大，數(shù)據(jù)挖掘在數(shù)據(jù)存儲和處理