一種基于位置信息的高效DNA序列挖掘算法

楊靜欣 毛國君

(中央財經大學信息學院 北京 100081)

一種基于位置信息的高效DNA序列挖掘算法

楊靜欣 毛國君

(中央財經大學信息學院 北京 100081)

類Apriori算法在產生頻繁模式時需要多次掃描數據庫，并且產生大量的候選集；FreeSpan和PrefixSpan等基于投影數據庫的算法在產生頻繁模式時會產生大量的投影數據庫，占用很多內存空間，這些都造成了很大的冗余。針對以往序列挖掘算法存在的不足，提出一種高效的序列挖掘算法——基于位置信息的序列挖掘算法PBSMA(Position-Based Sequence Mining Algorithm)。PBSMA算法通過記錄頻繁子序列的位置信息來減少對數據庫的掃描，利用位置信息逐漸擴大頻繁模式的長度，并且借鑒關聯矩陣的思想和PrefixSpan算法中前綴的概念，深度優先去尋找更長的關鍵模式。實驗結果證明，無論在時間還是空間上，PBSMA算法都比PrefixSpan算法更高效。

序列挖掘 DNA序列 位置信息 關聯矩陣 前綴

0 引 言

序列挖掘是數據挖掘中非常重要的一個研究領域，一般是指從序列數據庫中發現蘊含在其中的，相對于時間或者其他順序高頻率出現的子序列，并稱這個高頻子序列為序列模式。序列挖掘的概念最早由Agrawal等在針對超市中購物籃數據的分析中提出[1]，目的是發現某一時間段內客戶的購買活動規律。序列挖掘經過近20年的發展，其應用范圍已經不再局限于交易數據庫，在商業，消費者行為分析，股票趨勢預測，生物序列分析，Web挖掘等領域都有重要的應用。商業組織利用序列模式去研究客戶購買行為模式特征、計算生物學中序列模式挖掘來分析不同氨基酸突變模式、用戶Web訪問模式預測以及DNA序列分析和譜分析，尤其在DNA分析等尖端科學研究領域、Web訪問等新型應用數據源等方面得到了有針對性的研究[2-3]。

DNA序列挖掘是序列挖掘最重要的應用之一，通過挖掘DNA序列，研究者可以發現隱藏在序列數據背后的有價值的規律，用以解讀相應生物體中的生命特征。眾所周知，生物的遺傳信息被儲存在DNA中，而DNA是由兩條盤繞在雙螺旋結構上的線性鏈組成，每條鏈可以看成是四種核苷酸A(腺嘌呤)、G(鳥嘌呤)、T(胸腺嘧啶)、C(胞嘧啶)的線性組合，兩條線性鏈嚴格遵守堿基配對規則，即A與T配對、C與G配對出現。例如，一條DNA序列是，則其配對的鏈條序列一定是是。對于現代生物而言，被符號化的DNA序列一旦被儲存在數據庫中，特別是成為網絡上的公共數據集，那么他們就可以供科研人員研究和使用。比如GenBank是目前被廣泛使用的生物基因數據庫，它是美國國家生物信息技術中心NCBI(National Center for Biotechnology Information)建立的DNA序列數據庫，其數據來源于科研人員的直接提供或大規模基因組測序計劃，目前已保存有超過70 000種生物的核苷酸序列。

二十一世紀是生物技術的時代，生物技術是當前最熱門的研究領域之一[4]。DNA數據量龐大，其中蘊藏著海量的信息，我們有理由相信，DNA序列挖掘將會幫助人類解開更多的基因之謎，在遺傳、疾病、物種學上帶來更多的突破。DNA全序列具有什么樣的結構、由這4個字符排成的看似隨機的序列中隱藏著什么規律、各堿基的功能等都有待于進一步的研究。因此，DNA序列模式挖掘成為序列挖掘最重要、最有價值的應用。

1 相關工作

