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

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

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

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

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

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