面向對比序列模式發現的獨立精確置換檢驗算法

吳 軍，歐陽艾嘉，張 琳

（遵義師范學院信息工程學院，貴州遵義 563000）

0 概述

在現實世界的許多應用中都存在大量的序列數據，如基因序列、文本序列、軌跡序列等。發現序列數據中的序列模式是一個十分重要的研究問題［1-2］。其中，在不同類型的序列數據分布中呈現顯著對比性的模式被稱作對比序列模式［3］。對比序列模式具有非常重要的應用價值，比如在生物蛋白質序列中發現生物標記［4］、在風險評估和管理中預防攻擊行為［5］等。

為了挖掘對比序列模式，一些方法被相繼提出［3，6-8］。這些方法將注意力主要集中在對比性度量選擇以及閾值約束設定上，使得結果中會存在一定數量偶然滿足了算法約束但不能體現真實對比性的對比序列模式。這樣的模式被稱為假陽性模式，它們提供的錯誤信息會對后續分析產生嚴重的干擾。

DSPM-MTC 方法運用統計顯著性檢驗過濾了結果中的部分假陽性對比序列模式［9］，其使用直接計算法來計算p-value 值。在統計顯著性檢驗中，每個被檢驗的對比序列模式會根據其分布信息計算得到一個p-value 值，該值的大小度量了其統計顯著性。對比序列模式的p-value 值越小，則為假陽性模式的可能性就越小。

標準置換檢驗是一種常用的統計顯著性檢驗方法，在非序列數據的模式發現任務中其檢驗效力高于直接計算法［10］。標準置換檢驗通過置換數據類型標簽生成一定數量的置換數據集合，從中計算得到對比性度量值并建立相應的零分布，從而由該零分布計算得出被檢驗的對比序列模式的p-value 值。值得注意的是，標準置換檢驗通常只執行一定次數的置換過程，因此其生成的只是精確零分布的一個近似零分布。使用該近似零分布檢驗挖掘結果存在p-value 值可能為0、零分布共享、結果不唯一和計算開銷大4 個缺點，這些缺點限制了標準置換檢驗的實用性。

經過分析發現，導致標準置換檢驗上述缺點的原因是其構建的零分布是一個共享近似零分布。為此，本文提出一種通過模擬置換過程構建獨立精確零分布的解決方案。通過設計基于獨立精確置換檢驗的IEP-DSP 算法，挖掘統計顯著的對比序列模式，找到原始數據集合中和置換數據集合中的對比序列模式，并根據長度進行分組，計算置換數據集合每組中各個模式的對比性度量值分布，合并置換數據集合每組中的對比性度量值分布構建各自的獨立精確零分布，通過獨立精確零分布計算原始數據集合每組中候選對比序列模式的精確p-value 值，并運用錯誤發現率（False Discovery Rate，FDR）度量將每組的假陽性模式數量約束在置信度為α的統計顯著水平下，以保留更多的真對比序列模式。

1 相關工作

數據挖掘領域的目標是從數據中發現有價值的信息。為了得到正確信息，對數據挖掘算法結果進行評估成為當前熱門研究問題［11-13］。在對比序列模式挖掘任務中，傳統的挖掘算法將注意力放在了約束度量的設計和挖掘效率的優化上［3，6-8］，沒有對挖掘到的對比序列模式進行質量評估，即判別挖掘到的模式是否真實地體現了數據類別的特征。

