多序列比對軟件T—Coffee的并行化設(shè)計與實(shí)現(xiàn)

1、第卷第期年月計算機(jī)應(yīng)用與軟件多序列比對軟件的并行化設(shè)計與實(shí)現(xiàn)靳新駱志剛蔣曉舟王金華張雯（國防科學(xué)技術(shù)大學(xué)并行與分布處理國家重點(diǎn)實(shí)驗(yàn)室湖南長沙）摘要是廣泛用于核酸或氨基酸的多序列比對工具。它通過生成基本信息庫，擴(kuò)展庫，生成指導(dǎo)樹，漸近式比對四個階段來完成多序列的比對。分析了串行算法及其復(fù)雜度，并提出了基于機(jī)的并行化版本。目標(biāo)是使其充分并行化，實(shí)驗(yàn)結(jié)果表明它明顯的提高了性能，并得到了很好的相對加速比。關(guān)鍵詞全局比對局部比對漸近式算法共享內(nèi)存多處理機(jī)，）（，：，引言串行算法是一種新的準(zhǔn)確率高的多序列比對算法，由多序列比對是分子生物學(xué)中重要的分析工具。它可用于探測新序列與已知序列家族的同源性，預(yù)測新序

2、列的二級和三級結(jié)構(gòu)，蛋白質(zhì)家族中結(jié)構(gòu)或功能的相似片斷。隨著測序的自動化使得新序列以指數(shù)級別增長，人們對快速高效的多序列比對算法的需求越來越迫切。目前已產(chǎn)生了幾種多序列比對軟件，如，等，這些算法的時間復(fù)雜度都非常高。其中，是新產(chǎn)生的一種方法，與前幾種方法相比，它綜合了全局和局部比對及位置信息，提高了準(zhǔn)確率和敏感性，但同時也增加了它的時間復(fù)雜度。緩存和并行化的策略通?？梢越档瓦@些算法的時間復(fù)雜度，提高計算吞吐量。目前已產(chǎn)生了多種并行化版本，如的商業(yè)版本，基于集群的，基于消息通信的【，這些算法都在不同環(huán)境下、不同程度上提高了的效率，而目前還未實(shí)現(xiàn)并行化。本文提出了基于的并行化算法，它將按功能分成四個

3、階段，分別實(shí)施并行化策略，這樣大大降低了的時間復(fù)雜度。它可以用于服務(wù)器上執(zhí)行，以提供高效快速的多序列比對服務(wù)。等四人于年提出。傳統(tǒng)的多序列比對通常由序列兩兩比對產(chǎn)生距離矩陣、生成系統(tǒng)發(fā)育樹、漸近算法的全局比對三部分組成。而綜合了全局和局部比對信息，并增加了序列的位置信息，提高了多序列比對的敏感性和準(zhǔn)確率。其流程如圖所示。瓣圖的邏輯流程生成基本比對信息庫分別對輸入序列進(jìn)行兩兩全局和局部比對，從而形成全局比對信息庫和局部比對信息庫，然后對這收稿日期：。靳新，碩士生，主研領(lǐng)域：計算機(jī)應(yīng)用技術(shù)，生物信息學(xué)。萬方數(shù)據(jù)計算機(jī)應(yīng)用與軟件丘兩個庫進(jìn)行組合，產(chǎn)生一個基本比對信息庫，作為下一步的輸入。這一步復(fù)雜度

4、為（），是輸入序列條數(shù)，是序列的平均長度。由于循環(huán)大小可變，我們采用舊的“”機(jī)制避免數(shù)據(jù)在各個處理器上的分配不平衡問題一，理論上。“”機(jī)制此處可用，但是各個比對所用的處理時間不同，所以此處采用“”機(jī)制。盡管作了這樣的優(yōu)化，它最終還受限于處理器的數(shù)目。為了達(dá)到更快的速度，必須在指導(dǎo)樹生成和漸近式比對采取并行優(yōu)化來處理。在（）階段與（）階段的問題是相似的，此處要計算的不是兩兩比對，而是兩兩比對與其他任一序列形成的三元組比較，所以我們采用了相同的并行化的策略實(shí)現(xiàn)。在（）階段，串行算法在一個循環(huán)內(nèi)直接調(diào)用（，），雖然循環(huán)本身不能被并行化，但是我們可以采用并行策略預(yù)先計算出（，）的數(shù)值。因此需要動態(tài)分配

