基于關(guān)鍵字樹(shù)和滑動(dòng)窗口的大規(guī)模生物遺傳序列的算法研究.pdf

1、隨著人類(lèi)基因組計(jì)劃的順利實(shí)施，生物數(shù)據(jù)海量增加，隨后生物信息學(xué)開(kāi)始迅速興起。生物序列比對(duì)是目前生物信息學(xué)領(lǐng)域一個(gè)有難度卻重要的研究課題，廣泛的應(yīng)用于基因識(shí)別和氨基酸結(jié)構(gòu)預(yù)測(cè)等領(lǐng)域中。在很多種情況下，具有高相似性的大規(guī)模生物數(shù)據(jù)需要被分析處理。由于生物學(xué)本身的特點(diǎn)和海量生物數(shù)據(jù)的獲得，到目前為止還沒(méi)有一個(gè)方法可以滿(mǎn)足各領(lǐng)域研究人員的需求，其中串行算法在處理生物數(shù)據(jù)時(shí)所表現(xiàn)的的低效率也困擾著研究人員。本文將著重考察利用并行計(jì)算來(lái)進(jìn)行多序列比

2、對(duì)及其并行化處理方案，對(duì)此提出了一個(gè)新的多序列比對(duì)并行算法P-MA。
　　 詳細(xì)分析了目前使用比較廣泛的多序列比對(duì)算法，其中，動(dòng)態(tài)規(guī)劃方法在處理序列優(yōu)化時(shí)表現(xiàn)非常良好，然而由于它的平方級(jí)時(shí)間復(fù)雜度成為了進(jìn)一步研究的瓶頸。人們開(kāi)始尋求一種平衡，近似最優(yōu)化情況下去提高算法運(yùn)行速度。星比對(duì)方法經(jīng)常被用來(lái)處理大規(guī)模序列數(shù)據(jù)。本文嘗試了更為適合具有高相似性序列的星比對(duì)算法并進(jìn)行了相應(yīng)的改進(jìn)，在基于改進(jìn)的星形比對(duì)算法中引入了并行處理機(jī)制，從

3、而使該算法的時(shí)間復(fù)雜度降低至幾乎線(xiàn)性。
　　 首先一種針對(duì)此的多序列比對(duì)算法MA算法被提出，利用關(guān)鍵字樹(shù)和滑動(dòng)窗口來(lái)匹配r-length片段的子字符串而剩余片段使用動(dòng)態(tài)規(guī)劃比對(duì)，最終得到比對(duì)結(jié)果。這種方法提供參數(shù)調(diào)節(jié)機(jī)制，調(diào)節(jié)參數(shù)對(duì)于該算法的性能起著極重要的作用。實(shí)驗(yàn)結(jié)果充分說(shuō)明了其在計(jì)算效率上的優(yōu)勢(shì)。
　　 盡管做了如上改進(jìn)，時(shí)間需求仍然比較大，當(dāng)在按照上面所介紹的方法進(jìn)行比對(duì)時(shí)，發(fā)現(xiàn)對(duì)于條數(shù)很多的待比對(duì)序列在尋找中心

4、序列時(shí)，會(huì)出現(xiàn)很多序列沒(méi)有做任何事的情況，出現(xiàn)了很大的空隙。加上多序列比對(duì)的高計(jì)算復(fù)雜性問(wèn)題，研究了基于MA算法的并行化處理策略?；谶@些，本文提出P-MA來(lái)合理分配以及處理在尋找中心序列時(shí)出現(xiàn)的空閑，將原來(lái)需要串行處理的序列在不同的處理器上同時(shí)處理，找到中心序列后再做綜合處理。該方法同樣遵守滑動(dòng)調(diào)節(jié)機(jī)制，在分配各處理器任務(wù)時(shí)特別注重合理性，因?yàn)檫\(yùn)用并行計(jì)算本身會(huì)帶來(lái)額外的開(kāi)銷(xiāo)，所以自我調(diào)節(jié)機(jī)制和任務(wù)分配對(duì)于P-MA是極其重要的。針對(duì)算

5、法提出了并行處理策略:對(duì)基于并行計(jì)算的多序列比對(duì)方法依次進(jìn)行了構(gòu)建P-MA、改變參數(shù)和兩兩比對(duì)階段的串行處理過(guò)程和可并行性進(jìn)行了探討，提出了各個(gè)階段的并行處理策略。
　　 對(duì)以改進(jìn)算法效率為目標(biāo)的算法需要盡量將敏感度保證在可接受范圍內(nèi)，不能讓最終的比對(duì)結(jié)果失去了研究?jī)r(jià)值和生物意義。為使多序列比對(duì)問(wèn)題的時(shí)間復(fù)雜度降到了線(xiàn)性級(jí)，在中心序列獲得后，最終我們會(huì)利用動(dòng)態(tài)規(guī)劃方法得到多序列比對(duì)結(jié)果，保證其優(yōu)化程度。本文還改進(jìn)了MA，充分將空