運用統計顯著性檢驗評估挖掘到的模式質量成為模式發現領域中熱門研究方向，并相繼提出一些不同策略的統計顯著性檢驗方法。這些方法在模式挖掘過程中評估模式質量，或者在挖掘后的結果中進行模式質量評估。BRIN 等［14］運用chi-square 檢驗評估挖掘到統計顯著性模式，然后根據一個設定的閾值過濾掉非統計顯著的模式；ZHANG 等［15］定義了一種新的模式SQ 規則，并提出了一種隨機檢驗的方法用于發現統計顯著的SQ 規則。WEBB［16］認為上述方法隨著假設數量的增加，假陽性模式的數量也會增加，并針對該缺點，提出了直接計算法。LIU等［10］運用標準置換檢驗發現統計顯著模式，并提出一次挖掘技術和預存儲技術減少標準置換檢驗的計算開銷；隨后，研究人員提出2 個改進的置換檢驗算法［17-18］，這2 個算法避開挖掘計算生成零分布，運用westfall-young 置換過程計算得到模式的置換檢驗近似p-value，從而提升了置換檢驗用于模式發現任務的效率；PELLEGRINA 等［19］設計了Spumante 算法，該算法運用一種新穎的無條件檢驗找到統計顯著的模式。無條件檢驗與Fisher 檢驗等條件檢驗相比，對數據的假設要求更少。

以上方法僅在非序列數據的模式發現問題中得到了驗證。為了提高序列數據中挖掘到的模式的質量，HE 等［9］設計了DSPM-MTC 算法挖掘統計顯著的對比序列模式。該算法首先生成每個被檢驗模式的超幾何分布，然后根據該分布直接計算得到模式的p-value 值并進行非統計顯著模式過濾，這種根據服從分布計算p-value 值的方法稱為直接計算法。文獻［10］驗證了在非序列數據集中，標準置換檢驗方法的性能優于直接計算法，但是由于置換的隨機性，標準置換檢驗存在4 個缺點。為探索置換檢驗對序列數據模式發現任務的有效性，并考慮到標準置換檢驗的缺點，本文提出使用獨立精確置換檢驗的IEP-DSP 算法挖掘統計顯著的對比序列模式，以進一步提升報告的對比序列模式的質量。

2 問題描述

2.1 對比序列模式挖掘

令字母表為E=｛e1，e2，…，e|E|｝，一個序列模式t是由E中元素構成的一個有序符號列表，其中mi∈E。如果一個序列模式t包含k個元素，則t的長度為k。給定2 個序列模式t1=和，如果t2的每一個元素m*

j都存在于t1中，且符合t1的元素順序，則t2被稱作是t1的子序列，表示為給定一個包含n條序列的數據集合D=｛s1，s2，…，sn｝和某個序列模式t，t在D中的支持度sup（t，D）被定義為即D中包含t的序列數量。當且僅當序列模式t在D中的支持度超過了自定閾值θsup，t就被認為是D中的頻繁序列模式。目前，已經提出了許多頻繁序列模式挖掘算法［20］，如GSP、Spade、PrefixSpan 等算法。

假設數據集合D含有ν個類型標簽，即D=｛D1，D2，…，Dν｝，若序列模式t在不同Di中的支持度sup（t，Di）呈現顯著對比性，則t被稱為對比序列模式。上述對比性可以由不同的對比性度量量化［21］，例如Growth rate、Diffsup、OddsRatio 等。為了便于闡明本文提出方法，后續討論均假定D=｛D1，D2｝。

對比序列模式挖掘任務的目標是找到所有支持度不小于θsup且對比度性度量值不小于θdis的序列模式，即頻繁且存在對比性的序列模式。

2.2 標準置換檢驗

由于傳統的對比序列模式挖掘算法只考慮了對比性度量約束，從而結果中會存在一定數量的假陽性模式，假陽性模式沒有真正體現不同類型數據集的對比特征。統計顯著性檢驗被廣泛應用于假陽性結果的過濾，運用統計顯著性檢驗進行質量評估時，建立的零假設為對比序列模式在D1和D2中具有相同的分布。同時，每個對比序列模式會被分配一個p-value 值度量其統計顯著性。一個對比序列模式t的p-value 值的定義是在假設零假設為真的前提下，獲得一個至少與t同樣極端的對比序列模式的概率，這里的極端主要體現在對比性度量值的大小。

一般地，可以通過設定一個p-value 值的置信度閾值α決定是否拒絕零假設，但當有多個對比序列模式需要被同時檢驗時，即多重假設檢驗，這種策略會導致假陽性結果的增加。FDR 是多重假設檢驗中常用的度量約束，其定義是整個結果中假陽性對比序列模式比例的期望值，可以使用BH 方法約束整個結果的FDR 值［22］。

