異構(gòu)機(jī)群系統(tǒng)上序列比對并行處理研究.pdf

1、序列比對是生物信息學(xué)的核心研究內(nèi)容之一，也是各種序列分析任務(wù)的基本方法。它研究序列之間的優(yōu)化對應(yīng)，即用一個(gè)距離函數(shù)或者相似分?jǐn)?shù)來度量序列之間的相似性和非相似性。序列比對對研究分子結(jié)構(gòu)與功能預(yù)測具有重要意義，因此其計(jì)算方法得到人們高度重視。在實(shí)際應(yīng)用中，序列比對的規(guī)模很大，即使利用最快的串行比對算法也很耗時(shí)，因此需要設(shè)計(jì)高效的并行算法以快速求解這類問題。由于機(jī)群計(jì)算系統(tǒng)具有高性能和低成本的特點(diǎn)，所以在異構(gòu)機(jī)群系統(tǒng)上研究序列比對算法的并行處

2、理具有重要的現(xiàn)實(shí)意義。 本文基于可分負(fù)載理論的最優(yōu)原則，對于處理機(jī)節(jié)點(diǎn)具有不同的計(jì)算速度、通信延遲和存儲容量的異構(gòu)機(jī)群系統(tǒng)，考慮通信啟動(dòng)開銷，提出一種雙序列全局比對問題并行處理的最優(yōu)分配策略，利用該策略確定出并行迭代次數(shù)和分配給各個(gè)從處理機(jī)的子序列長度。異構(gòu)PC機(jī)群系統(tǒng)上的實(shí)驗(yàn)結(jié)果表明，與平均分配策略相比，本文提出的最優(yōu)分配策略進(jìn)行雙序列全局比對并行處理所需的時(shí)間明顯縮短，并獲得良好的加速和可擴(kuò)展性。 多序列局部比對是另