在早期，序列挖掘算法大多基于Agrawal等提出的關聯規則算法—Apriori算法[5]，該算法的核心理論是頻繁模式的任何子模式都是頻繁的。Agrawal和Srikant提出的AprioriAll算法、AprioriSome算法和DynamicSome算法都是基于這個思想而提出，成為序列挖掘算法研究的基礎[1]；1996年，Srikant和Agrawal又提出GSP算法，這是一種廣度優先的自下而上的算法，采用不同的剪枝策略產生較少的候選模式，因而效率相對于AprioriAll算法有所提高，是目前引用率較高的算法之一[6]；然而類Apriori算法自身存在局限性，學者們紛紛開始尋找更高效的方法。2000年，Han等提出了基于模式增長的FP-growth算法，該算法不產生候選集，而是使用FP-tree的樹狀結構壓縮數據庫，然后再利用FP-tree對頻繁模式從下向上的挖掘，加快了挖掘過程[7]。隨后，學者們又提出了一系列基于數據投影的算法，包括Han和Pei于2000年提出的FreeSpan算法[8]和2001年提出的PrefixSpan算法[9]，這些都是經典的序列挖掘算法。近年來，在經典序列挖掘算法的基礎上，學者們相繼提出了優化的序列挖掘算法。2007年，張坤等提出一種基于GSP的MFS(Mining Frequent Sequence)算法[10]，它不需要多次遍歷數據庫，通過連接不同長度的已知頻繁序列來產生的候選序列，比GSP算法更高效；張利軍等提出一種基于位置信息的序列模式挖掘算法PVS，在使用PrefixSpan算法時通過記錄每個已產生的投影數據庫的位置信息降低投影數據庫的冗余，提高算法效率[11]；2012年，劉棟等提出了基于Map Reduce的序列挖掘模式，在PrefixSpan算法的基礎上，對模式挖掘任務進行分割，利用Map函數處理由不同前綴得到的序列模式并構造投影數據庫，從而提高挖掘效率及簡化搜索空間[12]；2013年，吳信東等設計了一種帶有通配符的模式挖掘算法One-Off Mining，通配符的加入使模式的形式更加靈活[13]；2015年，劉端陽等首次在頻繁序列模式挖掘算法中引入邏輯的思想，提出一種基于邏輯的頻繁序列挖掘算法LFSPM，通過邏輯規則過濾，優化結果集[14]。

DNA序列挖掘作為序列挖掘領域最重要的應用之一，也獲得了很多學者的特別關注。學者們結合DNA序列的特點后對傳統的序列挖掘算法進行了有意識的改造提出了在處理DNA序列是更高效的算法。2007年，朱揚勇等對于DNA序列挖掘的問題進行了綜述，回顧了DNA序列挖掘的發展歷程，總結出DNA序列挖掘經歷了三個階段，依次是基于統計技術的應用階段，一般化挖掘方法的應用階段到如今的專門面向DNA序列挖掘的設計階段[15]；2007年，熊赟等提出了一種融合自底向上和自頂向下策略挖掘DNA重復序列的新算法DnaReSM[16]，克服了完全自底向上算法產生大量短候選模式的缺點；2011年，周溜溜等提出了一種基于頻繁子樹挖掘策略的DNA頻繁模式挖掘算法，繞開了傳統序列的對比方式，將序列按照后綴樹結構方式進行組織約減提升識別效率[17]；2013年，姜華等在引入近似度的概念的基礎上，構造頻繁近似模式，提出了頻繁近似模式的挖掘算法SFAP[18]；2015年，毛國君等在分析DNA序列的特點的基礎上，提出了一種基于關聯矩陣(AMSMA)的算法，將掃描數據庫得到的DNA序列信息儲存在關聯矩陣(Association Marix)中，利用矩陣壓縮空間使用率，體現出較好的時間和空間效率[19]。這些算法關注于DNA序列的特點，大大提升了算法的效率。

本文中汲取了上面多個算法的精華，分別是PrefixSpan算法中基于前綴的思想[9]、PVS算法中位置信息的概念[11]和AMSMA算法中關聯矩陣的概念[19]，利用這些算法的優勢提出一種高效的基于位置信息的DNA序列挖掘算法PBSMA(Position-Based Sequence Mining Algorithm)。

2 PBSMA算法描述

2.1 基本概念

定義1 DNA序列(DNA Sequence)：給定字符集合E={A,T,C,G}，一個DNA序列被表示為S=，其中對于任意的si∈E。

例如，在序列abacd中，aba是abacd的前綴，而ba不是。

定義3 關聯矩陣：給定DNA序列S=，其中si∈{A、T、C、G}。關聯矩陣Pij(M×4)總是有4列， 對應{A、T、C、G}四個字符；矩陣的行數是動態變化的，每行對應S的一個長度為k(k≥1)的頻繁子序列，矩陣中元素Pij的值為i行對應子序列和j列對應字符連接后的子序列在序列S中出現的次數，即Pij=support(i∞j)。特別的，當行對應的頻繁模式長度為k時，矩陣Pij稱為k階關聯矩陣[19]。