標準置換檢驗是一種常用的統計顯著性檢驗方法［10］，其核心過程如圖1 所示。首先，挖掘原始數據集合D1中的候選對比序列模式R；然后，根據零假設生成一定數量的置換數據集合，挖掘并計算每個置換數據集合中對比序列模式的對比性度量值；最后，用所有計算得到的對比性度量值建立該置換檢驗的零分布，并通過該零分布計算所有候選對比序列模式的p-value 值。

圖1 標準置換檢驗過程Fig.1 Process of standard permutation testing

在標準置換檢驗中，窮舉生成一個集合所有可能的置換數據集合是不切實際的，所以通常只產生一定數量的置換數據集合，這導致了構建的零分布不是精確零分布。使用該近似零分布進行模式統計顯著性評估存在以下4 個缺點：

1）某些對比序列模式的p-value 值計算結果為0；

2）共享同一個零分布會增大模式之間的互相影響；

3）同一數據集進行多次檢驗得到的統計顯著的對比序列模式數量不一致；

4）增大置換次數會導致計算開銷的顯著增大。

這些缺點會大幅降低標準置換檢驗的實用性。分析發現造成標準置換檢驗4 個缺點的根本原因是置換過程構建了一個共享近似零分布。因此，快速構建獨立精確零分布是去除4 個缺點的一個可行的解決方案。

3 IEP-DSP 算法

IEP-DSP 算法從序列數量分布出發，運用排列組合的思想模擬置換過程，直接計算得到不同長度對比序列模式的置換檢驗獨立精確零分布。

3.1 候選對比序列模式

IEP-DSP 算法選定WRAcc（Weighted Relative Accuracy）作為對比性度量［21］。給定一個對比序列模式t，其WRAcc 值主要考慮了2 個部分信息：t的相對支持度和t的支持度比率與數據比率的差別。具體的WRAcc 值的計算公式為：

其中：q表示D1中包含t的序列數量，即支持度sup（t，D1）。

IEP-DSP 算法運用Spade 算法挖掘頻繁序列模式［23］。Spade 算法先將數據集中的序列表示為垂直結構，再運用序列聯合操作構建樹形結構以找到所有的頻繁序列模式。如果一個頻繁序列模式的對比性度量值超過了閾值θdis，則該頻繁序列模式被稱為候選對比序列模式，表示為to。

3.2 獨立精確置換檢驗

給定置換數據集合中的一個對比序列模式t′，數據置換過程會改變它在置換數據集合和中的序列數量分布。假設t′在中的支持度為q′，則它在和中的序列數量分布如表1 所示。

表1 模式t 的序列數量分布Table 1 Sequence number distribution of pattern t

從表1 可以看出，給定q′值后其余數值均可以寫成基于q′的計算公式，即對于一個確定的q′，t′在和的數量分布是唯一的。

獨立精確置換檢驗的過程如圖2 所示。首先，找到候選對比序列模式R和所有可能在置換數據集合中出現的對比序列模式R′，并根據模式長度進行各自分組；其次，針對集合中每個對比序列模式t′，計算出其相應的對比性度量值分布；再次，合并集合中每個對比序列模式t′的對比性度量值分布即得到對應的獨立精確零分布；最后，從獨立精確零分布中計算出Rk中每個候選對比序列模式的精確p-value 值。

圖2 獨立精確置換檢驗過程Fig.2 Process of independent exact permutation testing

獨立精確置換檢驗最關鍵的步驟是每個模式對比性度量值分布的計算，該分布由對比性度量值和其在置換數據集合中的次數構成。給定一個t′，t′的每個q′僅對應一個對比性度量值，即wra（t′，q′）。q′的最小值L（t′）為min｛θsup，|D1|+sup（t′，D1）-|D|｝，最大值U（t′）為min｛sup（t′，D），|D1|｝，因此q′∈［L（t′），U（t′）］。

t′的每個對比性度量值在置換數據集合中相應的次數，可以通過以下模擬置換過程計算得出：

