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

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

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