基于DNA計(jì)算的聚類算法研究.pdf

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

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

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

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

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

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

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

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

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

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

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

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

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