其中：g1（t′，q′）表示從D中含有t′的序列中隨機拿出q′條放入中；g2（t′，q′）表示從D中不含t'的序列中隨機拿出|D1|-q′條放入中。因此，g1（t′，q′）與g2（t′，q′）相乘表示只有q′條序列含有t′的置換數據集合的數量。同時，再考慮和內部序列的排列可能性：|D1|！和|D2|！，式（4）的結果即是wra（t′，q′）值在置換數據集合中相應的次數。

從而，Rk中每個候選對比序列模式to的精確p-value 值計算如下：

其中：W表示中比to更極端的模式對應的序列數量分布集合，即W=｛q′|wra（to，sup（to，D1）≤wra（t′，q′））｝。

從式（6）可以得知，最終精確p-value 值的計算公式的分子分母均為式（4）的累加結果。因此，為了減少計算開銷，可以刪去式（4）中的|D1|！和|D2|！項，即：

3.3 約束度量

計算得到Rk中每個候選對比序列模式的精確p-value值后，IEP-DSP 算法運用BH 方法將Rk中的FDR 度量值約束在置信度為α的統計顯著水平下。具體而言，先將Rk中候選對比序列模式按照p-value 值從小到大排序進行排列得到Ck，然后進行如下計算：

最終非統計顯著的對比序列模式ci將被過濾。

3.4 IEP-DSP 算法步驟

根據以上討論，詳細的IEP-DSP 算法步驟見算法1。

算法1 相應的解釋如下：

1）運用pattern_mining（）方法挖掘D1中的候選對比序列模式并放入集合R（第1 步）；運用pattern_mining（）方法挖掘D中的對比序列模式并放入集合R'，R'中的模式即是所有可能在置換數據集合中出現的對比序列模式（第2 步）。

2）運用len_cla（）方法將R和R'中的模式根據長度進行分組（第3 步、第4 步）。對于每個，分別用iend_generation（）方法建立其對應的獨立精確零分布Ik（第5 步、第7 步）。

3）對于每個獨立精確零分布Ik，根據zwr值的降序排列所有對，并根據該順序累加Ik中對的znc值（第8 步～第11 步）。上述操作是為了快速檢索大于等于某個對比性度量值的WRAcc值的個數。每個Ik中最后一個對的znc值即是該獨立精確零分布中所有的WRAcc 值個數。

4）對于Rk中每個候選對比序列模式to，運用find_wra（）方法找到比to更極端的模式數量x；隨后to的精確p-value 值可由x/last_nc（Ik）計算得出，其中last_nc（）返回Ik中最后一個對的znc值（第12 步～第16 步）。

5）運用redundancy_remove（）方法過濾Rk中冗余模式。這里的冗余模式指的是p-value 值大于等于任一子模式的p-value 值的候選對比序列模式；再運用p_sort（）方法根據p-value 值從小到大排序模式后，就能夠使用BH（）方法將每組Rk中的FDR 控制在置信度為α的統計顯著水平下，最終，合并所有即得到統計顯著的對比序列模式集合C*（第17 步～第20 步）。

IEP-DSP 算法各步驟的時間復雜度分析：頻繁模式挖掘算法的時間復雜度分析見文獻［23］，其對IEP-DSP 算法的時間復雜度影響不大；模式長度分組操作可以在模式數量的線性階時間內完成；構建每個對應的獨立精確零分布操作等同于計算R′中每個對比序列模式t′的對比性度量值分布，因此該操作的時間復雜度為O（|R′|avg（U（t′）-L（t′））；排序操作和累加操作可以在統計度量值數量的線性對數階和線性階時間內完成；p-value 值計算操作、去冗余操作和FDR 計算操作均可在模式數量的線性階時間內完成。從上述分析可知：IEP-CSP 算法的時間復雜度主要由構建獨立精確零分布操作決定，即O（|R′|avg（U（t′）-L（t′））。