例如在序列s=中，它的1階關聯矩陣如圖1所示。其中，子序列AA的支持度為0，AT的支持度為3……由此關聯矩陣可以得到所有長度為2的子序列的支持度。

圖1 關聯矩陣舉例

定義4 位置信息：一個子序列在數據庫S中的位置信息為這個子序列在數據庫S中的序列號和在序列中的結束位置，記為(s,v)，其中s表示S中包含該模式序列的序號；v表示對應的序列關于該模式的結束位置。當一個子序列在數據庫中多次出現時，這個子序列的位置信息表示為((s1,v1)，(s2,v2)，…，(sn,vn))。

2.2 算法思路

PBSMA算法是一種基于前綴的深度優先的挖掘算法，以DNA數據為例，在使用PBSMA算法處理上，首先通過掃描數據庫來獲取大1-項集L1={A,T,C,G}，然后依次以L1中的元素為前綴構造關聯矩陣，例如先以A為前綴產生所有以A開頭的關鍵模式，深度優先直到不再有關鍵模式產生時，再以T為前綴……依次類推，直到遍歷過L1中的所有元素后停止。

PBSMA算法的步驟如下：

(1) 掃描序列數據庫，得到長度為1的序列模式L1，作為初始的種子集；

(2) 對于L1中的每一個元素，依次取出一個元素作為新候選模式的前綴，以此來劃分搜索空間；

(3) 將上一步得到的前綴作為關聯矩陣的行，以L1中的所有元素作為關聯矩陣的列，生成關聯矩陣。計算關聯矩陣中每一個候選模式在數據庫中出現的次數(即支持度)并保存每次出現的位置信息；

(4) 檢測關聯矩陣中候選模式的支持度是否大于設定的最小支持度，若大于，則該子序列為關鍵序列，加入到L2并更新其位置信息；若不大于，則不是關鍵序列，刪除之前保存的位置信息；

(5) 利用L2和位置信息依次生成更高階關聯矩陣，得到L3，L4……直到沒有新的序列模式或新的候選序列模式產生為止。

重復步驟(2)-步驟(5)，直到遍歷完L1中的所有序列。

值得注意的是，與從單條序列中挖掘關鍵模式不同，在多條序列的挖掘中，如果某子序列在一條記錄中多次出現，仍然只計數一次，但需要記錄該子序列出現的每一個位置信息，后面的例子中將會詳細說明這一點。

2.3 算法舉例

例1 例如在表1中的DNA序列數據庫，設最小支持度為2，則子序列AT是一個頻繁模式，它的位置記為((1,2)、(1,7)、(2,4)、(2,9)、(3,4))。其中在(1,2)中，1表示S中的第一條序列，2中表示AT這個子序列的最后一個字符在序列1中所處的位置為2，后四者亦同。

表1 例1中DNA序列數據庫

在上例中，首先構造A為前綴的關聯矩陣，構造關聯矩陣如圖2所示。

圖2 前綴為A的一階關聯矩陣

掃描計數的同時，記錄到的AT的位置信息(1,2)、(1,7)、(2,4)、(2,8)和(3,4)，AC的位置信息(3,7)。當支持度為2時，AT是頻繁模式，而AC不是，因此進行剪枝，不再保留AC的位置信息。

利用上一步得到的長度為2的頻繁模式構造2階關聯矩陣。此時無需掃描數據庫，利用上一步得到的位置信息，直接去序列中尋找AT的后綴，構造關聯矩陣并計數，同時更新位置信息。在上例中，出現在(1,2)位置的AT直接后綴為T，則在關聯矩陣相應位置將子序列ATT的支持度增加1，并保存位置信息(1,3)，出現在(2,4)位置的AT直接后綴為C，則子序列ATC的支持度增加1，并保存位置信息(2,5)…依次找到每一個位置信息下的AT的后綴形成關聯矩陣并保存位置信息，得到如圖3的二階關聯矩陣。

圖3 以A為前綴的二階關聯矩陣

對應位置信息為ATT(1,3)、(1,8)、(3,5)，ATC(2,5)。在支持度為2時，得到長度為3的頻繁序列ATT，刪除ATC的位置信息。同樣，利用長度為3的頻繁序列構造4階關聯矩陣，利用位置信息找到長度為4的候選序列，計數并記錄位置信息后發現長度為4的頻繁模式ATTA，位置信息為(1,9)、(2,6)，如圖4所示。利用長度為4的頻繁模式構造五階關聯矩陣，如圖5所示，沒有發現支持度大于2的頻繁模式。至此，以A為前綴的頻繁模式全部找到。

