[發明專利]一種基于PHMM模型的差分可辨性基因序列聚類方法

有效

• 申請號: 202110738987.7
• 申請日: 2021-06-30
• 公開（公告）號: CN113380330B
• 公開（公告）日: 2022-07-26
• 發明（設計）人: 尚濤;任旭杰;楊英;姜亞彤;劉建偉
• 申請（專利權）人: 北京航空航天大學
• 主分類號: G16B40/30
• 分類號: G16B40/30;G16B30/00
• 代理公司: 北京慧泉知識產權代理有限公司 11232
• 代理人: 王順榮;唐愛華

1.一種基于PHMM模型的差分可辨性基因序列聚類方法，其特征在于，它包含以下步驟：

步驟1：輸入基因序列數據集記錄數為n，初始化算法迭代輪數r＝1；隨機生成K個PHMM模型

步驟2：根據Viterbi算法計算n條基因序列數據對每個PHMM模型輸出的分數O_i表示第i條基因序列數據，表示第r輪迭代的第j個PHMM模型；按最高分數對應的PHMM模型將序列劃分到相應的聚類

步驟3：根據迭代輪數是否事先指定閾值，確定該輪迭代用于保護匹配狀態和插入狀態下發射觀測符號a的概率的差分可辨性隱私參數ρ_r，采用拉普拉斯機制實現差分可辨性隱私保護；

步驟4：構建新的聚類中心模型；以極大似然估計法計算第k(k＝1,2,..,K)個聚類內的序列數據中隱狀態s₁到s₂的轉移概率和隱狀態s對發射觀測符號a的發射概率；對計算得到的發射概率再進行差分可辨性隱私噪聲的添加；

步驟5：計算每個聚類中心模型與上一輪迭代時之間的散度距離若散度距離的和D＝∑_kD_k小于預設的閾值，則認為聚類迭代已經收斂，聚類中心模型不再發生變化，輸出聚類結果C₁,C₂,...,C_K；否則迭代輪數r＝r+1，并重復迭代執行步驟2～步驟5。

2.根據權利要求1所述的一種基于PHMM模型的差分可辨性基因序列聚類方法，其特征在于：在步驟1中，具體過程如下：輸入序列數據集共有n條記錄，表示為O＝{O₁,O₂,...,O_n}；其中每條序列長度為L；聚類算法開始前，迭代輪數r初始化為1；隨機生成K個PHMM模型

其中a_kl表示隱狀態k到l的轉移概率，e_k(a)表示隱狀態k下發射觀測符號a的概率。

3.根據權利要求1所述的一種基于PHMM模型的差分可辨性基因序列聚類方法，其特征在于：在步驟2中，令為將子序列x₁,...,x_m與結束于狀態M_n的子模型的最優路徑匹配的對數幾率；和分別表示以狀態I_n和D_n結束的最優路徑的對數幾率；Viterbi算法的通式如下：

三者的最大值即為序列對應最優路徑的對數幾率，回溯后能找到最優路徑；計算出每條序列對每個PHMM的分數，并分配到分數最高的PHMM對應的類C_i表示第i條序列對應的類；其中，

表示隱狀態M_n發射觀測符號x_m的概率，表示所有隱狀態發射觀測符號x_m的總概率，表示子序列x₁,...,x_m-1與結束于狀態M_n的子模型的最優路徑匹配的對數幾率，表示隱狀態M_n-1到M_n的轉移概率，表示子序列x₁,...,x_m-1與結束于狀態I_n-1結束的最優路徑的對數幾率，表示隱狀態I_n-1到M_n的轉移概率，表示以狀態D_n-1結束的最優路徑的對數幾率，表示隱狀態D_n-1到M_n的轉移概率，表示隱狀態I_n發射觀測符號x_m的概率，表示子序列x₁,...,x_m-1與結束于狀態M_n的子模型的最優路徑匹配的對數幾率，表示隱狀態M_n到I_n的轉移概率，表示子序列x₁,...,x_m-1與結束于狀態I_n結束的最優路徑的對數幾率，表示隱狀態I_n到I_n的轉移概率，表示子序列x₁,...,x_m-1與結束于狀態D_n結束的最優路徑的對數幾率，表示隱狀態D_n到I_n的轉移概率，表示子序列x₁,...,x_m與結束于狀態M_n-1的子模型的最優路徑匹配的對數幾率，表示隱狀態M_n-1到D_n的轉移概率，表示子序列x₁,...,x_m與結束于狀態I_n-1結束的最優路徑的對數幾率，表示隱狀態I_n-1到D_n的轉移概率，表示子序列x₁,...,x_m與結束于以狀態D_n-1結束的最優路徑的對數幾率，表示隱狀態D_n-1到D_n的轉移概率；三者的最大值即為序列對應最優路徑的對數幾率，回溯后即可找到最優路徑。