5、一新矩陣，它會在一個并行體中計算，如下所示：（）擴(kuò)展信息庫增加基本庫中每兩兩比對信息的價值，也就是獲得比對在全局中的“地位”，“位置信息”。采用啟發(fā)式算法通過每個兩兩比對與其他所有序列的信息比較得到，其結(jié)果可直接用于多序列比對，其復(fù)雜度為（）。生成指導(dǎo)樹根據(jù)第二步形成的擴(kuò)展信息庫，使用近鄰歸并法生成指導(dǎo)樹，來表示序列之間的距離，位于相同分支上的序列距離更近，復(fù)雜度為（）。漸近式多比對根據(jù)上步生成的指導(dǎo)樹，進(jìn)行多序列比對，復(fù)雜度為（。）。由此可得總的復(fù)雜度是：（）（）（）（）。與相比，不僅要進(jìn)行全局兩兩比對，而且要進(jìn)行兩兩局部比對，然后加權(quán)綜合這兩部分的信息，這一步的復(fù)雜度比要高出一倍多。在第二

6、步要加入序列的位置信息，即擴(kuò)展庫，而沒有這一步。第三步和第四步與相同。由此也可以看出，對并行化提高其效率的必要性。：（）（）（）；（；）（）（）（）；（；）（；），】（，）；的并行化設(shè)計對算法進(jìn)一步分析知，各個步驟產(chǎn)生的數(shù)據(jù)不相（；）（；），；關(guān)，也就是說各個階段可以獨(dú)立執(zhí)行，因此可以按功能分成四個部分，分別為：通過兩兩比對生成基本信息庫，擴(kuò)展基本信息庫，根據(jù)擴(kuò)展庫生成指導(dǎo)樹，漸近式全序列比對，為了引用方便分別命名為（），（），（），（）。流程圖如圖所示。主結(jié)點(diǎn)?？梢钥闯?，這是一個遞歸調(diào)用的循環(huán)體，和前面的循環(huán)不同，并行將多次進(jìn)入該循環(huán)體。所以這個循環(huán)更適合采用的“”模式實(shí)現(xiàn)并行，以降低的負(fù)載

7、。如下：當(dāng)程序第一次運(yùn)行時，主結(jié)點(diǎn)調(diào)用（）為從結(jié)點(diǎn)分配任務(wù)，在不同的處理機(jī)上執(zhí)行序列的全局和局部比對。當(dāng)（）執(zhí)行完成以后，主結(jié)點(diǎn)調(diào)用（）執(zhí)行，依次執(zhí)行到（）產(chǎn)生最終的結(jié)果。：”叫以上分別介紹了各個階段的實(shí)現(xiàn)細(xì)節(jié)，主程序的執(zhí)行過程¨帥，州）髓圖圖左表示主程序的四個并行段；圖右表示第一個實(shí)驗(yàn)結(jié)果我們用語言和怕。模型實(shí)現(xiàn)了的并行化，使其能夠在共享內(nèi)存（）的多處理機(jī)上執(zhí)行，然后在銀河上進(jìn)行了測試。實(shí)驗(yàn)進(jìn)行了以下兩項(xiàng)測試：（）并行墻鐘時間（），即在并行機(jī)上執(zhí)行時，第一個節(jié)點(diǎn)開始，到最后并行段（）分配序列兩兩比對在個處理器上執(zhí)行。在（）階段（見圖右），將有（）次兩兩的全局和局部序列比對，這一步的

8、時間復(fù)雜度為（）。由于每個兩兩比對與其他的數(shù)據(jù)不相關(guān)，所以很容易實(shí)現(xiàn)并行化操作，其偽代碼如下：（）（；）（；）（，）；（，）；（）；一個結(jié)點(diǎn)產(chǎn)生結(jié)果這段時間，其中包括讀取數(shù)據(jù)和寫結(jié)果。（）相對加速比（），即串行時間與并行執(zhí)行時間的比值。實(shí)驗(yàn)所用的序列從下載。在第一次測試中，分別使用了，條平均長度為的核苷酸序列，結(jié)果如表所示。當(dāng)在個處理器中執(zhí)行時，其加速比依次為，；當(dāng)處理器增至個時，加速比為，?？梢姡铀俦扰c處理器的數(shù)目成比例關(guān)系，處理器增加，加速比也會變大。隨著序列條數(shù)增加，序列比對部分在總時間中占的比例越來越大，使得加速比有所下降。；萬方數(shù)據(jù)第期靳新等：多序列比對軟件的并行化設(shè)計與實(shí)現(xiàn)表三個

