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

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

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

3、關(guān)于雜交、連接、聚合、退火和電泳等常用生化操作的順序圖。利用順序圖可以清楚的了解生物反應(yīng)的全過(guò)程，并可以應(yīng)于計(jì)算機(jī)的模擬程序設(shè)計(jì)，為將來(lái)的計(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é)合提供支持。⑶分析了聚類(lèi)問(wèn)題的本質(zhì)，將其轉(zhuǎn)化為可以采用DNA計(jì)算解決的組合優(yōu)化問(wèn)題或者圖論問(wèn)題。對(duì)于樣本數(shù)據(jù)對(duì)象的聚類(lèi)就

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

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

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

7、技術(shù)解決圖像聚類(lèi)問(wèn)題，對(duì)圖進(jìn)行分割。提出了利用k-medoids算法進(jìn)行圖像分割的DNA過(guò)濾模型，并給出了編碼方案和生物實(shí)驗(yàn)設(shè)計(jì)。該編碼方案根據(jù)將圖像中的像素點(diǎn)看作是樣本數(shù)據(jù)點(diǎn)，灰度值看作是樣本數(shù)據(jù)點(diǎn)的屬性，設(shè)定一定的灰度值作為聚類(lèi)的質(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ì)圖像的百萬(wàn)級(jí)像素時(shí)將顯現(xiàn)非常大的優(yōu)勢(shì)。⑻通過(guò)計(jì)算機(jī)模擬整個(gè)生化反應(yīng)過(guò)程。實(shí)驗(yàn)基于節(jié)點(diǎn)和邊編碼方案的網(wǎng)格聚類(lèi)，通過(guò)模擬連接反應(yīng)獲得所有可能解，再通過(guò)模擬生物實(shí)驗(yàn)將聚類(lèi)結(jié)果解出。該模擬程序完全按照 DNA計(jì)算的生物實(shí)驗(yàn)原理，生成所有可能解，該實(shí)驗(yàn)將花費(fèi)大量的時(shí)間，因此聚類(lèi)的數(shù)據(jù)量較小，但可以證明編碼方案的可行性和DNA計(jì)算算法的正確性。⑼利用并行計(jì)算算法模擬整個(gè)生化反應(yīng)過(guò)程。由于并行反應(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)的簇的聚類(lèi)時(shí)間。該實(shí)驗(yàn)從并行反應(yīng)的角度驗(yàn)證了DNA計(jì)算的并行優(yōu)勢(shì)，并應(yīng)用于規(guī)模較大，形狀較復(fù)雜的數(shù)據(jù)集中，聚類(lèi)效果同原聚類(lèi)算法相同，而計(jì)算時(shí)間要比串行和原聚類(lèi)時(shí)間少。⑽建立模型來(lái)證明其可行性。采用坐標(biāo)的編碼方式，并改進(jìn)了DNA連接過(guò)程的掃描方式，提高了計(jì)算機(jī)的模擬速度，實(shí)現(xiàn)起來(lái)較為簡(jiǎ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í)間長(zhǎng)。聚類(lèi)效果上和原有的聚類(lèi)算法沒(méi)有任何差別。與Bakar提出的基于DNA計(jì)算的聚類(lèi)算法比較，由于網(wǎng)格聚類(lèi)的優(yōu)勢(shì)，使得聚類(lèi)時(shí)間大大縮短，并且編碼設(shè)計(jì)上也具有一定的優(yōu)勢(shì)。⑿給出了一套生物實(shí)驗(yàn)過(guò)程，包括編碼設(shè)計(jì)方案

11、、生物實(shí)驗(yàn)算法以及生物實(shí)驗(yàn)過(guò)程。詳細(xì)描述了如何利用DNA計(jì)算進(jìn)行聚類(lèi)分析的生化實(shí)驗(yàn)操作步驟，并得到的預(yù)期效果。⒀算法復(fù)雜度的討論分為兩個(gè)方面:一個(gè)是在計(jì)算機(jī)模擬的基礎(chǔ)上對(duì)基于DNA計(jì)算的聚類(lèi)算法進(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ù)后情況和圖像分割處理。采用層次聚類(lèi)的方法對(duì)山東省的17個(gè)城市進(jìn)行了聚類(lèi)，通過(guò)模擬DNA計(jì)算獲得了聚類(lèi)結(jié)果，可以將17個(gè)城市劃分為三個(gè)零售商的區(qū)域，區(qū)域內(nèi)的城市會(huì)有一條最短路徑相連，對(duì)物流和區(qū)域運(yùn)輸都是有益的。利用網(wǎng)格聚類(lèi)對(duì)UCI提供的真實(shí)醫(yī)學(xué)數(shù)據(jù)集進(jìn)行了聚類(lèi)，該數(shù)

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