基于多核架構(gòu)的生物序列比對算法的設(shè)計與實現(xiàn).pdf

1、生物信息學(xué)是計算技術(shù)在管理和分析生物信息數(shù)據(jù)上的應(yīng)用。在生物信息學(xué)中，序列比對是一種計算排列DNA、RNA和蛋白質(zhì)序列的方法，此方法用來劃分序列間可能與功能、結(jié)構(gòu)或進(jìn)化關(guān)系有關(guān)的相似區(qū)域。序列的關(guān)系是可以量化的，并且它們之間的相似度也是可以評估的。這種相似度可以用來鑒定一個新發(fā)現(xiàn)的序列和一個已知基因之間的進(jìn)化關(guān)系。如果相似度低，除非收集到足夠的證據(jù)，否則它們的進(jìn)化關(guān)系只能是待定的。序列比對已經(jīng)成為分子生物學(xué)中的一項常規(guī)操作。今天，序列可

2、以很容易獲得，但是去比對已經(jīng)得到的序列仍然是分子生物學(xué)中復(fù)雜的一部分。過去的幾十年中，一系列的序列比對程序已經(jīng)出現(xiàn)。它們中的大多數(shù)采用了基于動態(tài)規(guī)劃思想的算法，這個算法由Needleman和Wunsch于1970年提出。
　　 Needleman-Wunsch算法基于動態(tài)規(guī)劃思想。這個算法的時間復(fù)雜度是O(n2)，這里的n是輸入序列的長度。因為該算法需要執(zhí)行與序列長度乘積規(guī)模相當(dāng)?shù)囊幌盗胁僮?，所以其計算耗費是相當(dāng)高的。為了降低算

3、法執(zhí)行所需要的時間，我們很自然地考慮到這個算法的并行化設(shè)計。
　　 由于多核架構(gòu)上編程簡易且功能強(qiáng)大，因此適合用作高性能計算。進(jìn)一步說，此架構(gòu)有很好的價格/性能比率。很多任務(wù)都可以基于多核平臺執(zhí)行，并且執(zhí)行效率顯著提升。這篇論文工作的主要動機(jī)就是利用現(xiàn)有普通的多核架構(gòu)的巨大的計算能力，實現(xiàn)一個序列比對的高效解決方案。OpenMP是一個可移植，可擴(kuò)展的模型，它給基于共享存儲器編程的程序員提供一個簡單且靈活的接口，以此來開發(fā)從桌面到

4、超級計算機(jī)平臺都適用的并行程序。
　　 本文研究了生物序列比對算法及其并行化，主要研究內(nèi)容如下：
　　 1.介紹了多核架構(gòu)以及OpenMP編程模型的一些基本知識。闡述了多核架構(gòu)的特點，OpenMP模型的相關(guān)信息。
　　 2.對雙序列比對算法做了分析，指出了其優(yōu)點與不足。并用Diagonal Wavefront算法結(jié)合OpenMP模型的特性對Needleman-Wunsch算法進(jìn)行了并行化。
　　 3.在N

5、eedleman-Wunsch算法并行化的基礎(chǔ)上，研究了基于Needleman-Wunsch算法的Clustal算法的并行化。
　　 4.通過比較Needleman-Wunsch算法和Clustal算法在單線程和多核系統(tǒng)下多線程并行執(zhí)行的耗費時間，我們發(fā)現(xiàn)當(dāng)計算的比對序列較長以及比對序列較多時，計算速度有較明顯的上升。實驗的結(jié)果證實了序列比對算法完全可以因并行計算而獲得性能提升。實驗結(jié)果同樣說明了這樣一個事實：要高效利用多核系統(tǒng)