從式（1）和式（4）中可以發現，如果置換數據集合中2 個對比序列模式和在D中的支持度相同，即sup（，D）等于sup（，D），那么和構建的對比性度量值分布就相同。為了減少IEP-DSP 算法的時間復雜度，支持度相同的模式的對比性度量值分布只需計算1 次即可。因此，IEP-DSP 算法的時間復雜度減少為，其中表示合并R′中所有支持度相同的對比序列模式的結果。

4 實驗

為了驗證IEP-DSP 算法的有效性，在真實數據集和仿真數據集上進行了大量對比實驗。對比的方法包括SP-DSP 算法、DSPM-MTC 算法［9］、ESM 算法［7］和IMP 算法［3］。其中，SP-DSP 算法使用標準置換檢驗挖掘對比序列模式。在所有算法中，ESM 算法和IMP 算法是基于對比性度量約束的挖掘算法，IEP-DSP算法、SP-DSP 算法和DSPM-MTC 算法是基于統計顯著性檢驗的挖掘算法，且這3 個算法均使用FDR 作為約束。所有實驗均使用一臺配置為2.40 GHz CPU和12 GB 內存的電腦設備。

4.1 真實數據集實驗

4.1.1 數據信息

實驗選用了4 個不同類型的真實數據集，即Epitope［24］、Unix［25］、Question［26］和Phospep［27］。Epitope是抗原蛋白序列的數據集；Unix 是用戶操作序列的數據集；Question 是文本序列的數據集；Phospep 是磷酸化肽段序列的數據集。數據集的詳細信息如表2 所示，其中，kmin、kmax和kavg分別表示序列最短長度、序列最長長度和序列平均長度。

表2 真實數據集信息Table 2 Information of the real data sets

4.1.2 真實數據集實驗結果

為評估每個算法的挖掘能力，本文首先對比了每個算法在相同參數下（θsup，θdis，α）報告的對比序列模式數量，結果如圖3 所示。從實驗結果可以看出：基于統計顯著性檢驗的方法得到的模式數量遠小于基于對比性度量約束的方法，這是因為基于統計顯著性檢驗的方法除了考慮對比性度量約束外，還會考慮統計顯著性約束；在基于對比性度量約束的方法中，ESM 算法得到的模式數量非常多，其原因是ESM 算法沒有使用去冗余的方法；在基于統計顯著性檢驗的方法中，IEP-DSP 算法比SP-DSP 算法、DSPM-MTC 算法報告的模式數量更多，這表明獨立精確置換檢驗能夠拒絕更多的零假設。

圖3 每個算法在不同的數據集上報告的對比序列模式數量Fig.3 Number of contrast sequential patterns reported by each method on different data sets

由于真實數據集中對比序列模式真假信息的缺失，不能直接根據各個算法報告的模式結果評價其有效性，因此后續實驗采用一種間接的分類預測方法評估返回的模式質量［28］，即根據每個算法報告的模式信息，為數據集中的每條序列構建一個特征向量，將該向量送入分類器進行預測。特征向量的每個值是該序列和模式的包含關系，即包含為1，不包含則為0。該實驗能夠間接反映挖掘到的模式的真假性的原因是：真對比序列模式本質上體現了不同類型序列數據的相異性。為了減小分類器本身影響，實驗采用了3 種不同類型的分類器，分別為樸素貝葉斯、支持向量機和多層感知機。實驗結果如表3～表5 所示，每個正確率值均取自于10 次預測結果的平均值。

表3 樸素貝葉斯分類器的分類正確率Table 3 Classification accuracy reported by the Naive Bayes classifier

表4 支持向量機分類器的分類正確率Table 4 Classification accuracy reported by the support vector machine classifier

表5 多層感知機分類器的分類正確率Table 5 Classification accuracy reported by the multilayer perceptron classifier

從不同分類器的分類結果中可以看出：基于統計顯著性檢驗的方法的分類正確率高于基于對比性度量約束的方法。因此，可以說明基于統計顯著性檢驗的方法過濾了許多假陽性對比序列模式。以Question 數據集為例，基于對比性度量約束的方法會返回和模式，而基于統計顯著性檢驗的方法只有和模式。is 和the 在英文句子中出現頻率很高，且通常作為語法結構出現，因此它們無法表現句子的差別，從而給分類器造成干擾。

