計算DNA序列模式特征的匹配算法

戴勝冬，楊　昆

(杭州電子科技大學(xué)計算機(jī)學(xué)院，浙江 杭州 310018)

摘要：分析了DNA序列特征計算過程中的特殊性，提出了一種基于“空間換時間”的模式匹配算法，設(shè)計了以map數(shù)據(jù)結(jié)構(gòu)來存儲中間結(jié)果的方案，使得掃描DNA序列一次即可同時計算所有元組模式在該序列中出現(xiàn)的次數(shù)。實驗結(jié)果及分析表明，算法提升了DNA序列模式特征計算的效率，較好地解決了計算DNA序列模式特征的問題。

關(guān)鍵詞：算法；生物信息學(xué)；DNA序列；模式匹配

DOI: 10.13954/j.cnki.hdu.2015.01.018

計算DNA序列模式特征的匹配算法

戴勝冬，楊昆

(杭州電子科技大學(xué)計算機(jī)學(xué)院，浙江 杭州 310018)

摘要：分析了DNA序列特征計算過程中的特殊性，提出了一種基于“空間換時間”的模式匹配算法，設(shè)計了以map數(shù)據(jù)結(jié)構(gòu)來存儲中間結(jié)果的方案，使得掃描DNA序列一次即可同時計算所有元組模式在該序列中出現(xiàn)的次數(shù)。實驗結(jié)果及分析表明，算法提升了DNA序列模式特征計算的效率，較好地解決了計算DNA序列模式特征的問題。

關(guān)鍵詞：算法；生物信息學(xué)；DNA序列；模式匹配

DOI:10.13954/j.cnki.hdu.2015.01.018

收稿日期：2014-06-26

基金項目：國家自然科學(xué)基金資助項目(60903086)

通信作者：

作者簡介：戴勝冬(1990-)，男，安徽巢湖人，在讀研究生，表觀遺傳數(shù)據(jù)分析和挖掘.楊昆副教授，E-mail: yangkun@hdu.edu.cn.

中圖分類號：TP311.1

文獻(xiàn)標(biāo)識碼：：A

文章編號：：1001-9146(2015)01-0088-05

Abstract:This paper analyzed the specificity of DNA feature calculation， proposed an algorithm based on “space for time” idea， which designed a scheme of using map data structure to store the intermediate calculation results， so that each DNA sequence needs to be scanned just once to calculate all pattern features. Experiment results and analysis show that the algorithm can effectively improve the efficiency of calculating DNA feature， and better solve the problems common pattern calculating algorithms have in calculating DNA feature.

0引言

DNA序列特征的計算在生物信息學(xué)的研究中具有著重要的基礎(chǔ)性地位，具體的序列特征有很多類型，而元組模式是其中一個重要且常見的類別[1-4]。對DNA甲基化狀態(tài)預(yù)測就需要計算DNA序列中元組模式出現(xiàn)的次數(shù)[5-10]。例如，文獻(xiàn)[9]通過計算人類淋巴細(xì)胞21號染色體的甲基化數(shù)據(jù)特征，發(fā)現(xiàn)序列模式是指示CpG島甲基化狀態(tài)的三類特征之一；文獻(xiàn)[10]利用乳腺癌高甲基化基因的上游CpG島的模式特征數(shù)據(jù)，分析得出序列特征可以作為標(biāo)識來識別癌癥高甲基化基因。然而如何高效率的量化DNA序列中元組模式特征已經(jīng)成為生物信息學(xué)研究中的一個基本問題。在對DNA序列進(jìn)行元組模式特征的計算中，DNA序列的數(shù)目往往非常龐大，單個DNA序列的長度也比較長，同時需要量化的元組模式數(shù)量較多、組合多變，這使得傳統(tǒng)的模式匹配算法在DNA序列特征計算中時間效率不理想。