圖4 以A為前綴的三階關聯矩陣

圖5 以A為前綴的四階關聯矩陣

同樣的，應用上面的方法分別建立以T、C、G為前綴的各階關聯矩陣，采用深度優先的原則分別發現以T、C、G為前綴的頻繁模式。產生的所有頻繁模式如表2所示。

表2 例1中的所有頻繁模式

由此可得到最大關鍵模式有：CTA，TCG，CGATTA。

2.4 算法偽代碼

算法描述：PBSMA算法偽碼

輸入：稀疏項目集序列數據庫S；最小支持度min-sup

輸出：S的關鍵子序列KS

1. scan S to get L1{};

//掃描數據庫找到所有的頻繁1-序列

2. FOR m=0 TO L1.size()

//深度優先，最外層循環依次遍歷L1中的每個序列

3. former=L1.get(m);

4. FOR n=0 TO L1.size();

//該層循環意在獲取初始位置

5. later=L1.get(n);

6. string=former+later;

//子序列連接

7. Calculate support of string occur in S ;

//計算子序列支持度

8. IF(support >=min_sup)

//大于等于最小支持度為頻繁模式

9. add string to KS;

10. save Position of string;

//記錄子序列位置信息

11. WHEN(Position is not empty) DO

12. use Position to extend longer subsequence;

13. calculate support;

//利用位置信息尋找更長的頻繁模式并計算支持度

14. IF support>=min-sup

15. add subsequence to KS;

16. update Positon;

//更新位置信息

17. ELSE

18. delete Position;

//不滿足最小支持度的序列刪除位置信息

19. END DO

20. Retrun KS

//輸出所有頻繁序列

3 實驗分析

