[發明專利]基于隨機采樣及模體壓縮的差分隱私DNA模體識別的方法

在審

• 申請號: 201810296901.8
• 申請日: 2018-04-03
• 公開（公告）號: CN108664807A
• 公開（公告）日: 2018-10-16
• 發明（設計）人: 吳響;關健;毋文敏;魏裕陽
• 申請（專利權）人: 徐州醫科大學
• 主分類號: G06F21/62
• 分類號: G06F21/62;G06F19/20;G06F19/24
• 代理公司: 北京盛凡智榮知識產權代理有限公司 11616
• 代理人: 晏榮府

1.一種基于隨機采樣及模體壓縮的差分隱私DNA模體識別的方法，其特征在于：

1)首先對原始數據進行隨機采樣，獲得樣本數據集合；

2)設置所求頻繁模體集合長度上限l_L、下限l_U的值，令l等于l_L，并求出其支持度，利用字符表{A、G、C、T}形成所有的長度為l的候選模體集合；

3)對候選模體集合執行樣本數據長度壓縮獲取壓縮后的樣本；

4)在壓縮后的樣本中計算候選模體支持度；

5)對步驟4)的候選模體支持度執行Laplace加噪，獲取候選模體集合的加噪支持度，利用最大支持度修正閾值，此時的加噪支持度與修正后的閾值比較，獲取潛在頻繁模體集合；

6)對步驟4)的候選模體支持度執行Laplace加噪，獲取候選模體集合的加噪支持度，利用平均支持度修正閾值，此時的加噪支持度與修正后的閾值比較，獲取頻繁l模體集合；

7)增加l的值，在步驟5)獲取的潛在頻繁模體集合的基礎上利用向下封閉性質獲取長度為l+1的候選模體集合，并再次執行步驟3)、4)、5)、6)，直到l等于l_U為止，獲得長度為l_L到l_U之間的頻繁模體集合；

8)對頻繁模體集合執行聯合支持度計算；

9)選取最頻繁的N項DNA模體，即TopN頻繁DNA模體。

2.根據權利要求1所述的基于隨機采樣及模體壓縮的差分隱私DNA模體識別的方法，其特征在于：步驟3)中樣本數據長度壓縮具體步驟如下：

首先，利用不相關項刪除原理，對樣本中模體長度初步刪減；

其次，利用連續項壓縮原理，壓縮候選模體中連續出現的相同字符，減小樣本數據的長度，獲得壓縮后的樣本。

3.根據權利要求1所述的基于隨機采樣及模體壓縮的差分隱私DNA模體識別的方法，其特征在于：Laplace加噪機制如下：添加服從Laplace((l_max-l+1)/ε₁)分布的噪音。

4.根據權利要求1所述的基于隨機采樣及模體壓縮的差分隱私DNA模體識別的方法，其特征在于：支持度閾值修正單元具體步驟如下：

1)根據“雙重標準”法，給定序列S的噪聲支持度θ′，估算序列S在轉換后數據集中的真實支持度θ^real；

2)根據序列在轉換后數據集中真實支持度θ^real，進一步估計序列在原始數據集的真實支持度θ。

5.根據權利要求1所述的基于隨機采樣及模體壓縮的差分隱私DNA模體識別的方法，其特征在于：聯合支持度計算具體步驟如下：

1)從頻繁模體中選擇一個索引模體；

2)使用漢明距離計算其余模體與該索引模體之間的漢明距離：如果漢明距離小于容錯指數δ，則將其加噪支持度頻率加入到該索引模體；如果漢明距離大于容錯指數δ，則不進行任何操作，計算出該索引模體的最終近似加噪聯合支持度頻率。