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

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

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

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

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

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