基于統計顯著性檢驗的3 種算法的準確率高低排序為：IEP-DSP 算法>SP-DSP 算法>DSPM-MTC 算法，這個結果證明了IEP-DSP 算法能夠保留更多的真對比序列模式。以Phospep 數據集實驗結果為例，IEP-DSP 算法保留了模式，而SP-DSP 算法和DSPM-MTC 算法只保留了模式，從而導致7 條包含的磷酸化肽段被分類為非磷酸化肽段，此現象說明了模式應該是真對比序列模式。綜上，IEP-DSP 算法不僅能夠過濾大量假陽性模式，還能夠盡可能地保留真對比序列模式。

4.1.3 IEP-DSP 算法與SP-DSP 算法

在2 個置換檢驗算法中，IEP-DSP 算法使用的是獨立精確置換檢驗構建精確零分布，SP-DSP 算法使用的是標準置換檢驗構建共享近似零分布。為了證明獨立精確零分布能夠去除共享近似零分布的4 個缺點，本文進行了以下的討論和實驗。

在SP-DSP 算法報告的結果中，存在一定數量p-value 值為0 的對比序列模式。這是因為SP-DSP算法生成的置換數據集合中沒有找到比這些模式更為極端的模式存在。而在IEP-DSP 算法報告的結果中，所有模式的p-value 值均不為0。這是因為IEP-DSP 算法考慮了所有的置換數據集合，總能找到至少和這些模式一樣極端的模式存在。p-value值等于0 是一個非常差的近似值，它表達的意義是這些模式的統計顯著性無窮大。然而，在某些非常謹慎的應用中，即使α設置得非常小也無法過濾掉這些模式。

在SP-DSP 算法中，不同長度模式的p-value 值均通過同一個共享零分布計算得到；而在IEP-DSP算法中，不同長度模式的p-value 值通過各自的獨立零分布計算得到。在共享零分布中，子模式和超模式之間存在相應序列數據的反單調性，從而在計算p-value 值時會存在一定程度的互相干擾，這個情況導致了SP-DSP 算法報告的模式數量少于IEP-DSP算法。

圖4（a）展示了在Phospep 數據集上運行100 次IEP-DSP 算法和SP-DSP 算法返回的結果。可以看出：SP-DSP 算法結果會有波動，而IEP-DSP 算法結果是唯一的。這是因為標準置換檢驗中置換數據集合的生成存在隨機性，從而構建的近似零分布也存在隨機性，而獨立精確置換檢驗構建的每個獨立精確零分布都是唯一的。標準置換檢驗的隨機性導致了SP-DSP 算法難以判定處于閾值邊界的對比序列模式的統計顯著性，可以采用多次運行取平均的方法，但這必然會導致計算開銷的大幅提升。

圖4（b）展示了在Unix 數據集中IEP-DSP 算法和SP-DSP 算法的運行時間。可以看出：IEP-DSP 算法的運行時間顯著低于SP-DSP 算法的運行時間，其原因是IEP-DSP 算法不需要實際生成置換數據集合，而SP-DSP 算法不僅需要實際生成一定次數的置換數據集合，還需要對置換數據集合進行挖掘。此外，對于不同的數據集合而言，很難確定需要執行多少次置換才能得到一個誤差較小的近似零分布。為了得到更準確的近似零分布，SP-DSP 算法需要增加置換次數，這會導致SP-DSP 算法需要的更多的運行時間。

圖4 2 種算法的對比序列模式數量和運行時間Fig.4 Distinguishing seguential patterns number and running time of two algorithms

綜上，IEP-DSP 算法能夠去除SP-DSP 算法的4 個缺點。這體現了獨立精確置換檢驗相較于標準置換檢驗的優勢。

4.2 仿真數據集實驗

4.2.1 數據生成

由于真實數據集缺少對比序列模式真假的信息，實驗生成了仿真實驗數據進一步驗證各個算法的有效性。仿真數據的生成步驟如下：

