生物序列近似頻繁模式挖掘研究.pdf

1、隨著生物信息學(xué)的快速發(fā)展，人類基因、蛋白質(zhì)測序的實施和完成，積累了大量的生物數(shù)據(jù)。從生物數(shù)據(jù)中挖掘頻繁模式有助于發(fā)現(xiàn)生物序列中潛在的信息、生物基因和蛋白質(zhì)同源性的檢測等。生物序列中頻繁模式的挖掘已經(jīng)成為生物信息領(lǐng)域研究的重要任務(wù)。本文深入研究了生物序列中帶可變長度間隔約束的近似頻繁模式挖掘問題，序列之間相似性的度量使用了編輯距離和生物字符間的評分。此外，本文定義了插入、替換和刪除字符三種近似操作，克服了已有的近似頻繁模式挖掘算法僅僅包含

2、替換字符一種近似操作的不足。本文的主要工作如下:
　　(1)給出了包含插入、替換和刪除字符的三種近似操作的定義，及近似模式匹配與挖掘的相關(guān)定義。為了使用模式的出現(xiàn)頻率判斷該模式是否是頻繁模式，本文給出了近似模式匹配中補償序列數(shù)（Nl,editmax）的推導(dǎo)。由于帶可變長度的近似頻繁模式挖掘具有較大的候選解空間，本文設(shè)計了Apriori-like剪枝策略用于降低候選解空間的維度。
　　(2)本文基于編輯距離度量序列間的相似性，

3、設(shè)計了編輯距離矩陣(A-EDM)和其構(gòu)造函數(shù)，編輯距離矩陣記錄了模式子字符串與序列子字符串之間的最小編輯距離（誤差）。在A-EDM的基礎(chǔ)上，本文設(shè)計了候選模式解集合的矩陣結(jié)構(gòu)(MST)和近似模式匹配算法(APM)計算模式在序列中的近似出現(xiàn)次數(shù)和出現(xiàn)位置。然后本文給出了近似頻繁模式挖掘算法(MAPA)，當(dāng)編輯距離閾值editmax=0時，MAPA算法轉(zhuǎn)變?yōu)榫_頻繁模式挖掘算法。
　　(3)為了對生物序列頻繁模式的挖掘更具有針對性，本

4、文在編輯距離約束的基礎(chǔ)上結(jié)合了生物字符的評分矩陣，設(shè)計了模式與序列之間的匹配得分矩陣(MSM)，MSM中記錄了模式子字符串與序列子字符串之間的最大匹配得分。基于MSM，本文設(shè)計了針對生物序列的近似模式匹配方法(S-APM)，S-APM采用回溯MSM的方式計算模式在序列中的近似出現(xiàn)次數(shù)。隨后本文給出了針對生物序列的近似頻繁模式挖掘算法(MAPS)和多序列共同頻繁模式挖掘算法（co-fp-miner）。co-fp-miner算法中對Apri