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

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

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

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

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

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