基于多線程技術的ｄ－ＢＭ改進算法
2008-12-31 00:00:00劉少鵬林丕源張麗霞劉吉平
計算機應用研究 2008年11期
(華南農業大學， 廣州 510642)
摘要：在分析基于壓縮的DNA模式匹配算法d-BM的基礎上，采用多線程技術，設計并實現MultipleOF-dBM算法和DoubleOF-dBM算法。實驗結果表明，新算法的匹配速度比d-BM算法有所提高。
關鍵詞：生物信息學； 壓縮模式匹配； d-BM算法； 多線程技術
中圖分類號：TP311文獻標志碼：A
文章編號：1001-3695(2008)11-3299-03
Multithread-based improvement of d-BM algorithm
LIU Shao-peng， LIN Pi-yuan， ZHANG Li-xia， LIU Ji-ping
(South China Agricultural University， Guangzhou 510642， China)
Abstract:After analysis of the d-BM algorithm for DNA compressed pattern matching， two new algorithms， MultipleOF-dBM and DoubleOF-dBM were designed and implemented by using multithreads. The experimental results show that the efficiency of the new algorithms is higher than the old one.
Key words：bioinformatics; compressed pattern matching; d-BM; multithread technology
0引言
生物信息學(bioinformatics)[1，2]實質是利用計算機科學和網絡技術來解決生物學問題。其中DNA序列比對[3，4]是生物信息學最基本、最重要的操作之一，通過它可以發現生物序列的功能、結構和進化信息。DNA序列比對是傳統的模式匹配；而直接利用壓縮后的DNA數據進行序列比對則是特殊的模式匹配，即DNA壓縮模式匹配[5]，它無須解壓縮操作，在減少DNA序列存儲空間的同時，極大地提高匹配檢索效率。
經典的字符串模式匹配算法有Knuth-Morris-Pratt算法[6，7]和Boyer-Moore算法[8，9]等。Boyer-Moore算法的匹配速度很快，與同類算法相比，表現更為優秀。其算法思想是：a)根據模式串構造壞字符移動表和好后綴移動表；b)從右至左掃描文本串，直到找出所有匹配位置。
由于DNA序列具有特殊性(它僅包括A、T、C、G四個字母，字母表大小為4)，而Boyer-Moore算法的匹配速度與模式的字母表大小是緊密聯系的(字母表越大，速度就越快；字母表越小，速度越慢)，使得Boyer-Moore算法難以在DNA序列的模式匹配中發揮其高效性。
Chen Lei等人[10]設計了d-BM壓縮模式匹配算法，通過對DNA序列和模式進行壓縮，擴大模式的字母表，再利用Boyer-Moore算法進行匹配。該算法的匹配速度明顯比Boyer-Moore算法快。
本文采用多線程技術，在d-BM算法的基礎上改進，設計并實現MultipleOF-dBM算法和DoubleOF-dBM算法，實驗結果表明新算法的匹配速度比d-BM算法有所提高。
1d-BM壓縮模式匹配算法
11d-BM算法思想
d-BM算法思想：a)采用簡單01碼壓縮算法[11]，將DNA序列壓縮為一個Unicode字符串，DNA模式壓縮為八個Unicode字符串，以及相關的信息。b)八個壓縮DNA模式串分別與壓縮DNA串進行一次BM(即Boyer-Moore算法)匹配，再根據壓縮后DNA模式串的特殊字符和補位信息，對匹配位置進行檢驗，確保其合法性。
12d-BM算法描述
壓縮DNA模式表示為五元組：〈Pf， Af， Pm， Pb， Ab〉。其中：Pf是第一個unicode字符；Af是Pf中無效的比特位數；Pb是最后一個Unicode字符；Ab是Pb中無效的比特位數；Pm是除去Pf和Pb后的Unicode字符串，其長度為m′。壓縮DNA序列表示為三元組：〈Tf， Tb， A〉。其中：Tb是最后一個Unicode字符；A是Tb中無效的比特位數；Tf是除去Tb后的Unicode字符串，長度為n′。
d-BM算法如下：
//輸入：DNA序列和模式
//輸出：matchPosition數組記錄所有匹配位置，并打印
begin
/*簡單0/1碼壓縮算法壓縮DNA序列和DNA模式*/
壓縮得到八個DNA壓縮模式：〈Pfi，Afi，Pmi，Pbi，Abi〉
其中i≥1且i≤8
壓縮得到壓縮DNA序列： 〈Tf， Tb， A〉
/*BM算法的預處理*/
每個DNA壓縮模式，計算壞字符移動表和好后綴移動表
/*d-BM匹配部分*/
matchPosition[8][];//存放匹配位置的二維數組
for i = 0 to i ＜ 8 do //8個模式分別匹配
matchPosition[i]←BM (Tm，Pm); //BM匹配
//對每個壓縮模式找到的匹配位置，驗證正確性
// 調用size()方法計算數組大小
for j = 0 to j＜size(matchPosition[i]) do
//調用檢驗匹配位置方法CheckPosition()
if CheckPosition() is true then
//刪除找到的多余位置
remove(matchPositon[i][j]);
end if
end for
//輸出準確的匹配位置
for k = 0 to k < size(matchPosition[i]) do
print(matchPosition[i][k]);
end for
end for
end
13驗證匹配位置正確性的方法
八個壓縮DNA模式分別調用BM匹配，找出所有匹配位置，然后調用方法CheckPosition( )，檢驗匹配位置的正確性。
方法CheckPosition( )如下：
//功能：實現匹配位置position的正確性檢驗
//輸入：Pfi， Afi， Pmi， Pbi， Abi， Tf， Tb， A
//輸出：布爾型flag，若true，則刪除找到的匹配位置。
flag ← 1;//初始化
lastPosition ← n′- m′;//特殊位置
if position==0 or position==lastPosition then
//找到位置是特殊位置進行特殊的判斷;
else
//非特殊位置，需檢驗模式第一個和最后一個特殊字符
if Pfi not equal對等位DNA字符then
//檢驗模式第一個字符
flag ← true;
elseif flag is 1 then //若flag為1
if Pbi not equal對等位DNA字符then
//檢驗模式最后一個字符
flag ← true;
end if
end else if
end if
end if
return flag;
2基于多線程技術的壓縮模式匹配算法的設計與實現
21多線程編程與Java
線程也稱輕量級進程(lightweight process，LWP)，它由線程ID、程序計數器、寄存器集合和堆棧組成，是CPU使用的基本單元。多線程編程具有響應程度高、資源共享、經濟、能夠利用多處理器結構四個主要優點[12]。
Java是在語言級提供了線程創建和管理支持功能的為數不多的一種語言。在Java語言中，實現線程編程有兩種方法：a)從java.lang.Thread繼承，該類已經實現具有了創建和運行線程所必要的架構。其中最重要的方法是run()，程序員要覆蓋這個方法，實現自己所要的功能。b)實現Runnable接口。可以看到，使用Java實現多線程編程是相當方便的。本文的MultipleOF-dBM算法和DoubleOF-dBM算法采用第一種方法設計并實現。
22MultipleOF-dBM算法
1)算法思想
d-BM算法的匹配過程具有重復性特點，DNA模式壓縮為八個，每個壓縮DNA模式與壓縮DNA序列進行相同的BM匹配查找，然后檢驗匹配位置正確性。MultipleOF-dBM算法正是根據模式匹配的重復性特點，采用八線程設計。
其主要思想是：a)利用簡單0/1碼壓縮算法，對DNA序列和DNA模式進行壓縮處理。 b)考慮到直接采用d-BM算法，每個壓縮DNA模式都要依次與壓縮DNA序列進行匹配查找，共計八次，耗時長。為減少時間，算法創建八個線程，每個線程分別對應一個壓縮DNA模式的BM匹配查找，使八次匹配查找同步并行。c)檢驗匹配位置的正確性。
2)算法步驟
a)構造八個vector對象。
b)調用MultipleOfdBMThread類的構造方法，創建八個線程。
c)同時啟動八個線程。
d)八個線程分別執行d-BM匹配查找，將線程找到的匹配位置保存到相應vector對象。
算法過程如圖1所示。
3)線程類MultipleOfdBMThread代碼實現
class MultipleOfdBMThread extends Thread{
private int i = 0;//i代表了第i個線程
public void run(){//執行線程
matchPosition [i] = BM (Tm，Pm);
//對每個模式找到的匹配位置，驗證其正確性
for(int j = 0; j < matchPosition [i].size(); ++j)
if(CheckPosition ())
//刪除找到的多余位置
matchPosition [i].removeElementAt(j);
}
23DoubleOF-dBM算法
1)算法思想
從壓縮DNA序列的角度思考，若要提高算法的匹配查找速度，應縮短壓縮DNA序列的長度。DoubleOF-dBM算法，通過將壓縮DNA序列截成兩半（考慮到可能遺漏匹配位置的情況，不是進行簡單的長度對分）。
其主要思想是：a)利用簡單0/1碼壓縮算法，對DNA序列和DNA模式進行壓縮處理。 b)在壓縮DNA序列長度減小為1/8的基礎上，將壓縮DNA序列截成兩半，使得每次檢索的信息縮小為一半。 c)算法創建兩個線程并發執行已截半的壓縮DNA序列的d-BM匹配。
2)算法步驟
a)構造二維vector對象，每維大小為8。
b)調用DoubleOfdBMThread類的構造方法，創建八個線程。
c)同時啟動兩個線程。
d)兩個線程分別執行d-BM匹配查找（檢索的壓縮DNA序列長度變為一半），再將線程找到的匹配位置保存到相應vector對象。
算法過程如圖2所示。
3)線程類DoubleOfdBMThread代碼實現
class DoubleOfdBMThread extends Thread{
private int startDNAPosition， //壓縮DNA序列起始位置
endDNAPosition;//壓縮DNA序列結束位置
private int threadNum = 0; //i代表了第i個線程
public void run(){//執行線程
for(int i = 0; i < 8; ++i){//8個模式分別匹配
matchPosition [threadNum][i]=BM (Tm，Pm);
//對每個模式找到的匹配位置，驗證其正確性
for(int j = 0; j < vectorOfdBM[i].size(); ++j)
if(CheckPosition ())
//刪除找到的多余位置
matchPosition [i].removeElementAt(j);
}
}
}
3實驗結果與分析
實驗數據主要包括兩部分：a)真實的DNA序列，如EMBL數據庫的Homo sapiens物種HUMHBB序列以及est_hum數據庫的DNA序列。b)程序隨機生成的DNA序列。
31真實DNA序列的實驗結果
采用est_hum數據庫的DNA序列，約40 MB。如表1及圖3所示，記DNA模式長度為m，單位是字節。當m＜100 Byte，MultipleOF-dBM算法和DoubleOF-dBM算法表現優于d-BM算法，BM算法最差；100 Byte＜m＜4 KB，MultipleOF-dBM算法最好，DoubleOF-dBM算法略優于d-BM算法；m＞4 KB，與d-BM算法相比，MultipleOF-dBM算法和DoubleOF-dBM算法沒有優勢。
隨著DNA模式長度m的增大，四種算法的運行時間都在下降。這是因為壓縮后，DNA模式的字母表明顯增大(最大可為216)，從而縮短算法匹配查找時間。m=72 KB時，算法時間都開始接近0，甚至為0。
32隨機DNA序列的實驗結果
采用程序隨機生成的DNA序列，約100 MB。如表2及圖4所示，記DNA模式長度為m，單位是字節。當m＜100 Byte，MultipleOF-dBM算法和DoubleOF-dBM算法表現優于d-BM算法，BM算法最差，DoubleOF-dBM算法最好；100 Byte＜m＜4 KB，與d-BM算法相比，MultipleOF-dBM算法和DoubleOF-dBM算法沒有優勢。
注：MultipleOF-dBM算法和DoubleOF-dBM算法的運行時間取各個線程運行時間中的最大值。
4結束語
在d-BM壓縮模式匹配算法的基礎上，采用多線程編程技術，設計并實現基于壓縮的多線程模式匹配算法MultipleOF-dBM和DoubleOF-dBM。實驗結果表明：當DNA序列與模式長度分別不超過100 MB和100 Byte時，兩個算法的匹配速度與d-BM算法相比有所提高；隨著DNA序列和DNA模式長度的增大，兩個算法與d-BM算法相比，優勢不明顯。
進一步的工作是：a)綜合考慮多線程創建的開銷等因素，把兩個算法不斷完善。b)由于算法使用Java平臺，實現模塊化簡單，可成為搭建生物信息學平臺的重要模塊，完成其中的DNA序列比對工作。
參考文獻：
［1］陳新.生物信息學簡介[EB/OL].(2001) [2007-10-21].http://166.111.68.168/bioinfo/papers/Chen_Xin.pdf.
[2]林毅申，林丕源.基于Web services的生物信息解決方案[J]. 計算機應用研究， 2005，22(6): 157-158，164.
[3]ATTWOOD T K， PARRY-SMITH D J.生物信息學概論[M].羅靜初，譯. 北京：北京大學出版社，2002.
[4]CHEN Yuan.序列比較[EB/OL].[2007-10-21].http://www.lmbe.seu.edu.cn/chenyuan/xsun/bioinfomatics/Web/CharpterThree/3.1.htm.
[5]NAVARRO G， RAFFINOT M. A general practical approach to pattern matching over ziv-lempel compressed text[C]//Proc of Combinatorial Pattern Matching. Berlin: Springer， 1999:14-36.
[6]KNUTH D E， MORRIS J H， PRATT V R.Fast pattern matching in strings[J].SIAM Journal on Computing， 1977，6(2):323-350.
[7]嚴蔚敏，吳偉民.數據結構[M].北京：清華大學出版社，2004：80-83.
[8]BOYER R S，MOORE J S.A fast string searching algorithm[J].Communications of the ACM， 1977，20(10):762-772.
[9]LEVITIN A. 算法設計與分析基礎[M].潘彥，譯.北京：清華大學出版社，2004：202-209.
[10]CHEN Lei， LU Shi-yong， RAM J.Compressed pattern matching in DNA sequences[C]//Proc of IEEE Computational Systems BioinformaticsConference. Washington DC: IEEE Computer Society，2004: 62-68.
[11]張麗霞，張義青，林丕源，等.基于字符和0/1碼的DNA壓縮模式匹配算法[J].計算機應用研究， 2007，24(9):22-24.
[12]SILBERSCHATZ A. 操作系統概念[M].鄭扣根，譯.北京：高等教育出版社，2004：98-99.
