基于CUDA的元胞粒子對(duì)和螢火蟲算法的基因聚類算法研究.pdf

1、隨著生命科學(xué)研究的不斷深入，生物信息學(xué)所涉及的研究范疇也在不斷地?cái)U(kuò)展。微陣列(microarray)技術(shù)作為生物信息學(xué)中極具發(fā)展前景的技術(shù)之一，得到了學(xué)者們的關(guān)注和普及，該技術(shù)能同時(shí)檢測(cè)成千上萬個(gè)基因的表達(dá)水平，從而產(chǎn)生了大量蘊(yùn)含基因信息的基因表達(dá)數(shù)據(jù)。如何高效分析海量的基因數(shù)據(jù)，從中獲得對(duì)人類有意義的信息是現(xiàn)今生物信息學(xué)亟待解決的熱點(diǎn)問題，其中聚類分析則是微陣列數(shù)據(jù)分析中應(yīng)用最為廣泛的方法，具有較高的研究?jī)r(jià)值。
　　在微陣列數(shù)據(jù)

2、基因聚類分析上，現(xiàn)代智能仿生算法日益受到關(guān)注。粒子群優(yōu)化算法、遺傳算法等都已成功地應(yīng)用于基因聚類中，并獲得了不錯(cuò)的聚類效果。近年來的研究表明，采用單一算法已很難獲得較好的聚類結(jié)果，于是眾多學(xué)者開始從各方面入手研究各類算法的改進(jìn)，并取得了顯著的成果。其中，混合算法由于結(jié)合了多種算法的優(yōu)勢(shì)，因而可能克服單一算法的局限性以及各自的缺點(diǎn)。許多近期發(fā)展起來的混合算法在基因表達(dá)聚類分析中也取得了較滿意的效果。
　　隨著微陣列技術(shù)的迅猛發(fā)展，數(shù)

3、據(jù)規(guī)模越來越大，計(jì)算強(qiáng)度和復(fù)雜度已經(jīng)遠(yuǎn)遠(yuǎn)超過個(gè)人計(jì)算機(jī)所能處理的范圍。一種已經(jīng)出現(xiàn)且迅速崛起的高性能計(jì)算技術(shù)CUDA（統(tǒng)一計(jì)算架構(gòu)），打破了傳統(tǒng)GPU上僅適應(yīng)圖形語言的局限，使得應(yīng)用個(gè)人PC機(jī)執(zhí)行高性能并行計(jì)算成為現(xiàn)實(shí)，為推進(jìn)和普及包括大規(guī)模數(shù)據(jù)處理和密集型計(jì)算在內(nèi)的科學(xué)研究與應(yīng)用開辟了新的途經(jīng)。
　　基因表達(dá)數(shù)據(jù)聚類算法尚處在不斷研究和探索之中，作為比較新穎的基因聚類算法——粒子對(duì)算法(PPO)，具有群體規(guī)模小，便于協(xié)調(diào)粒子之間

4、的位置關(guān)系，能獲得較好的聚類效果等優(yōu)勢(shì)，是目前較為廣泛使用的基因聚類算法。然而，PPO算法中由于粒子的交流較少，也存在容易過早陷入局部最優(yōu)、全局搜索能力不強(qiáng)等缺點(diǎn)。合理地利用元胞自動(dòng)機(jī)(CA)中的元胞規(guī)則，可以讓鄰域元胞間具有較強(qiáng)的交流傳播能力，如果通過科學(xué)、合理地設(shè)計(jì)，使PPO和CA算法相互融合，并協(xié)同完成進(jìn)化過程，則可充分地利用CA的優(yōu)勢(shì)來改進(jìn)PPO過早陷入局部最優(yōu)而導(dǎo)致精度不高的缺點(diǎn)。此外，螢火蟲算法(FA)在位置更新的過程中使用

5、了擾動(dòng)因子，在避免過早陷入局部最優(yōu)上有其自身的優(yōu)勢(shì)，同時(shí)其在解決復(fù)雜優(yōu)化問題的效率上也是目前比較好的算法之一。鑒于此，本文建議了一種新的基于元胞粒子對(duì)(PPO(CA)）和螢火蟲算法(FA）的混合算法(PPO(CA)-FA)。該算法在PPO算法的第一階段迭代過程中引入元胞自動(dòng)機(jī)，利用相應(yīng)元胞規(guī)則來更新粒子的個(gè)體歷史最優(yōu)適應(yīng)值和歷史最優(yōu)位置，同時(shí)元胞自動(dòng)機(jī)強(qiáng)大的鄰域交流能力克服了PPO算法易于陷入局部最優(yōu)的缺點(diǎn)。元胞自動(dòng)機(jī)的加入，需要適當(dāng)?shù)?/p>

6、增加算法中粒子的數(shù)量，這樣既提高了粒子全局最優(yōu)值在種群中的傳播速度，也使得新混合算法能對(duì)鄰域進(jìn)行充分搜索的同時(shí)獲得較好的精度。在PPO(CA)的基礎(chǔ)上，為更好地避免陷入局部最優(yōu)，若在第二階段的迭代過程中連續(xù)多次解的最小誤差在指定范圍時(shí)，則引入FA算法，充分利用螢火蟲算法可以高效的搜索解空間的優(yōu)點(diǎn)，獲得更有效的基因聚類結(jié)果。
　　為了驗(yàn)證混合算法的有效性，將PPO(CA)、PPO(CA)-FA與K-Means、PPO算法進(jìn)行比較。將

7、該四種算法運(yùn)行在四組常用標(biāo)準(zhǔn)數(shù)據(jù)集CellCycle_384、histone.pcl、6400和i2282.pcl上，實(shí)驗(yàn)結(jié)果顯示，PPO(CA)-FA能獲得更好的聚類精準(zhǔn)度和聚類效果，在均方差、類內(nèi)緊致度和類間分離度方面都有改進(jìn)。為了驗(yàn)證CA融入的效應(yīng)，將PPO(CA)與只擴(kuò)大了種群沒有加入CA的混合算法(PPO(noCA))進(jìn)行比較，實(shí)驗(yàn)結(jié)果說明CA的加入增加了混合算法在均方差上穩(wěn)定性，改善了聚類效果以及PPO算法易于陷入局部最優(yōu)的

8、缺點(diǎn)。而PPO(CA)與FA的融合，使得混合算法PPO(CA)的全局搜索能力增強(qiáng)，讓算法結(jié)果更加靠近最優(yōu)聚類結(jié)果。
　　PPO(CA)-FA算法在處理高通量、大密度數(shù)據(jù)的等問題時(shí)，存在計(jì)算時(shí)間過長(zhǎng)、效率低的缺點(diǎn)。為了將算法更好的應(yīng)用于實(shí)際，本文在CUDA架構(gòu)下設(shè)計(jì)并實(shí)現(xiàn)了一種并行的PPO(CA)-FA算法，且對(duì)并行算法進(jìn)行了優(yōu)化，提高了混合算法的運(yùn)行效率，同時(shí)保證了算法的準(zhǔn)確率。根據(jù)并行層次的不同，本文提出了兩種優(yōu)化方案。在5種數(shù)