本文分析了上述DNA序列特征計算中存在的問題，針對其特殊性，提出了基于“空間換時間”思想的DNA序列模式計算的Map-based算法。算法設(shè)計了以元組模式為鍵元組模式在序列中出現(xiàn)次數(shù)為值的map數(shù)據(jù)結(jié)構(gòu)，利用map數(shù)據(jù)結(jié)構(gòu)來存儲中間結(jié)果，使得掃描DNA序列一次即可同時計算所有元組模式在該序列中出現(xiàn)的次數(shù)。同時，設(shè)計了一個直觀的單序列順序遍歷算法。作為對比參照，實現(xiàn)了常規(guī)的Boyer-Moore、KMP模式匹配算法，并在不同規(guī)模的真實數(shù)據(jù)上測試算法的性能。實驗結(jié)果和分析表明，本文提出的Map-based算法在不同數(shù)據(jù)規(guī)模下都有著最好的性能。

1問題的描述和相關(guān)算法

1.1　問題的描述

DNA序列形式上是由A(腺嘌吟堿基)、T(胸腺嘧啶堿基)、C(胞嘧啶堿基)、G(鳥嘌吟堿基)4個堿基字符隨意組合而成的一定長度的字符串。元組模式則是一定長度的DNA IUPAC code組成的片段，DNA IUPAC code中不僅包含A、T、C、G 4個堿基字符，還包含一些通配符，如R表示A or G，本文設(shè)計的算法不考慮其中的gap字符。將片段長度為n個堿基字符的元組模式稱為n元組，例如元組模式GCCTRG長度為6個字符，稱之為6元組。DNA序列的元組模式特征的量化，就是計算元組模式在DNA序列中出現(xiàn)的次數(shù)，例如DNA序列ATGCTGATGCC，元組模式ATGC在其中一共出現(xiàn)了2次，則DNA序列ATGCTGATGCC的元組模式ATGC的特征量化后即為2。實際計算過程中，要同時計算的DNA序列是由數(shù)量達(dá)到成千上萬的DNA序列組成的序列集，元組模式特征則是由數(shù)量幾百的元組模式序列組成的模式集。

1.2　相關(guān)的算法

KMP算法[11]是一個常用且高效率的模式匹配算法，該算法在常規(guī)順序掃描匹配模式算法的基礎(chǔ)上，預(yù)先構(gòu)造模式本身的“失配推進(jìn)表”，每當(dāng)一趟匹配過程中出現(xiàn)字符比較不等時，不需要回溯掃描指針，而是利用已經(jīng)得到的“部分匹配”的結(jié)果，實際上就是查詢“失配推進(jìn)表”得到在模式當(dāng)前位置失配的情況下模式可以向右“滑動”的最遠(yuǎn)的一段距離，繼續(xù)進(jìn)行比較，此算法可以在序列長度為m，元組模式長度為n時在O(n+m)的時間數(shù)量級上完成串的模式匹配操作。

另一個久負(fù)盛名的模式匹配算法是BM(Boyer-Moore)算法，它是一種非常高效的字符串搜索算法。它由Bob Boyer和J Strother Moore設(shè)計于1977年[12]。此算法僅對搜索目標(biāo)字符串(關(guān)鍵字)進(jìn)行預(yù)處理，而非被搜索的字符串。雖然Boyer-Moore算法的執(zhí)行時間同樣線性依賴于被搜索字符串的大小，但是通常僅為其它算法的一小部分，不需要對被搜索的字符串中的字符進(jìn)行逐一比較，而會跳過其中某些部分。通常搜索關(guān)鍵字越長，算法速度越快。

2Map-based算法

綜合DNA元組模式特征計算中的特殊性，考慮采用在存儲和查詢上時間效率都較為優(yōu)秀的Map來記錄和查詢DNA序列的元組模式特征及數(shù)量，在含有通配符的元組模式擴(kuò)展階段，Map被用來存儲展開模式集。本文提出的算法如下描述。

算法1MAP-BASED-COMPUTE-PATTERN-COUNT(S，P，K)

輸入：序列集合S，包含了所有的待計算的DNA序列。元組模式集合P，包含了所有的元組模式。元組模式長度的集合K，如需要計算的元組模式包含了2元組、3元組、4元組、6元組，則K={2，3，4，6}。

1letcount-mapbe a map

2letexpanded-patterns-mapbe a multimap

3letwc-patterns-mapbe a map

4letnowc-patterns-mapbe a map