9、不同的測試集在不同處理器上的結(jié)果（上接第頁）標(biāo)記名稱存儲，同時狀態(tài)從狀態(tài)跳轉(zhuǎn)到狀態(tài)，“”字符結(jié)束（）（）（）了對“”字符串的解析，同時使?fàn)顟B(tài)從狀態(tài)跳回到狀態(tài)。由于“”字符匹配了狀態(tài)的狀態(tài)字符，相應(yīng)的狀態(tài)處理函數(shù)就使解析樹獲得了第一個有意義的元素。再接下來的“”和“”字符串的解析過程和“？字符串的解析過程基本相同，唯一的不同點(diǎn)在于，元素作為的子元素進(jìn)注：序列的平均長度為，表示處理器數(shù)目，為執(zhí)行時間，入解析樹，而元素則作為的子元素進(jìn)入解析樹。為加速比。對于“”字符串，對應(yīng)的狀態(tài)處理第二次對算法的吞吐量進(jìn)行了測試。分別使用了條和函數(shù)把其存入文本緩沖區(qū)。因?yàn)槲谋驹貎H用來顯示，并不屬條平均長度同樣為的

10、兩種測試集，結(jié)果如下圖所示，于規(guī)范規(guī)定的元素范疇，因此在本文中，把文本元素始終在處理器數(shù)目為，個時，它們之間的加速比相差不大，但是隨作為葉子元素。后續(xù)的“”字符匹配了狀態(tài)的狀態(tài)字符，由著處理器結(jié)點(diǎn)的增多，條的序列比條的序列加速比明于文本緩沖區(qū)不為空，文本緩沖區(qū)的內(nèi)容，即字符串“顯變大，這就表明了我們修改后的算法更適合處理大數(shù)據(jù)，具有”作為文本元素成為元素的子元素。按照高吞吐量的性質(zhì)，這也正是并行化要達(dá)到的效果。規(guī)范，“”被解析成單獨(dú)的元素，因?yàn)槭÷粤私Y(jié)束元素，該元素依然是元素的子元素，作為文本元素的相鄰元素存入解析樹，之后解析自動機(jī)的狀態(tài)回到狀態(tài)。接下來的“”將狀態(tài)從狀態(tài)轉(zhuǎn)變?yōu)闋顟B(tài)，而字符被存

11、入名稱緩沖區(qū)，同時使?fàn)顟B(tài)從狀態(tài)跳轉(zhuǎn)到狀態(tài)，該元素仍然是元素的子元素，做為元素的相鄰元素存人解析樹中，同時狀態(tài)從狀態(tài)跳轉(zhuǎn)到狀態(tài)。按照上述單字符的解析方法，解析自動機(jī)對頁面中圖在不同測試集上的加速比對照的所有字符進(jìn)行解析，直到最后一個字符。最終得到該結(jié)論頁面對應(yīng)的解析樹（如圖）。本文提出并實(shí)現(xiàn)了基于共享內(nèi)存多處理機(jī)系統(tǒng)（）的并行算法，與串行算法相比，它明顯改善了性能。在我們的算法中，將的四個階段：生成基本庫，擴(kuò)展庫，產(chǎn)生指導(dǎo)樹和漸近比充分并行化，使其都能夠在并行機(jī)上執(zhí)行。實(shí)驗(yàn)結(jié)果表明，該算法明顯減少了執(zhí)行的墻鐘時間，得到較高的相對力速比。；：囂“；：囂要寸“參考文獻(xiàn)）日一一圖最終的解析樹。，（）：結(jié)束語文中討論的解析方法以及對應(yīng)的解析自動機(jī)結(jié)構(gòu)，基本上，：可以不加任何改動而用作其他標(biāo)記語言的解析，包括、以及其他基于格式的標(biāo)記語言。這是采用單字符（），解析方法的突出特點(diǎn)。