本部分實驗中DNA數據來源于美國國家生物技術信息中心(http://www.ncbi.nim.nih.gov)。由于這里只探討算法的可用性和時間空間效率，而不是要解決生物問題，也無需對實驗結果進行解釋，因此為了更好地控制實驗變量，實驗數據在原始數據上進行了一定的處理，具體處理方法在下面的各個實驗中作了說明。

實驗是在一臺4GB內存、使用英特爾酷睿i3,1.40 GHz處理器的計算機上進行。采用的對比算法是同樣基于分治思想的PrefixSpan算法[9]。實驗的目標主要是檢測本文算法的精度和效率(包括時間效率和空間效率)。

實驗1 比較內存空間使用情況

由于PBSMA算法不需要產生投影數據庫，因此占用更少的內存。實驗1模擬PreifixSpan算法和PBSMA算法的運行過程，對實驗1中的序列數據進行分析，每一步的占用內存如表3所示。由于兩個算法都是基于前綴的分治思想，因此表3中先討論以L1中頻繁1-序列為前綴的情況，最后再從總體上進行討論。

值得注意的是，PrefixSpan算法的投影數據庫保存投影序列，在本實驗中即字符序列，是字符型數據；PBSMA算法的位置信息保存坐標位置，由兩個整型數值構成，為方便表示，在表3的討論中均將其作為字符處理。

表3 PrefixSpan算法和PBSMA算法的內存使用情況

從表3的實驗結果可以看出，無論利用分治的思想在每一個小范圍內討論，還是從總體上考慮最大使用內存和合計使用內存情況，PBSMA算法的空間效率都要好于PrefixSpan算法。雖然PBSMA算法需要記錄較多的位置信息，但由于每個位置信息僅占用兩字符的內存，相比于PrefixSpan算法投影數據庫中的子序列相比，仍然有優勢。

實驗1中序列數據量小，并且每條序列長度較短，當應用于實際的序列數據庫時，PrefixSpan算法將產生更多的投影數據庫，因而PBSMA算法的空間優勢將會更明顯。

實驗2 比較不同的最小支持度下執行時間

本實驗的數據來源于美國國家生物技術信息中心(NCBI)的序列數據庫，序列被隨機劃分為長度20～30的序列，實驗記錄1 369條，共28 739個字符，將此實驗數據集命名為PBSMA實驗數據集-1。

利用PBSMA實驗數據集-1，在兩個最小支持度區間進行實驗，分別是小支持度區間(5%～30%)、大支持度區間(10%～90%)，測試本文提出的PBSMA算法和PrefixSpan算法的運行效率。表4給出的是實驗數據在小支持度區間范圍內挖掘出的頻繁序列的個數，圖6對應給出在該區間內PrefixSpan和PBSMA運行時間效率的對比；表5給出的是實驗數據在大支持度區間范圍內挖掘出的頻繁序列的個數，圖7對應給出在大支持度區間PrefixSpan和PBSMA運行時間效率的對比。

表4 小支持度區間內挖掘出頻繁序列個數

圖6 小支持度區間內算法時間效率對比

由表4和圖6可以看出，在小支持度區間，實驗數據集-1產生較多的關鍵模式。隨著最小支持度的增加，PBSMA和PrefixSpan算法的執行時間都在下降，這是因為隨最小支持度的增加，生成的關鍵子序列在減少，并且在該數據集中，關鍵子序列減少的速度很快。同時也可以看出，PBSMA算法在處理DNA序列時時間效率明顯高于PrefixSpan算法。

表5和圖7從更宏觀、更全面的角度進行實驗，展現了最小支持度在更大范圍內變化時兩算法的執行效率對比。實驗結果表明：隨著最小支持度的增加，PBSMA和PrefixSpan算法的執行時間都在下降，同時，PBSMA算法在各支持度下的時間效率明顯都要高于PrefixSpan算法。其中，在支持度在10%～30%的范圍內變化時，由于挖掘出的頻繁子序列數量減少速度很快，因此算法執行時間下降速度很快；在40%～70%的范圍內，頻繁子序列數量減少速度相對較慢，因此挖掘算法的執行時間降速放緩甚至趨于平穩；然而在70%及以上的支持度下，由于此時已經不再有頻繁模式被挖掘出來，算法執行時間再一次驟減，并且由于兩算法在掃描一次數據庫后基本不用再進行后面的循環，因此兩算法的運行時間都趨于0，PBSMA算法的優勢也不如產生大量頻繁子序列時明顯。

表5 大支持度區間內挖掘出頻繁序列個數

圖7 大支持度區間內算法時間效率對比

實驗3 比較不同的DNA序列數下執行時間

本實驗的數據來源于美國國家生物技術信息中心(NCBI)的序列數據庫，創建5個數據文件，其中存放序列數量分別為2 000、4 000、6 000、8 000、10 000，每條序列長度20～30。將此實驗數據集命名為PBSMA實驗數據集-2。

本實驗在控制最小支持度變量為20%不變的前提下，運用PBSMA實驗數據集-2中五個不等長數據文件，考察隨著序列數量攀升的情況下兩算法的執行效率。實驗結果如圖8所示。

圖8 序列數量增加時執行時間的比較

圖8表明：在固定的最小支持度下，隨著序列數據庫規模的增大，即序列數量的增加，PBSMA和PrefixSpan算法的執行時間在攀升。在數據量較小的情況下，兩算法的運行時間效率相差不多，但在數據量逐漸增多的過程中，PBSMA展現出越來越優于PBSMA算法的表現，特別地，當序列數量為100 K時，PrefixSpan算法所需要的時間幾乎是PBSMA算法運行時間的兩倍，并且可以預見的是，當數據量更大時，PBSMA算法的優勢將更加明顯。因此可以得出結論，在任何數據量下，PBSMA的算法運行效率都要優于PrefixSpan算法，并且數據量越大，PBSMA算法在時間效率上的提升越明顯。

4 結 語

本文提出了基于位置信息的序列挖掘算法——PBSMA算法。PBSMA算法結合了關聯矩陣、基于前綴、位置信息等的思想，用于從多條序列中挖掘出頻繁模式。較之PrefixSpan算法，PBSMA算法有如下的優點：

(1) 不需要產生投影數據庫，大大節約了存儲空間；

(2) 由位置信息直接定位到序列數據庫中，不需要多次掃描數據庫及投影數據庫，減少時間花銷。

在實驗中，PBSAM算法展現出高于PrefixSpan算法的時間和空間效率，證明了算法的有效性和高效性。但是，本文提出的序列挖掘算法在時間和空間上都還有提升的空間，算法也可以尋找更廣闊的應用空間，這都是未來應該著重研究的領域。

[1] Agrawal R,Srikant R.Mining sequential patterns[C]//Proceedings of the 11th International Conference on Data Engineering.IEEE Computer Society,1995:3-14.

[2] 毛國君,段麗娟,王實,等.數據挖掘原理與算法[M].2版.北京:清華大學出版社,2007:217-218.

[3] 陳卓,楊炳儒,宋威,等.序列模式挖掘綜述[J].計算機應用研究,2008,25(7):1960-1963,1976.

[4] 羅春雨,毛國君,邱洪君.序列分析技術在DNA序列挖掘中的應用[J].計算機系統應用,2005(12):22-25.

[5] Agrawal R,Imieliński T,Swami A.Mining association rules between sets of items in large databases[N].ACM SIGMOD Record,1993,22(2):207-216.

[6] Srikant R,Agrawal R.Mining sequential patterns:generalizations and performance improvements[C]//Proceedings of the 5th International Conference on Extending Database Technology:Advances in Database Technology,1996:3-17.

[7]HanJ,PeiJ,YinY.Miningfrequentpatternswithoutcandidategeneration[C]//Proceedingsofthe2000ACMSIGMODInternationalConferenceonManagementofData.NewYork,NY,USA:ACMPress,2000:1-12.

[8]HanJ,PeiJ,Mortazavi-AslB,etal.FreeSpan:frequentpattern-projectedsequentialpatternmining[C]//Proceedingsofthe6thACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMining.NewYork,NY,USA:ACMPress,2000:355-359.

[9]PeiJ,HanJ,Mortazavi-AslB,etal.PrefixSpan:miningsequentialpatternsefficientlybyprefix-projectedpatterngrowth[C]//Proceedingsofthe17thInternationalConferenceonDataEngineering.IEEEComputerSociety,2001:215-224.

[10] 張坤,朱揚勇.無重復投影數據庫掃描的序列模式挖掘算法[J].計算機研究與發展,2007,44(1):126-132.

[11] 張利軍,李戰懷,王淼.基于位置信息的序列模式挖掘算法[J].計算機應用研究,2009,26(2):529-531.

[12] 劉棟,尉永清,薛文娟.基于MapReduce的序列模式挖掘算法[J].計算機工程,2012,38(15):43-45.

[13] 吳信東,謝飛,黃詠明,等.帶通配符和One-Off條件的序列模式挖掘[J].軟件學報,2013,24(8):1804-1815.

[14] 劉端陽,馮建,李曉粉.一種基于邏輯的頻繁序列模式挖掘算法[J].計算機科學,2015,42(5):260-264.

[15] 朱揚勇,熊赟.DNA序列數據挖掘技術[J].軟件學報,2007,18(11):2766-2781.

[16] 熊赟,陳越,朱揚勇.DnaReSM:一個基于多支持度的DNA重復序列挖掘算法[J].計算機科學,2007,34(2):211-212,封四.

[17] 周溜溜,業寧,徐昇,等.基于頻繁子樹挖掘的DNA重復序列識別方法[J].微電子學與計算機,2011,28(9):193-196,201.

[18] 姜華,孟志青,周克江.DNA序列頻繁近似模式挖掘[J].生物信息學,2013,11(1):11-15.

[19] 毛國君,楊靜欣.一種基于關聯矩陣的高效DNA序列挖掘算法[J].計算機科學與應用,2015,5(8):271-277.

AN EFFICIENT POSITION-BASED DNA SEQUENCE MINING ALGORITHM

Yang Jingxin Mao Guojun

(SchoolofInformation,CentralUniversityofFinanceandEconomics,Beijing100081,China)

Similar to Apriori algorithm in generating frequent patterns need to scan the database several times, and generate a large number of candidate sets. Algorithms based on the projection database, such as FreeSpan and PrefixSpan, in generating frequent patterns will produce a large number of projection database, taking up a lot of memory space, which have caused a lot of redundancy. Aiming at the shortcomings of the previous sequence mining algorithms, an efficient sequence mining algorithm named PBSMA is proposed in this paper. The PBSMA reduces the scanning of the database by recording the position information of frequent subsequences, and gradually enlarges the length of the frequent patterns by using the position information. The algorithm uses the idea of association matrix and the concept of prefix in PrefixSpan algorithm to search for a longer key pattern. The experimental results show that the PBSMA is more efficient than PrefixSpan algorithm both in time and space.

Sequence mining DNA sequence Position information Association matrix Prefix

2016-05-17。國家自然科學基金項目(61273293)。楊靜欣，碩士生，主研領域：數據挖掘和生物信息學。毛國君，教授。

TP311.1

A

10.3969/j.issn.1000-386x.2017.06.042