1）假設Efalse=｛e1，e2，…，e30｝表示隨機元素字母表，Etrue=｛e31，e32，…，e42｝表示植入元素字母表。

2）從Efalse中隨機挑選元素生成4 000 條長度為30 的序列數據組成D2；從D2中隨機挑選800 條序列數據組成D1。

3）從Etrue中隨機挑選6 個字母作為長度為1 的對比序列模式，并指定任意4 個模式的支持度范圍為150～190，余下2 個模式支持度范圍為40～80。6 個模式的支持度的和等于800。為每個模式選擇1 個位置進行植入，具體做法是直接用模式替代D1序列中相應元素，同時每條序列數據包含且只包含1 個長度為1 的植入模式。

4）從Etrue中挑選未使用的4 個字母同支持度最高的4 個長度為1 的模式結合生成長度為2 的對比序列模式。其中，支持度最高的2 個長度為1 的模式生成的長度為2 的模式支持度范圍為110～150，其余2 個生成的長度為2 的模式支持度范圍為40～80。植入方式同第3 步。

5）從Etrue中選擇未使用的2 個字母同支持度最高的2 個長度為2 的模式結合生成長度為3 的對比序列模式，這2 個長度為3 的模式的支持度范圍為40～80。植入方式同第3 步。

通過上述步驟，人為植入了6 個長度為1、4 個長度為2 和2 個長度為3 的對比序列模式。同時，在挖掘算法返回的對比序列模式中，如果某個對比序列模式包含Etrue中的元素，則該模式被認定為真對比序列模式；反之，如果某個對比序列模式僅包含Efalse中的元素，則該模式被認定為假陽性對比序列模式。

4.2.2 仿真數據實驗結果

為減小隨機性的影響，實驗共生成了10 組仿真數據集。各個算法返回的對比序列模式信息如表6所示，其中每個結果取自于10 個仿真數據集挖掘結果的平均值。從表6 可以看出，基于對比性度量約束的ESM 算法和IMP 算法都報告了許多對比序列模式，其中大部分模式為假陽性對比序列模式；而基于統計顯著性檢驗的DSPM-MTC 算法、SP-DSP 算法和IEP-DSP 算法報告的模式數量較少，且大部分為真對比序列模式。在這3 種方法中，IEP-DSP 算法報告的模式數量最多，且假陽性對比序列模式最少，這證明了IEP-DSP 算法能過濾掉大量對比性度量約束方法中報告的假陽性模式，且相較于SP-DSP 算法和DSPM-MTC 算法能夠保留更多的真對比序列模式，體現了IEP-DSP 算法挖掘對比序列模式的優勢。值得注意的是，ESM 算法報告了許多真對比序列模式，這是因為ESM 算法沒有使用去冗余方法，從而導致了大量真對比序列模式實際上提供了重復的信息。

表6 不同算法的真對比序列模式和假陽性模式數量Table 6 Number of true distinguishing seguential patterns and false positive patterns of different algorithms

5 結束語

為過濾對比序列模式挖掘算法中存在的大量假陽性模式，本文提出一種面向對比序列模式的獨立精確置換檢驗挖掘算法。該算法能為不同長度的模式分別構建獨立精確零分布，從而能夠計算出精確p-value 值。實驗結果表明，該算法不僅能夠去除一定數量的假陽性對比序列模式，且能夠比其他統計顯著性檢驗方法保留更多的真對比序列模式，驗證了獨立精確置換檢驗相較于標準置換檢驗的優越性。此外，本文算法傾向于保留較短的對比序列模式，主要是因為其采用了去冗余方法，即如果一個對比序列模式t的p-value 值大于其任何一個子模式tsub的p-value 值，則該對比序列模式被認定為冗余模式。由于t和tsub的支持度具備反單調性關系，因而tsub會對t的統計顯著性產生影響，但該影響不具備反單調性關系。單純地運用p-value 值比較方法能夠去除掉一定數量的冗余模式，但是也會過濾掉一些非冗余模式。因此，下一步將研究更優的去除子對比序列模式統計顯著性影響的方法。