5for each patternp∈P

6ifpcontains wildcards

7mapcount-map[p]to 0

8for each patternep∈expanded patterns ofp

9mapwc-patterns-map[ep]to 1

11mapexpanded-patterns-map[ep]top

12else then

13mapcount-map[p]to 0

14mapnowc-patterns-map[p]to 1

15for each sources∈S

16fori=0 tos.length

17for eachk∈K

18sub-string=SUB-STRING(s，i，k)

19ifwc-patterns-map[sub-string]==1

20for eachkeyinexpanded-patterns-map[sub-string]

21count-map[key]=count-map[key]+1

22ifnowc-patterns-map[sub-string]==1

23count-map[sub-string]=count-map[sub-string]+1

本算法借助map來存儲預(yù)處理階段的中間結(jié)果，一方面合理且高效地解決了包含通配符的模式計算問題，另一方面借助map較高的查找效率，可以快速地完成模式的定位和模式的計數(shù)操作。程序在預(yù)處理階段構(gòu)造的map雖然占用了較多的內(nèi)存空間，但是在DNA序列的模式計算中，通過map的內(nèi)存空間換取更快的查找效率來節(jié)省計算任務(wù)的時間是完全可取的。

3實驗

本文實驗采用真實的DNA序列數(shù)據(jù)，該數(shù)據(jù)來自于預(yù)測人類基因甲基化程度的原始數(shù)據(jù)集(http://rulai.cshl.edu/HDMFinder/M-set.fa)[13]，其中DNA序列的平均長度為15 370個堿基字符，原始數(shù)據(jù)未進(jìn)行其他處理。元組模式來自文獻(xiàn)[3]中的序列特征模式motif: 1個二元組，64個三元組，256個四元組，133個六元組，其中有30個包含通配符的六元組，共計454個元組模式。實驗的軟件條件為Java 7，Windows 7 32-bit，硬件條件為Intel CPU i5 3.2 GHz雙核，內(nèi)存2.0 GB。

對本文中實現(xiàn)的4種模式計算算法，分別在DNA序列個數(shù)為100、200、400、800、1 600、3 200的規(guī)模下測試算法的效率，在每個具體的數(shù)據(jù)上重復(fù)運行算法5次，統(tǒng)計每個算法運行時間的平均值和標(biāo)準(zhǔn)差，實驗結(jié)果如表1所示。

對比表1中數(shù)據(jù)可以看出，運行速度最慢的是BM算法，最快的是Map-based算法，Map-based算法比第二快的單個序列順序遍歷算法平均快2.45倍。同時可以看出，實驗數(shù)據(jù)中標(biāo)準(zhǔn)差都一致的較小，相對平均值最大的占2.84%，表明實現(xiàn)的4個算法性能穩(wěn)定，實驗結(jié)果可靠。同時分析各算法耗時的方差可以看出，普遍上Map-based算法方差都遠(yuǎn)遠(yuǎn)低于其他模式匹配算法，說明Map-based效率上的穩(wěn)定性更好。

表1　4個算法在不同數(shù)據(jù)上的執(zhí)行時間　ms

從實驗結(jié)果可以看出來，常規(guī)的BM和KMP算法在本文實驗條中表現(xiàn)非常不佳，這主要是因為BM和KMP算法比較適用于模式比較復(fù)雜、長度較長情況下單個序列的模式計算，不適合序列模式個數(shù)多、長度短、復(fù)雜度低的情況。在算法開始匹配之前，兩者都要對模式進(jìn)行預(yù)處理，得出一些輔助數(shù)據(jù)來加速算法運行，在序列模式計算中這個預(yù)處理過程要進(jìn)行m×n次，m、n分別為序列集合和元組模式集合的元素個數(shù)，算法所需的輔助數(shù)據(jù)的重復(fù)計算會給性能帶來很大的損失，模式匹配上的加速不足以彌補(bǔ)模式預(yù)處理消耗的時間。

為了比較4種算法對常規(guī)任務(wù)的計算效率，即對單個長度較長的復(fù)雜模式的計算效率，基于原始數(shù)據(jù)集，隨機(jī)截取長度為200的5個DNA片段分別作為5個單一復(fù)雜模式，在長度為125 000、250 000、500 000、1 000 000、2 000 000、4 000 000的DNA序列上應(yīng)用本文的4種算法來分別計算每個復(fù)雜模式，統(tǒng)計每個算法在5個單一模式的計算上耗費時間的平均值和標(biāo)準(zhǔn)差，實驗結(jié)果如表2所示。

表2　4個算法在不同序列長度上單個模式特征的計算時間　ms

從表2數(shù)據(jù)可以看出，在上述實驗條件下Map-based算法速度最慢，平均比BM、KMP、單個序列順序遍歷算法分別慢47、46、97倍。這個結(jié)果說明，模式較為復(fù)雜、模式長度較長的情況下，對于單個模式計算上常規(guī)算法具有優(yōu)勢。綜合表1、表2中的結(jié)果可以得出，相較于常規(guī)算法，本文提出的Map-based算法能更好地適用于DNA序列模式的計算。

4結(jié)束語

本文提出的算法在應(yīng)用到DNA的序列特征計算時，能很好地應(yīng)對DNA序列數(shù)目龐大、單個DNA序列的長度較長，需要計算的元組模式數(shù)量多、組合多變的情況，實驗結(jié)果表明，在實際應(yīng)用中該算法不僅效率更高而且性能穩(wěn)定性也較高，并且易于實現(xiàn)，具有一定的應(yīng)用推廣價值。

參考文獻(xiàn)

[1]Fan S C， Zhang X G. Progress of bioinformatics study in DNA methylation[J]. Prog Bio-chem Biophys，2009，36(2):143-150.

[2]戴勝冬，楊昆，顧靚，等.DNA序列的甲基化特征提取軟件[J].生物信息學(xué)，2012，10(1):5-7.

[3]楊昆，張彥斌，戴勝冬，等.DNA甲基化的重要特征[J].生物物理學(xué)報，2012，28(11):910-922.

[4]Edwards J R， O’Donnell A H， Rollins R A， et al. Chromatin and sequence features that define the fine and gross structure of genomic methylation patterns[J]. Genome Research，2010，20(7):972-980.

[5]Fang F， Fan S， Zhang X， et al. Predicting methylation status of CpG islands in the human brain[J]. Bioinformatics，2006，22(18):2 204-2 209.

[6]Bhasin M， Zhang H， Reinherz E L， et al. Prediction of methylated CpGs in DNA sequences using a support vector machine[J]. FEBS Letters，2005，579(20):4 302-4 308.

[7]Fan S， Zhang M Q， Zhang X. Histone methylation marks play important roles in predicting the methylation status of CpG islands[J]. Biochem. Biophys. Res. Commun.，2008，374(3):559-564.

[8]凡時財，鄒見效，徐紅兵，張學(xué)工.人類基因組CpG島甲基化概況的預(yù)測[J].科學(xué)通報，2010，55:1 329-1 334.

[9]Bock C， Paulsen M， Tierling S， Mikeska T， Lengauer T， Walter J. CpG island methylation in human lymphocytes is highly correlated with DNA sequence， repeats， and predicted DNA structure[J]. PLoS Genetics，2006，2(3):e26.

[10]Lv J， Su J， Wang F， et al. Detecting novel hyper methylated genes in breast cancer benefiting from feature selection[J]. Computers in biology and medicine，2010，40(2):159-167.

[11]Knuth D E， Morris， Jr J H， Pratt V R. Fast pattern matching in strings[J]. SIAM journal on computing，1977，6(2):323-350.

[12]Boyer R S， Moore J S. A Fast String Searching Algorithm[J]. Communications of the ACM，1977，20(10):762-772.

[13]Das R， Dimitrova N， Xuan Z， et al. Computational prediction of methylation status in human genomic sequences[J]. Proceedings of the National Academy of Sciences，2006，103(28):10 713-10 716.

Pattern Matching Algorithm for Calculating DNA Feature

Dai Shengdong， Yang Kun

(SchoolofComputer，HangzhouDianziUniversity，HangzhouZhejiang310018，China)

Key words: algorithm; bioinformatics; DNA sequence; pattern matching