并行生物序列算法設(shè)計(jì)與優(yōu)化.pdf

1、并行計(jì)算是解決單處理器速度瓶頸的最好方法，它能充分利用計(jì)算機(jī)硬件資源，實(shí)現(xiàn)程序的高效執(zhí)行。它的研究方向包括:計(jì)算機(jī)并行硬件平臺(tái)、并行軟件、并行算法等。
　　目前并行計(jì)算的現(xiàn)狀是:并行算法發(fā)展的速度不及并行硬件性能增長的速度，一些現(xiàn)有的并行算法無法高效的利用并行硬件資源。高效并行算法的缺乏是發(fā)展并行計(jì)算很大的障礙。這種現(xiàn)狀的一個(gè)很重要原因是并行算法的設(shè)計(jì)和優(yōu)化要比串行算法復(fù)雜得多，例如計(jì)算子任務(wù)的劃分、負(fù)載均衡、并行任務(wù)之間的通信和

2、同步等。每一部分的設(shè)計(jì)都會(huì)影響算法最后的性能。所以研究如何設(shè)計(jì)出高效的并行算法具有重要意義。
　　選取了生物信息學(xué)領(lǐng)域中的兩個(gè)基礎(chǔ)課題:蛋白質(zhì)序列比對(duì)和DNA序列拼接，進(jìn)行研究。它們是生物信息學(xué)領(lǐng)域最基礎(chǔ)的課題之一，也是難度較大但十分有意義的課題，很多其他的課題都需要依托這兩個(gè)基礎(chǔ)算法。DNA序列是由4種堿基組成(ATCG)，蛋白質(zhì)序列包含20種氨基酸（amino acid），從計(jì)算機(jī)角度來看它們都是由一串字符組成。但根據(jù)實(shí)際操作

3、的不同，需要采取不同的加速優(yōu)化策略。
　　序列比對(duì)是生物信息學(xué)的基本組成和重要基礎(chǔ)。它的基本思想是基于生物學(xué)中序列決定結(jié)構(gòu)，結(jié)構(gòu)決定功能的普遍規(guī)律。通過檢測序列之間的相似性，發(fā)現(xiàn)生物序列中的功能、結(jié)構(gòu)和進(jìn)化信息。因此蛋白質(zhì)序列比對(duì)對(duì)于研究蛋白質(zhì)在生物體中的作用功能，并研究它們的進(jìn)化起源有重要價(jià)值。但是隨著人類基因組計(jì)劃的實(shí)施，蛋白質(zhì)序列數(shù)據(jù)庫的規(guī)模已呈指數(shù)增長，單純的依靠串行的比對(duì)算法已經(jīng)很難滿足實(shí)際應(yīng)用的需求，這就需要研究并設(shè)計(jì)

4、高效的并行算法來加速蛋白質(zhì)比對(duì)。利用最新的基于Intel MIC(Many Integrated Core，集成眾核)架構(gòu)的Xeon Phi協(xié)處理器，設(shè)計(jì)出了支持異構(gòu)系統(tǒng)架構(gòu)的蛋白質(zhì)序列比對(duì)算法，XPFS，實(shí)現(xiàn)CPU和協(xié)處理器的高效并行工作。算法中實(shí)現(xiàn)了三級(jí)并行:指令集并行（例如利用SSE）、線程級(jí)并行和設(shè)備級(jí)并行。為了使硬件得到高效利用，采用動(dòng)態(tài)任務(wù)分配的策略，由任務(wù)分配器將總的任務(wù)切割成小的任務(wù)塊，每一個(gè)計(jì)算進(jìn)程在完成當(dāng)前任務(wù)塊后，

5、主動(dòng)向任務(wù)分配器申請(qǐng)下一個(gè)任務(wù)塊。由于任務(wù)塊可以分割的比較小，所以避免了負(fù)載不均衡的問題。通過實(shí)際的實(shí)驗(yàn)測試，并與傳統(tǒng)的PFSearch算法作比較，在保證比對(duì)結(jié)果相同的前提下，算法獲得了將近4倍的加速比。
　　DNA序列包含生物體的最基本的遺傳信息，是分子生物學(xué)研究的根本源頭。獲得生物體DNA全部序列對(duì)于揭示生命的本質(zhì)具有重要意義。由于測序技術(shù)的局限，當(dāng)前的測序儀只能一次讀取很短的DNA片段(75～400bp)，這對(duì)于分子生物學(xué)研

6、究是遠(yuǎn)遠(yuǎn)不夠的。序列拼接指的是通過聯(lián)配和融合一些短的測序片段形成更長的DNA序列從而重構(gòu)生物體DNA序列。這對(duì)于分子生物學(xué)是不可或缺的研究方向。序列拼接分為:全新拼接(de novo)和映射拼接(mapping assembly)。而全新拼接(de novo)一直是分子生物學(xué)領(lǐng)域研究的熱點(diǎn)問題。它是在沒有參照序列的前提下，將測序所得的reads片段，通過比對(duì)、連接、組裝等步驟，最終盡量還原出原始的DNA序列。它的主要難點(diǎn)在于: read

7、s片段數(shù)據(jù)量大、測序存在錯(cuò)誤、沒有參考基因組、DNA內(nèi)部存在大量重復(fù)區(qū)域，內(nèi)存需求大等，這都加大了全新拼接(de novo)的難度。根據(jù)拼接中的難點(diǎn)和現(xiàn)有基因拼接算法的不足，設(shè)計(jì)研發(fā)出全新的de novo拼接算法，ARCS。與其他算法不同，首先，ARCS將序列中的unique區(qū)域和repeat區(qū)域分開處理，降低repeat區(qū)域?qū)罄m(xù)拼接的影響。其次，在scaffold構(gòu)建構(gòu)成中，采用的是unique區(qū)域的全局最優(yōu)排列，而不是局部最優(yōu)。為