（植物學(xué)專業(yè)論文）基于hmm模型的啟動(dòng)子預(yù)測(cè)系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn).pdf

蘭州人學(xué)頌i 學(xué)位論文 摘要 啟動(dòng)子是基因表達(dá)調(diào)控中非常重要的一類順式作用元件 它決定著基因轉(zhuǎn)錄的起始位 置和轉(zhuǎn)錄頻率 因此啟動(dòng)子的研究對(duì)于闡釋基因表達(dá)凋控網(wǎng)絡(luò)的機(jī)制和基因組的功能都具 有非常重要的意義 啟動(dòng)子的識(shí)別作為啟動(dòng)子研究的首要環(huán)節(jié) 詎同益成為生物學(xué)研究的 一個(gè)熱點(diǎn) 傳統(tǒng)啟動(dòng)子識(shí)別是通過(guò)免疫沉淀 突變分析等生物學(xué)實(shí)驗(yàn)來(lái)進(jìn)行的 這些方法 成本高 效率低 極大地限制了啟動(dòng)子研究的進(jìn)展 因此利用計(jì)算機(jī)領(lǐng)域新興的數(shù)據(jù)挖掘 技術(shù)并開(kāi)發(fā)相應(yīng)的軟件來(lái)進(jìn)行啟動(dòng)子預(yù)測(cè)已經(jīng)成為生物信息學(xué)的一個(gè)重要方向 本文通過(guò) 對(duì)啟動(dòng)子的序列特征進(jìn)行深入分析 利用隱馬爾科夫模型 簡(jiǎn)稱為h m m 進(jìn)行數(shù)學(xué)建模 設(shè)計(jì)并編碼實(shí)現(xiàn)了一個(gè)基于h m m 的啟動(dòng)子預(yù)測(cè)軟件系統(tǒng) 本研究獲得了以下結(jié)果 l 設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)基于h m m 的啟動(dòng)子預(yù)測(cè)系統(tǒng) 包括序列輸入 預(yù)處理 模型訓(xùn) 練 未知序列識(shí)別和結(jié)果輸出等部分 本系統(tǒng)能深入挖掘出啟動(dòng)子序列的內(nèi)部統(tǒng)計(jì) 學(xué)規(guī)律 建立相應(yīng)的h m m 用于進(jìn)行啟動(dòng)子預(yù)測(cè) 2 用人類啟動(dòng)子序列和擬南芥啟動(dòng)子序列對(duì)系統(tǒng)進(jìn)行了驗(yàn)汪 驗(yàn)證結(jié)果顯示本系統(tǒng)預(yù) 測(cè)的準(zhǔn)確率較高 通用性較廣 對(duì)人類啟動(dòng)子預(yù)測(cè)的準(zhǔn)確率達(dá)到8 4 5 擬南芥啟動(dòng) 子的準(zhǔn)確率達(dá)到8 3 5 本系統(tǒng)為啟動(dòng)子的預(yù)測(cè)提供了一個(gè)平臺(tái) 極大的提高了啟動(dòng)子的預(yù)測(cè)效率 節(jié)約大量 的人力物力 為啟動(dòng)子的研究提供有力的支持 此外 本系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)方案也可以推 廣為一種通用的序列元件預(yù)測(cè)系統(tǒng)的解決方案 加速各類元件的預(yù)測(cè)和分析 最終將加快 整個(gè)基岡表達(dá)調(diào)控網(wǎng)絡(luò)的構(gòu)建 關(guān)鍵字 啟動(dòng)子預(yù)測(cè) 隱馬爾科夫模型 h m m j a v a 數(shù)學(xué)建模 數(shù)據(jù)庫(kù)設(shè)計(jì) 蘭州人學(xué)碩i 學(xué)位論文 a b s t r u c t p r o m o t e ri sav e r yi m p o r t a n tr e g u l a re l e m e n ti ng e n ee x p r e s s i o n i td e t e r m i n e st h ep o s i t i o no f t r a n s c r i p t i o n a ls t a r tp o i n ta n dt h ef r e q u e n c yw i t hw h i c ht h eg e n ei st r a n s c r i b e d t h er e c o g n i t i o no f p r o m o t e rw i l lp l a ya ni m p o r t a n tr u l ei nu n d e r s t a n d i n gt h eb i o l o g i c a lm e c h a n i s m a st h ep r i m a r y k e yi nt h ep r o m o t e rr e s e a r c h t h ep r o m o t e rr e c o g n i t i o ni sb e c o m i n gah o t s p o tn o w a d a y s t r a d i t i o n a lm e t h o d sf o rp r o m o t e rr e c o g n i t i o ni sb i o l o g ye x p e r i m e n t s s u c ha s i m m u n o p r e c i p i t a t i o na n dm u t a t i o na n a l y s i s b e c a u s et h e s e sm e t h o d sa r ew i t hh i g hc o s ta n d l o w e f f i c a c y t h e yc r a m p e dt h ed e v e l o p m e n to ft h ep r o m o t e rr e s e a r c h s ou s i n gd a t am i n i n g t e c h n o l o g yt od e v e l o ps o m es o f t w a r ef o rp r o m o t e rr e c o g n i t i o ni sb e c o m i n gav e r yi m p o r t a n t r e s e a r c hd i r e c t i o ni nb i o i n f o r m a t i c s i nt h i sa r t i c l e w ed e s i g n e dap r o m o t e rr e c o g n i t i o ns y s t e m b a s e do nh i d d e nm a r k o vm o d e l s i tc a nf i n ds t a t i s t i c sl a wo u td e e p l yi n s i d et h ep r o m o t e rs e q u e c e s a n du s ei tf o rp r o m o t e rr e c o g n i t i o n t h em a i nw o r ka n dr e s u l t sa r ea sf o l l o w s 1 d e s i g n e dap r o m o t e rr e c o g n i t i o ns y s t e mb a s e do nh i d d e nm a r k o vm o d e l s i n c l u d i n gs e q u e n c e i n p u t m e n t p r e p r o c e s s i n g l e a r n i n g p r o m o t e rp r e d i c t i o na n do u t p u t 2 u s i n gh u m a np r o m o t e r sa n da r a b i d o p s i st h a l i a n ap r o m o t e r s t ot e s t t h er e s u l ts h o w st h es y s t e m s s e n s i t i v i t yf o rh u m a np r o m o t e rp r e d i c t i o ni s8 4 5 a n d8 3 5 f o ra r a b i d o p s i st h a l i a n ap r e d i c t i o n t h es y s t e mi so fg e n e r a l i t ya n dh i g he f f i c i e n c y i tc a ng r e a t l yp r o m o t et h ee f f i c i e n c yo f p r o m o t e rr e c o g n i t i o na n dp r o v i d es t r o n gs u p p o r tf o rp r o m o t e rr e s e a r c h b e s i d e s i to f f e r sc u r r e n t s o l u t i o na n dc a na c c e l e r a t et h ep r o c e s so ft h eo t h e re l e m e n t s r e c o g n i t i o n f i n a l l yi m p r o v et h e c o n s t r u c t i o no fr e g u l a t o r yn e t w o r k s k e yw o r d s p r o m o t e rp r e d i c t i o n h i d d e nm a r k o vm o d e l s h m m j a v a m a t h e m a t i c a lm o d e l i n g d a t a b a s ed e s i g n 蘭州人學(xué)顧i 學(xué)位論文 原創(chuàng)性聲明 本人鄭重聲明 本人所呈交的學(xué)位論文 是在導(dǎo)師的指導(dǎo)下獨(dú)立進(jìn)行研究所取得的成 果 學(xué)位論文中兒引用他人己經(jīng)發(fā)表或未發(fā)表的成果 數(shù)據(jù) 觀點(diǎn)等 均已明確注明出處 除文中已經(jīng)注明引用的內(nèi)容外 不包含任何其他個(gè)人或集體已經(jīng)發(fā)表或撰寫(xiě)過(guò)的科研成果 對(duì)本文的研究成果做出重要貢獻(xiàn)的個(gè)人和集體 均已在文中以明確方式標(biāo)明 本聲明的法律責(zé)任由本人承擔(dān) 論文作者簽名 同期 社 關(guān)于學(xué)位論文使用授權(quán)的聲明 本人在導(dǎo)師指導(dǎo)下所完成的論文及相關(guān)的職務(wù)作品 知識(shí)產(chǎn)權(quán)歸屬蘭州 大學(xué) 本人完全了解蘭州大學(xué)有關(guān)保存 使用學(xué)位論文的規(guī)定 同意學(xué)校保 存或向國(guó)家有關(guān)部門(mén)或機(jī)構(gòu)送交論文的紙質(zhì)版和電子版 允許論文被查閱和 借閱 本人授權(quán)蘭州大學(xué)可以將本學(xué)位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù) 庫(kù)進(jìn)行檢索 可以采用任何復(fù)制手段保存和匯編本學(xué)位淪文 本人離校后發(fā) 表 使用學(xué)位論文或與該論文直接相關(guān)的學(xué)術(shù)論文或成果時(shí) 第一署名單位 仍然為蘭州大學(xué) 保密論文在解密后應(yīng)遵守此規(guī)定 論文作者簽名 醢蔓 導(dǎo)師簽名 日期 砷 6 7 蘭州人學(xué)碩l 學(xué)位論文 1 1 啟動(dòng)子 1 1 1 啟動(dòng)子預(yù)測(cè)的意義 第一章緒論 隨著人類基因組計(jì)劃和各種模式生物測(cè)序工作的完成 人類積累了大量的生物學(xué)數(shù)據(jù) 并且這些數(shù)據(jù)還在以幾何級(jí)數(shù)增長(zhǎng) 但是數(shù)據(jù)并不是知識(shí) 怎么樣對(duì)這些數(shù)據(jù)進(jìn)行分析和 處理 進(jìn)而從這些看似雜亂無(wú)章的數(shù)據(jù)中探索和發(fā)現(xiàn)生命的規(guī)律和真諦 是目前人類所面 臨的巨大挑戰(zhàn) 在測(cè)序得到的數(shù)據(jù)中 并非所有都是編碼蛋白質(zhì)的基因 恰恰相反 編碼 區(qū)只占了全部序列的很小一部分 以人類為例 在大約3 0 億對(duì)堿基中 只有3 5 是編 碼蛋白質(zhì)的編碼區(qū) 而剩下的9 5 以上是非編碼區(qū) 即所謂的 j u n kd n a 9 他們并不編 碼蛋白質(zhì) 雖然目前對(duì)他們的功能還不清楚 但是從生物進(jìn)化的觀點(diǎn)看 他們必然在遺傳 信息的傳遞和表達(dá)中發(fā)揮著不可或缺的作用 現(xiàn)在普遍的認(rèn)識(shí)是 非編碼區(qū)與基因在四維 時(shí)空的表達(dá)凋控有關(guān) 岡此也把這部分非編碼區(qū)序列叫做調(diào)控區(qū) 如果說(shuō)編碼區(qū)是創(chuàng)建生 命大廈的基石 那么凋控區(qū)就是這座宏偉大廈的設(shè)計(jì)藍(lán)圖 是他們?cè)谥笓]著這座大廈的構(gòu) 建 在調(diào)控區(qū)中分布著形形色色的調(diào)控元件 目前已知的有增強(qiáng)子 啟動(dòng)子 沉默子等 而其中的啟動(dòng)子 可以況是最重要的一類調(diào)控元件 它控制著基因表達(dá)的第一道關(guān)卡 基囚的轉(zhuǎn)錄 基因的表達(dá)調(diào)控體現(xiàn)在很多層面上 但主要的調(diào)控是轉(zhuǎn)錄水平的調(diào)控 而啟 動(dòng)子控制基因轉(zhuǎn)錄的起始位置和轉(zhuǎn)錄頻率 所以啟動(dòng)子可以說(shuō)足扮演著一個(gè)遺傳丌關(guān)的角 色 只有它r 丌啟了 遺傳信息彳 能進(jìn)行表達(dá) 因此 對(duì)啟動(dòng)子的研究將對(duì)理解整個(gè)基因轉(zhuǎn) 錄調(diào)控機(jī)制和表達(dá)模式進(jìn)而理解整個(gè)調(diào)控網(wǎng)絡(luò)起到至關(guān)重要的作用 也正是由于啟動(dòng)子在 調(diào)控中的重要作用 其正同益成為一個(gè)研究熱點(diǎn) 啟動(dòng)子的預(yù)測(cè)作為對(duì)啟動(dòng)子研究的自訂提 就自然而然成為重中之重了 啟動(dòng)子對(duì)轉(zhuǎn)錄的調(diào)控位于整個(gè)基因表達(dá)調(diào)控網(wǎng)絡(luò)的最上游 它相當(dāng)于丌關(guān)控制著整個(gè) 調(diào)控體系的丌啟 因此對(duì)啟動(dòng)子的研究對(duì)于在基岡層面 卜研究轉(zhuǎn)錄調(diào)控關(guān)系 進(jìn)而構(gòu)建表 達(dá)調(diào)控網(wǎng)絡(luò)有非常重要的作用 而啟動(dòng)子研究的自訂提就是啟動(dòng)子的識(shí)別 啟動(dòng)子的預(yù)測(cè)還 為新的未知基因尤其是真核生物基岡的發(fā)現(xiàn)提供了一條新途徑 因?yàn)樵谡婧松镏?編碼 蛋白質(zhì)的基因只占了很小的一部分 它們就像是一個(gè)個(gè)小島 分布在無(wú)垠的序列海洋中 傳統(tǒng)發(fā)現(xiàn)新基岡的方法是找劍首個(gè)外顯子 但是首個(gè)外顯子往往是很難找的 尤其足當(dāng)它 蘭州人學(xué)碩 i 學(xué)位論文 很短或處在未翻譯區(qū)時(shí) 通過(guò)啟動(dòng)子預(yù)測(cè) 我們可以i 口j 接找到首個(gè)外顯子的轉(zhuǎn)錄起始位點(diǎn) 這也就意味著找到了基因的一端 所以 找到啟動(dòng)子就意味著找到基因 啟動(dòng)子的預(yù)測(cè)還 為人類從轉(zhuǎn)錄調(diào)控層面攻克各種疑難雜癥提供了新的方法 由于基因的轉(zhuǎn)錄調(diào)控對(duì)人類的 健康有著直接影響 人類的很多癌癥 如胃癌 直腸癌等都與基因的不正常表達(dá)有關(guān) 如 果我們找到了調(diào)節(jié)這些基因進(jìn)行轉(zhuǎn)錄的啟動(dòng)子 就可以設(shè)法使這些基因的表達(dá)變慢 甚至 是完全破壞這些基因 從而從源頭掐斷病源 m c k n i g h ts le ta 1 1 9 8 2 啟動(dòng)子預(yù)測(cè)建立的 預(yù)測(cè)體系也將為別的調(diào)控元件的預(yù)測(cè)提供參考模型 以便于更好的預(yù)測(cè)別的調(diào)控元件 1 1 2 啟動(dòng)子的結(jié)構(gòu)和功能 1 1 2 1 啟動(dòng)子的結(jié)構(gòu) 1 1 2 1 1 原核啟動(dòng)子的結(jié)構(gòu) 原核啟動(dòng)子的核心區(qū)域一般在轉(zhuǎn)錄起始位點(diǎn)上游2 0 0 b p 至下游1 0 0 b p 的范圍內(nèi) 距基 因編碼區(qū)起點(diǎn)2 0 6 0 0 b p 杜耀華等2 0 0 2 原核啟動(dòng)子最顯著的特征就足在核心區(qū)域存在 小段的保守序列 通過(guò)對(duì)已知大量的原核生物啟動(dòng)子序列的分析 人們發(fā)現(xiàn)大多數(shù)原核啟 動(dòng)子存在著以下幾個(gè)保守區(qū)域 轉(zhuǎn)錄起始位點(diǎn) t t s 一般都是嘌呤堿基 通常是在序列c a t 的中心 p r i b n o w 框 它是一段富含a t 堿基的六聯(lián)體核苷酸序列 它的中心一般位于轉(zhuǎn)錄起始 位點(diǎn)上游1 0 b p 附近 因此也叫做一1 0 區(qū)域 為了方便 人們把轉(zhuǎn)錄起始位點(diǎn)記為1 沿轉(zhuǎn)錄 方向順流而下記為正 逆流而上的啟動(dòng)子部分均用負(fù)值表示 p r i b n o w 框的一致性序列足 t a t a a t 每個(gè)位點(diǎn)的保守頻度為瓦 鴿 死 以 4 五 可以看出在p r i b n o w 框中 第6 位t 的 保守性很高 因此這個(gè)t 也被叫做保守t 它幾乎存在于目自 發(fā)現(xiàn)的所有原核啟動(dòng)子中 推測(cè)其在結(jié)合r n a 聚合酶時(shí)起十分重要的作用 p r i b n o w 框是原核啟動(dòng)子中非常蕈要的一 類元件 r n a 聚合酶在此部位與啟動(dòng)子進(jìn)行結(jié)合 因此p r i b n o w 框也被稱為結(jié)合位點(diǎn) 當(dāng) r n a 聚合酶結(jié)合到p r i b n o w 框上后 在r n a 聚合酶的誘導(dǎo)下 p r i b n o w 框中d n a 序列首 先在轉(zhuǎn)錄方向上解 1 然后進(jìn)一步擴(kuò)大成1 7 個(gè)核苷酸長(zhǎng)度的泡狀物 即所謂的丌放性起始 子復(fù)合物 在泡狀物中 r n a 聚合酶從模板鏈了i 始順流而下轉(zhuǎn)錄r n a 產(chǎn)物 據(jù)推測(cè)p r i b n o w 框之所以成為第一個(gè)解旋的部位可能與它富含a t 堿基有關(guān) 岡為a t 堿基對(duì)問(wèn)只有兩個(gè)氫 鍵 作用力較弱 相比有三個(gè)氫鍵相互作用的g c 堿基更易于打丌 原核啟動(dòng)子的另一個(gè)保守區(qū)是位于一3 5 b p 附近的序列 稱作s e x t a m a 框 也叫 3 5 區(qū)序 2 蘭州人學(xué)碩i 學(xué)位論文 列 它的一致性序列為t t g a c a 各堿基出現(xiàn)頻率如下 五 毛g 7 a 6 c 5 4 其中t t g 具 有很高的保守性 s e x t a m a 框是原核生物啟動(dòng)子的r n a 聚合酶識(shí)別位點(diǎn) r n a 聚合酶全酶 依靠 因子識(shí)別s e x t a m a 框并與之結(jié)合 因此s e x t a m a 框的核苷酸結(jié)構(gòu) 在很大程度上決定 了啟動(dòng)子的強(qiáng)度 r n a 聚合酶易識(shí)別強(qiáng)的啟動(dòng)子 p r i b n o w 框和s e x t a m a 框序列幾乎存在于所有已經(jīng)發(fā)現(xiàn)的原核啟動(dòng)子中 可見(jiàn)這兩個(gè)元 件對(duì)原核生物的轉(zhuǎn)錄至關(guān)重要 研究發(fā)現(xiàn) p r i b n o w 框和s e x t a m a 框協(xié)同作用 控制著原核 生物轉(zhuǎn)錄的丌始 在這個(gè)過(guò)程中 r n a 聚合酶通過(guò) 因子首先識(shí)別s e x t a m a 框 然后與之 結(jié)合 隨后再與p r i b n o w 框結(jié)合 并在p r i b n o w 框?qū) n a 序列打開(kāi) 形成丌放性啟動(dòng)子復(fù) 合物 轉(zhuǎn)錄也就開(kāi)始了 對(duì)于r n a 聚合酶的這種先結(jié)合s e x t a m a 框 再與p r i b n o w 框結(jié)合 的行為 目前存在著兩種說(shuō)法 一種是滑動(dòng)假說(shuō) 即r n a 聚合酶分子沿著模板鏈從s e x t a m a 框滑動(dòng)到p r i b n o w 框 另一種貝0 認(rèn)為r n a 聚合酶分子比較長(zhǎng) 當(dāng)它的一端與s e x t a m a 框結(jié) 合后 它的分子的某一與p r i b n o w 框序列親和性很高的部位詐好到達(dá)p r i b n o w 框 從而與之 結(jié)合 后者似乎更為合理 因?yàn)橐延袑?shí)驗(yàn)表明 r n a 的分子很大 它的覆蓋范圍大概為7 0 b p 左右 因此當(dāng)它一端與s e x t a m a 框結(jié)合后 分子的其它部位完全可以到達(dá)p r i b n o w 框 這兩 個(gè)序列不僅決定在轉(zhuǎn)錄的起始與否 而且對(duì)轉(zhuǎn)錄的效率也有很大的影響 這兩個(gè)序列還對(duì) 啟動(dòng)子的活性有很重要的影響 目前發(fā)現(xiàn)影響啟動(dòng)子活性的若干突變體的突變位點(diǎn)都位于 s e x t a m a 框序列中或者p r i b n o w 框序列附近 位于s e x t a m a 框和p r i b n o w 框之間的堿基序列并不特別重要 但是它們之間的距離卻十 分重要 天然啟動(dòng)子中一般都是1 5 2 0 b p 實(shí)驗(yàn)表明s e x t a m a 框和p r i b n o w 框之間的距離為 1 7 b p 時(shí)轉(zhuǎn)錄的效率最高 據(jù)推測(cè) 這樣的距離正好有利于r n a 聚合酶與s e x t a m a 框和 p r i b n o w 框的結(jié)合 因?yàn)檫@個(gè)最佳距離使得各個(gè)位點(diǎn)幣好保持在雙螺旋的同一側(cè)從而促使它 們和r n a 聚合酶結(jié)合 1 1 2 1 2 真核啟動(dòng)子的結(jié)構(gòu) 真核生物的啟動(dòng)子結(jié)構(gòu)相對(duì)于原核生物要復(fù)雜得多 真核生物中有3 類啟動(dòng)子 ntt u n g e ta 1 分別與真核生物中三類4 i 同的r n a 聚合酶即r n a 聚合酶i i i i i i 結(jié)合 i 類啟動(dòng) 子比較單一 由上游控制元件 u c e 和核心啟動(dòng)子兩部分組成 它與r n a 聚合酶i 結(jié)合 主要用于調(diào)節(jié)核糖體r n a 5 8 s 1 8 s a n d2 8 sr r n a s 的合成 1 i 類啟動(dòng)子與r n a 聚合酶i i 結(jié)合 主要參與蛋白質(zhì)基因和部分s n r n a 的轉(zhuǎn)錄 由于編碼蛋白質(zhì)的基因各種各樣 因此 參與轉(zhuǎn)錄調(diào)控的相應(yīng)的啟動(dòng)子序列也不盡相同 所以i i 類啟動(dòng)子是最復(fù)雜的 i i i 類啟動(dòng)子 又可以分為三個(gè)亞類 第一亞類和第二亞類位于轉(zhuǎn)錄起始位點(diǎn)下游 因此又稱為內(nèi)部啟動(dòng) 蘭州人學(xué)碩i 學(xué)位論文 子 它們主要負(fù)責(zé)調(diào)控5 sr r n a 和t r n a 的轉(zhuǎn)錄 第三亞類啟動(dòng)子和自i 兩類一樣 是上游啟 動(dòng)子 主要用于調(diào)控s n r n a 的合成 因?yàn)樵谡婧松镏芯幋a蛋白質(zhì)的基因的轉(zhuǎn)錄主要是i i 類啟動(dòng)子進(jìn)行調(diào)控的 所以目前 的啟動(dòng)子預(yù)測(cè)主要是i i 類啟動(dòng)子的預(yù)測(cè) i i 類啟動(dòng)子有由核心啟動(dòng)子和上游啟動(dòng)予元件組 成 l 核心啟動(dòng)子是位于轉(zhuǎn)錄起始位點(diǎn)附近大約1 0 0 b p 的 4 段d n a 序列 是能夠使r n a 聚合酶i i 轉(zhuǎn)錄正常起始的最小d n a 序列 a n d e r sgpe ta 1 1 9 9 9 s m a l este ta 1 2 0 0 3 它由 t a t a 框 起始子 i n r t f i i b 識(shí)別元件 b r e 和下游啟動(dòng)子元件 d p e 四個(gè)部分組成 b u t l e rj e fe ta 1 2 0 0 2 s m a l es te ta 1 2 0 0 3 但是這四個(gè)部分并不一定同時(shí)出現(xiàn)在同一個(gè)核 心啟動(dòng)子中 通過(guò)對(duì)取自e p d p 6 r i e rr ce ta 1 19 9 7 p i e rr ce ta 1 2 0 0 0 和d b t s s s u z u k i y e ta 1 2 0 0 2 的1 0 0 0 0 條人的啟動(dòng)子序列進(jìn)行分析發(fā)現(xiàn) 在這些序列中只有5 0 存在起始子 而在這5 0 的序列中同時(shí)存在t a t a 框的只有1 0 左右 分析還發(fā)現(xiàn)下游啟動(dòng)子元件的存 在并不依賴于t a t a 框和起始子 但是t f i i b 識(shí)別元件只存在于t a t a 框缺失的序列中 核 心啟動(dòng)子單獨(dú)起作用時(shí)只能確定轉(zhuǎn)錄起始位點(diǎn)和產(chǎn)生基礎(chǔ)水平的轉(zhuǎn)錄 到b r e t a t a b o x ll 毒i n r 囂yl 懦鬻 圖1 1 核心啟動(dòng)子結(jié)構(gòu)圖 s t e p h e nt s m a l ee ta l2 0 0 3 a t a t a 框 又稱h o g n e s s 框 g o l d b e r g h o g n e s s 框 是最早被發(fā)現(xiàn)的真核生物啟動(dòng)子 元件 g o l d b e r gm l 1 9 7 9 b r e a t h n a c hr e ta 1 1 9 8 1 最早注意到它是因?yàn)樗慕Y(jié)構(gòu)和功能都 和原核啟動(dòng)子的p r i b n o w 框相似 但是后來(lái)的研究表明它和p r i b n o w 框并不是同源的 t a t a 框是一段富含a t 堿基的序列 其堿基一致性序列為t a t a a a a 各位點(diǎn)的保守頻度為 瓦 4 4 a 6 4 4 它通常位于轉(zhuǎn)錄起始位點(diǎn)上游約一3 0 到 5 0 b p 處 t a t a 框存在于大多 數(shù)真核基因中 作為r n a 聚合酶的結(jié)合處之一 它起著精確選擇轉(zhuǎn)錄起始位點(diǎn)的作用 也 就是說(shuō)t a t a 框決定了轉(zhuǎn)錄起始點(diǎn)的選擇 r n a 聚合酶與t a r a 框牢固結(jié)合之后爿 能丌始 4 蘭州人學(xué)碩 學(xué)位論文 轉(zhuǎn)錄 由于r n a 聚合酶的拓?fù)浣Y(jié)構(gòu)是固定的 其結(jié)合位點(diǎn)和催化位點(diǎn)的距離也是固定的 因此其決定了起始點(diǎn)的選擇 除了精確起始轉(zhuǎn)錄之外 t a t a 框還能影響轉(zhuǎn)錄的速率 體外 實(shí)驗(yàn)證明 t a t a 框中任何一個(gè)堿基的改變都會(huì)顯著降低轉(zhuǎn)錄效率 b r e a t h n a c hre ta 1 1 9 8 1 g r o s s c h e d lre ta 1 1 9 8 0 w a s y l y kbe ta 1 1 9 8 0 g r o s v e l dg ce ta 1 1 9 8 1 h usle ta 1 1 9 8 1 在伴清蛋白基因中 當(dāng)t a t a 框突變?yōu)閠 a g a 后 轉(zhuǎn)錄效率大大降低 如人類的b 珠蛋白 基因啟動(dòng)子中t a t a 序列發(fā)生突變 p 珠蛋白產(chǎn)量就會(huì)大幅度下降而引起貧血癥 b 起始子 i n r 它是一個(gè)與t a t a 框同等重要的核心啟動(dòng)子元件 統(tǒng)計(jì)分析顯示 圍 繞著轉(zhuǎn)錄起始點(diǎn)的具有i n r 活性的序列保守性很低 但是對(duì)部分功能性的i n i t i a t o r 元件進(jìn)行 的突變和計(jì)算機(jī)分析仍然揭示出規(guī)律性的結(jié)果 1 1 1 r 偏好的是一段富含嘧啶的序列一p yp y a 1 n t a p y p y 其中 1 位a 3 位t 或a 以及一1 位的嘧啶對(duì)i n i t i a t o r 活性最為關(guān)鍵 j a v a h e r y re ta 1 1 9 9 4 1l oke ta 1 1 9 9 6 i n r 在功能上與t a t a 盒類似 它能起始基礎(chǔ)轉(zhuǎn)錄 能介導(dǎo) 上游至少一部分激活因子的調(diào)控作用 并能決定轉(zhuǎn)錄起始點(diǎn)的位置 對(duì)海膽組蛋白h 2 a 包 括起始子的部分進(jìn)行敲除顯示 轉(zhuǎn)錄的效率顯著降低 而且轉(zhuǎn)錄起始位點(diǎn)發(fā)生位移 g r o s s c h e d lre ta 1 1 9 8 0 c t f i i b 識(shí)別元件 b r e 它是唯一目前已經(jīng)清楚的除了t f i i d 之外還能被別的轉(zhuǎn)錄因 子識(shí)別的核心啟動(dòng)子元件 它在上游緊挨著t a t a 框 共同的保守序列為 g c g c g a c g c c 其能夠被t f i i b 識(shí)別 在真核細(xì)胞中調(diào)節(jié)前起始復(fù)合物的裝配 d 下游啟動(dòng)子元件 被認(rèn)為是核心啟動(dòng)子的下游模體 是t a t a 缺失的啟動(dòng)子結(jié)合純 t f i i d 所必須的元件 b u t l e rjefe ta 1 2 0 0 2 b u r k etw e ta 1 1 9 9 8 k a d o n a g aj te ta 1 2 0 0 2 它在果蠅和人類啟動(dòng)子序列中捌有一樣的保守序列 下游啟動(dòng)子元件通常存在于 t a t a 框缺失的啟動(dòng)子序列中 和i n r 一起發(fā)揮作用 它的核心區(qū)域一般位于轉(zhuǎn)錄起始位點(diǎn) 上游2 8 到3 2 b p 處 k u t a c h a ke ta 1 2 0 0 0 2 上游啟動(dòng)子元件 它位于距離核心啟動(dòng)子上游1 k b p 的近端啟動(dòng)予區(qū) 這個(gè)區(qū)域的 元件對(duì)基因轉(zhuǎn)錄水平的調(diào)節(jié)發(fā)揮著很重要的作用 連接體掃描突變實(shí)驗(yàn)顯示 這個(gè)區(qū)域的 任何一個(gè)調(diào)節(jié)元件的任何一個(gè)位點(diǎn)的堿基發(fā)生突變 都會(huì)引起轉(zhuǎn)錄水平的顯著改變 c o o p e r sje ta 1 2 0 0 6 這個(gè)區(qū)域的元件可以分為兩類 一類是位于 3 5 0 劍 4 0 的元件 包括通常 7 0 b p 附近的c a a t 框和g c 框等 這些元件對(duì)啟動(dòng)子的活性有一個(gè)詎向調(diào)節(jié)作用 另一類是位 于 3 5 0 到 1 0 0 0 的元件 這類元件則對(duì)基岡的表達(dá)起到負(fù)凋節(jié)作用 a c a a t 框 也叫做c a t 框或c c a a tb o x 是另一個(gè)特征序列 一般位于在5 端轉(zhuǎn)錄 起始點(diǎn)上游約7 5 8 0 個(gè)核苷酸的地方 它的一致性序列為g g g t c a a t c t c a a t 框和g c 蘭州人學(xué)碩i 學(xué)位論義 框 用于和通用轉(zhuǎn)錄因子結(jié)合并控制著啟動(dòng)子轉(zhuǎn)錄的頻率 c a a t 框和g c 框一般位于t a t a 框1 0 0 1 5 0 個(gè)堿基處 b g c 框 常位于一些t a t a 框缺失的管家基因的啟動(dòng)子序列中 管家基因又叫做持家基 因 這些基因的產(chǎn)物是維持細(xì)胞的正常結(jié)構(gòu) 運(yùn)動(dòng) 以及參與新成代謝等生命活動(dòng)所必須 的 組蛋白基因 核糖體蛋白基因 線粒體蛋白基因 糖酵解酶基因等都是持家基因 它 的一致性序列為g g g c g g 是s p l 的結(jié)合位點(diǎn) s p l 結(jié)合在g c 框上 對(duì)轉(zhuǎn)錄的活化具有重要 作用 c c p g 島 上游啟動(dòng)子元件的另一個(gè)顯著特征是c p g 島的存在 c p g 島是一段長(zhǎng)度大于 2 0 0 b p 的富含g c 的未甲基化的d n a 序列 在這段序列中 堿基g 乖i c 的含量大于5 0 即 p g p c 0 5 并且c p g 島的頻率大于0 6 l i l j p c p g 0 6 x p g x p c c p g 島存在于4 0 哺乳動(dòng) 物啟動(dòng)子中 在人類啟動(dòng)子中的含量更是高達(dá)7 0 1 1 2 2 啟動(dòng)子的功能 雖然基因的表達(dá)調(diào)控有很多層面 例j z l i d n a 水平的調(diào)控 轉(zhuǎn)錄水平的凋控 轉(zhuǎn)錄后調(diào) 控 翻譯水平的調(diào)控 翻譯后水平的調(diào)控 但是轉(zhuǎn)錄調(diào)控被看做是最重要的層面 因?yàn)樵?任何連鎖反應(yīng)中 控制和凋節(jié)第一步往往是最有效果的 而啟動(dòng)子正好控制和調(diào)節(jié)著基因 表達(dá)調(diào)控的第一步 即調(diào)控轉(zhuǎn)錄的丌始時(shí)間和轉(zhuǎn)錄頻率 因此 啟動(dòng)子區(qū)和相關(guān)的調(diào)節(jié)元 件被看作是基因表達(dá)調(diào)控中最重要的一類元件 c o o p e rs je ta 1 2 0 0 6 啟動(dòng)子是最初結(jié)合 r n a 聚合酶的d n a 序列 在很多情況下與轉(zhuǎn)錄起始因子一起結(jié)合的 啟動(dòng)子與聚合酶的復(fù) 合體形成之后 結(jié)構(gòu)就發(fā)生改變 使起始過(guò)程繼續(xù)進(jìn)行 啟動(dòng)子對(duì)轉(zhuǎn)錄的調(diào)控可以分為兩 類 一類是非凋節(jié)性模式 負(fù)責(zé)持續(xù)表達(dá)基岡的轉(zhuǎn)錄調(diào)控 另一類是調(diào)節(jié)性模式 在這種 調(diào)控模式中啟動(dòng)子對(duì)轉(zhuǎn)錄的調(diào)控受胞內(nèi)和胞外的信號(hào)調(diào)節(jié) 通常r n a 聚合酶i i 不能單獨(dú)起 始轉(zhuǎn)錄而需要其它蛋白質(zhì)因子的協(xié)同參與 這能夠防止對(duì)細(xì)胞具有災(zāi)難性的無(wú)序轉(zhuǎn)錄的發(fā) 生 我們把這種調(diào)控基因轉(zhuǎn)錄的蛋白質(zhì)岡子稱為轉(zhuǎn)錄因子 1 1 2 2 1 轉(zhuǎn)錄因子的概念 通常在轉(zhuǎn)錄過(guò)程中 啟動(dòng)子需要其它輔助蛋白因子的協(xié)助才能與r n a 聚合酶結(jié)合 這 種蛋白輔助因子叫轉(zhuǎn)錄因子 轉(zhuǎn)錄因子是一類具有 f 調(diào)控作用的反式作用元件 它們能與 d n a 上特定的序列結(jié)合并構(gòu)成一種構(gòu)像 從而促進(jìn)基因的轉(zhuǎn)錄 根據(jù)結(jié)合部位的不同 轉(zhuǎn) 錄因子可以分為兩類 結(jié)合在t a t a 序列附近的蛋白質(zhì)因子稱為通用轉(zhuǎn)錄因子 以t f i i 表示 有t fi i a t fi i b t fi i d t fl i e t fi i f t fi i h t fi i i 等 結(jié)合在上游啟動(dòng)子元 6 蘭州人學(xué)碩i j 學(xué)化論文 件上的蛋白質(zhì)因子稱為轉(zhuǎn)錄調(diào)控因子 女i j s p i g a l 4 g c n 4 p h 0 4 等 另外還存在著誘 導(dǎo)型轉(zhuǎn)錄因子 i n d u c i b l ef a c t o r 它的作用與上游因子相同 但它們是受調(diào)控的 其在特定 時(shí)間 細(xì)胞發(fā)育階段 條件或特定的組織中合成或被活化 因而有調(diào)控基因在不同時(shí)間 條件或不同地點(diǎn)表達(dá)的作用 1 1 2 2 2 轉(zhuǎn)錄的定義 轉(zhuǎn)錄是基因進(jìn)行表達(dá)的第一步 也是最關(guān)鍵的一步 它是指d n a 遺傳信息傳遞到r n a 的過(guò)程 在這個(gè)過(guò)程中 各種r n a 如m r n a 及非編碼的t r n a r r n a 被合成 轉(zhuǎn)錄包括 起始 延長(zhǎng) 終止三個(gè)階段 在轉(zhuǎn)錄起始階段 r n a 聚合酶的o 因子識(shí)別d n a 啟動(dòng)子的 識(shí)別部位 r n a 聚合酶核心酶貝0 結(jié)合在啟動(dòng)子的結(jié)合部位 d n a 雙鏈打丌 形成一個(gè)大約 1 7 個(gè)堿基對(duì)長(zhǎng)度的轉(zhuǎn)錄泡 r n a 聚合酶隨后進(jìn)入轉(zhuǎn)入泡 在r n a 聚合酶的催化作用下 n t p 根據(jù)堿基互補(bǔ)原則依次結(jié)合在d n a 模板鏈上 在轉(zhuǎn)錄的延長(zhǎng)階段 核苷酸之間以3 5 一磷酸二酯鍵相連接沿5 一3 方向進(jìn)行r n a 的合成反應(yīng) 隨著反應(yīng)的進(jìn)行 由局部打丌 的d n a 雙鏈 r n a 聚合酶及新生成的r n a 局部形成的轉(zhuǎn)錄泡也隨之移動(dòng) 0 因子從模板 及r n a 聚合酶上脫落下來(lái) 于是r n a 聚合酶的核心酶沿著模板向下游移動(dòng) 脫落下的0 因子可以再次與核心酶結(jié)合而循環(huán)使用 在r n a 延長(zhǎng)進(jìn)程中 當(dāng)r n a 聚合酶行進(jìn)到d n a 模板的終止信號(hào)時(shí) r n a 聚合酶就不再繼續(xù)前進(jìn) 聚合作用也兇此停止 由于終止信號(hào)中 有由g c 富集區(qū)組成的反向重復(fù)序列 在轉(zhuǎn)錄生成的m r n a 中有相應(yīng)的發(fā)卡結(jié)構(gòu) 此發(fā)卡 結(jié)構(gòu)可阻礙r n a 聚合酶的行進(jìn) 由此而停止了r n a 聚合作用 1 1 2 3 啟動(dòng)子預(yù)測(cè)的現(xiàn)狀 1 1 2 3 1 啟動(dòng)子預(yù)測(cè)的方法 傳統(tǒng)的測(cè)定啟動(dòng)子的方法是通過(guò)生物學(xué)實(shí)驗(yàn) 如免疫沉淀 突變分析 印跡技術(shù)等來(lái) 進(jìn)行的 這些方法費(fèi)時(shí)費(fèi)力 隨著高通量實(shí)驗(yàn)的進(jìn)行 大量的數(shù)據(jù)涌現(xiàn) 傳統(tǒng)實(shí)驗(yàn)的方法 已經(jīng)遠(yuǎn)遠(yuǎn)不能滿足要求 近幾年出現(xiàn)的芯片技術(shù) 雖然能在一定程度上提高效率 但是也 存在著不少局限 例如受隨機(jī)因素影響大 可重復(fù)性差 費(fèi)用昂貴等 計(jì)算機(jī)技術(shù)的發(fā)展 使得對(duì)啟動(dòng)子的預(yù)測(cè)研究進(jìn)入了一個(gè)新的階段 利用計(jì)算機(jī)已成為目的啟動(dòng)子預(yù)測(cè)的主流 手段 a l f r e dqme ta 1 2 0 0 9 這種方法成本低 效率高 并且得到的結(jié)果也較為可靠 姚 鳳霞等2 0 0 5 各種各樣的啟動(dòng)子預(yù)測(cè)算法也相繼涌現(xiàn) 1 1 2 3 2 啟動(dòng)子預(yù)測(cè)的算法 蘭州人學(xué)碩i 學(xué)位論文 現(xiàn)行的啟動(dòng)子預(yù)測(cè)算法都是基于啟動(dòng)子區(qū)域的序列特征不同于別的功能區(qū)域的序列特 征這一基礎(chǔ)的 可分為三類 w ushe ta 1 2 0 0 7 基于信號(hào)的預(yù)測(cè)方法 基于 c p g 島 的預(yù)測(cè)方法以及基于內(nèi)容的預(yù)測(cè)方法 基于信號(hào)的預(yù)測(cè)方法 主要通過(guò)嘗試識(shí)別啟動(dòng)子的各類保守序列如原核啟動(dòng)子的 1 0 區(qū) 序列 3 5 區(qū)序列 真核啟動(dòng)子的t a t a b o x c a a t b o x 以及啟動(dòng)子序列中的轉(zhuǎn)錄因子結(jié)合 位點(diǎn)等一些啟動(dòng)子元件來(lái)區(qū)分啟動(dòng)子序列和非啟動(dòng)子序歹l j l iqz e ta 1 2 0 0 6 例如e p o n i n e d o w nt ae ta 1 2 0 0 2 d r a g o np r o m o t e rf i n d e r b a j i cv be ta 1 2 0 0 3 等都是基于信號(hào)的 預(yù)測(cè)軟件 但是由于目前對(duì)啟動(dòng)子的研究還不是很透徹 積累的數(shù)據(jù)還比較有限 導(dǎo)致很 多含有其他元件的啟動(dòng)子序列不能被很好的識(shí)別出來(lái) 另外 由于啟動(dòng)子保守模式的堿基 序列一般較短 很多保守模式在d n a 序列其他區(qū)域也大量存在 例如被普遍用于作為預(yù)測(cè) 特征元件t a t a b o x 將t a t a b o x 權(quán)矩陣應(yīng)用于哺乳動(dòng)物的非啟動(dòng)子序列結(jié)果顯示每1 2 0b p 就預(yù)測(cè)出一個(gè)t a t a b o x p r e s t r i d g edse ta 1 1 9 9 3 這些因素導(dǎo)致了單純使用轉(zhuǎn)錄因子結(jié) 合位點(diǎn)序列模式進(jìn)行啟動(dòng)子預(yù)測(cè)存在居高不下的假陽(yáng)性率 基于 c p g 島 的預(yù)測(cè)方法的依據(jù)是大部分的哺乳動(dòng)物基岡的啟動(dòng)子都和 c p g 島 有關(guān) 典型算法有f i r s t e f d a v u l u r irve ta 1 2 0 0 1 等 通過(guò) c p g 島 來(lái)尋找肩動(dòng)子 大約可以找到哺乳動(dòng)物一半的啟動(dòng)子 大約7 0 的人類基因啟動(dòng)子和 c p g 島 有關(guān) 如 果單純依靠 c p g 島 來(lái)進(jìn)行預(yù)測(cè)的話其正確率不會(huì)超過(guò)7 0 基于內(nèi)容的啟動(dòng)子預(yù)測(cè)方法是根據(jù)啟動(dòng)子序列相對(duì)于其它d n a 功能區(qū)域具有不同的堿 基選擇偏好柬區(qū)分啟動(dòng)子序列和非啟動(dòng)子序列的 w ushe ta 1 2 0 0 7 雖然d n a 序列都是 由a t g c 四種堿基構(gòu)成 但是四種堿基在各個(gè)功能區(qū)域中的分布并不均勻 即每種 功能區(qū)域存在著各自的內(nèi)部統(tǒng)計(jì)學(xué)規(guī)律 如單核苷酸或核苷酸聯(lián)體的統(tǒng)計(jì)分前i 規(guī)律 基于 內(nèi)容的方法運(yùn)用各種數(shù)據(jù)挖掘技術(shù) 挖掘出啟動(dòng)子序列內(nèi)部統(tǒng)計(jì)學(xué)規(guī)律作為判斷啟動(dòng)子的 依據(jù) 其準(zhǔn)確率關(guān)鍵在于數(shù)據(jù)挖掘 這種基于內(nèi)容的方法不需要了解轉(zhuǎn)錄的生物學(xué)意義 使得不具有生物學(xué)背景的研究者也可以進(jìn)行研究 降低了研究的準(zhǔn)入門(mén)檻 有助丁二啟動(dòng)子 預(yù)測(cè)的快速發(fā)展 這種方法還可以推廣到別的功能區(qū)域的預(yù)測(cè) 因而具有廣泛的應(yīng)用自訂途 本系統(tǒng)采用的h m m 的算法就是基于內(nèi)容的算法 蘭州人學(xué)顧l 學(xué)位論文 1 2 h m m 1 2 1 馬爾可夫模型介紹 1 8 7 0 年 俄國(guó)有機(jī)化學(xué)家v l a d i m i rvm a r k o v n i k o v 第一次提出馬爾可夫模型 馬爾可 夫模型是一個(gè)隨機(jī)的過(guò)程 它的根本特點(diǎn)就是馬爾可夫性也叫無(wú)后效性 即一個(gè)過(guò)程的 將 來(lái) 僅依賴 現(xiàn)在 而不依賴 過(guò)去 假設(shè)x 是一個(gè)馬爾可夫過(guò)程 x 在時(shí)刻t 的狀態(tài)是x t 則x 在時(shí)刻t l 的狀念x t 1 只與x 在時(shí)刻t 的狀態(tài)是x t 有關(guān) 可以表示成x t 1 f x t 馬爾可夫過(guò)程中的時(shí)間和狀念可以是連續(xù)的 也可以是離散的 我們把時(shí)間和狀態(tài)都離散 的馬爾可夫過(guò)程就叫做馬爾可夫鏈 馬爾可夫鏈的數(shù)學(xué)定義如下 隨機(jī)序列x 在任一時(shí)刻n 它可以處在狀態(tài)鼠 島 包 且它在m k 時(shí)刻所處的狀態(tài)為q 的概率只與它在f f l 時(shí)刻的狀態(tài)q 有關(guān) 而與m 時(shí) 刻以前它所處的狀態(tài)無(wú)關(guān) 1 2 2 h m m 介紹 1 2 2 1h m m 的定義 馬爾可夫鏈適用于狀態(tài)和事件一一對(duì)應(yīng)的情況 但是現(xiàn)實(shí)中的很多問(wèn)題往往比較復(fù)雜 有很多時(shí)候觀察到的事件并不是與狀念一一對(duì)應(yīng)的 而是通過(guò)一組概率分命對(duì)應(yīng) 這種情 況下 馬爾可夫模型就不適用了 h m m 就這樣應(yīng)運(yùn)而生 h m m 是馬爾可夫模型的一種擴(kuò) 充 最早在1 9 7 0 年左右被提出 b a u ml e1 9 7 2 b a u ml ee ta 1 1 9 6 7 b a u ml ee ta 1 1 9 6 6 b a u ml ee ta 1 1 9 7 0 隱馬爾可夫過(guò)程是一個(gè)雙重隨機(jī)過(guò)程 由兩個(gè)部分組成 馬爾可夫鏈 和一般隨機(jī)過(guò)程 其中馬爾可夫鏈用來(lái)描述狀念的轉(zhuǎn)移 用轉(zhuǎn)移概率描述 一般隨機(jī)過(guò)程 用來(lái)描述狀態(tài)與觀察序列問(wèn)的關(guān)系 用觀察值概率描述 觀察值序列和狀念序列并不是一 一對(duì)應(yīng)的關(guān)系 而是通過(guò)一組概率相聯(lián)系 h m m 的強(qiáng)大之處在于在觀察到的事件與內(nèi)在的 狀態(tài)間建立了一種概率模型 使用v e r t b i 算法 能夠根據(jù)一個(gè)給定的觀察序列和一個(gè)模型 在最佳的意義上確定內(nèi)部狀態(tài)序列 也就是說(shuō) 根據(jù)可觀察的事件序列 來(lái)推測(cè)不可觀察 的內(nèi)部狀態(tài)序列 一個(gè)h m m 可以表示為一個(gè)五元組 n m a b 也可以用簡(jiǎn)化了的三元組 b 衛(wèi) 來(lái)表示 其中 9 蘭州人學(xué)碩i 學(xué)位論文 n 表示h m m 的狀態(tài)數(shù)目 s s is 如 為狀態(tài)集合 模型在t 時(shí)刻的狀態(tài)記作q 模型 經(jīng)歷的狀態(tài)序列記為q 孫q 2 q m 表示每個(gè)狀態(tài)可能的觀察值數(shù)目 假設(shè)用v v i 屹 來(lái)表示觀察值集合 a 2 2p 吼 2 s jq 2 s 表示狀態(tài)轉(zhuǎn)移概率矩陣 表示從狀態(tài)s 轉(zhuǎn)移到狀態(tài)0 的 概率 且滿足 o 1 l b 釓 b k p q 咋iq s i 表示觀察值概率矩陣 表示在狀態(tài)s 下出現(xiàn)觀察值k 的 概率 萬(wàn) 萬(wàn)f 乃2p g l2 s 初始狀態(tài)分布概率且 7 i 1 m a r k o v 鏈 狀態(tài)序列 隨機(jī)過(guò)程 觀察值序列 尢 a q 1 q 2 o o o q t b 0 1 0 2 o t 圖1 2h m m 示意圖 1 2 2 2 h m m 的可解決的問(wèn)題及算法 1 2 2 2 1 h m m 主要用于解決三類問(wèn)題 1 評(píng)估問(wèn)題 給定觀察序列o q 0 2 0 以及模型入亍卅 b 吧 如何有效地計(jì)算出 觀察序列的概率 即求p o l 入 可以把它看作是評(píng)估一個(gè)模型和給定觀察輸出序列的匹配 程度 由此可以用來(lái)在一系列候選對(duì)象中選取最佳的匹配 2 解碼問(wèn)題 給定觀察序列o d i d 2 q 以及模型入亍 a b 吧 確定一個(gè)對(duì)應(yīng)的狀 態(tài)序列9 q lg g 使得q 能夠最為合理的解釋觀察序列o 3 學(xué)習(xí)問(wèn)題 在模型參數(shù)未知或不確定的情況下 如何根據(jù)觀察序列0 q 0 2 q 求 得模型參數(shù)或調(diào)整模型參數(shù) 使得p o i 入 最大 即試圖優(yōu)化模型的參數(shù)來(lái)最佳的描述一個(gè)給 定的觀察序列是如何得來(lái)的 1 2 2 2 2 h m m 的三個(gè)基本算法 針對(duì)h m m 的三個(gè)基本問(wèn)題 模型提供了三個(gè)算法 分別是前向后向算法 v i t e r b i 算法 和b a u m w e l c h 算法 三個(gè)算法的核心思想都是迭代思想 1 0 蘭州人學(xué)碩i 學(xué)位論文 1 前向后向算法 前向后向算法用于解決h m m 的評(píng)估問(wèn)題 給定觀察序列o a 0 2 0 7 和模型入 亍 a b 吧 計(jì)算由模型產(chǎn)生序列0 q d 2 q 的概率p oi 九 即給定模型和觀察序列 如何計(jì)算從模型生成觀察序列的概率 這種算法主要由如下兩部分組成 a h i j 向算法 定義前向變量 q f 2p d 1 d 2 0 t q 2 i 旯 2 f 丁 1 1 它的含義是給定模型入亍 a b 吧 在時(shí)刻t 狀態(tài)處于j 并且時(shí)刻1 2 t 的觀察序列為 o d l q q 的概率 前向算法的步驟為 1 初始化變量 口l f 2 乃6 d 1 l f n 1 2 2 遞歸過(guò)程 喇 陛o l t f 小 o t 1 l t t l 1 俐 l ij 1 3 3 終結(jié) p oi 五 l a d o q i 圖1 3 前向變量計(jì)算示意圖 b 后向算法 后向算法和前向算法類似 都是采用動(dòng)態(tài)規(guī)劃的思想 兩個(gè)算法的差別只是在于遞歸 的方向不一樣 日訂向算法是從后往前遞歸 而后向算法是從自訂往后遞歸 后向變量的含義 訇 意 示 是 屯 川 博 o o o 兒她 形馕 骺 圖 廠l墨 s o 塒鰳?biāo)?鋤 編識(shí) 咖 o o o 八 乳 眈 彤 跗 蘭州人學(xué)碩i 學(xué)位論文 是給定模型入 時(shí)刻t 處在狀態(tài)s 并且部分觀察序列為d 小d o r 的概率 其定義如 下 f l i p o f ld 2 0 rlq t a 后向算法的步驟為 1 初始化變量 歷 f 1 1 f n 2 遞歸過(guò)程 屈 f 口p b j o 1 屈 l r 丁一i t 一2 11 f n 1 3 終結(jié) p ol 兄 屈 f 1 5 1 6 1 7 1 8 前向算法和后向算法又統(tǒng)稱為前向后向算法 他們解決了h m m 的評(píng)估問(wèn)題 雖然用 傳統(tǒng)的定義法即排列組合的方法也可以解決h m m 的評(píng)估問(wèn)題 但是時(shí)間復(fù)雜度很高 而 前向算法和后向算法大大的降低了時(shí)間復(fù)雜度 2 v i t e r b i 算法 v i t e r b i 算法主要用于解決解碼問(wèn)題 它能夠根據(jù)一個(gè)給定的觀察序列o q 0 2 q 和一個(gè)模型旯 彳 b 萬(wàn) 在最佳的意義上確定一個(gè)內(nèi)部狀態(tài)序列q g q 2 q 定義4 f 為t 時(shí)刻沿著一條g f r 徑q q 2 q 且g s i 產(chǎn)生出序列0 q q9o o p 的最 大概率 該算法的計(jì)算步驟如下 1 初始化 西 f 7 0 島 d 1 l f n 1 9 識(shí) f o 1 f n 1 1 0 2 遞歸 諺 m a x 巧一l f 2 r 丁 1 1 l1 諺 a r g m a x 4 一l i a 2 t 1 j n 1 1 2 3 終結(jié) p m ax 4 1 13 1 2 蘭州人學(xué)碩i 學(xué)位論文 g a r g m a x 6 7 叫 1 1 4 4 求狀態(tài)序列 口j 諺 一 也 f 丁一1 t 一2 1 1 1 5 3 b a u m w e l c h 算法 模型訓(xùn)練算法 b a u m w e l c h 算法是目自仃使用較廣的一種用于h m m 參數(shù)選擇和優(yōu)化的算法 主要通過(guò) 迭代的思想進(jìn)行相關(guān)運(yùn)算 初始時(shí) 由用戶根據(jù)先驗(yàn)知諺 給出各個(gè)參數(shù)的估計(jì)值 通過(guò)不 斷迭代 使參數(shù)逐漸趨于更為合理的較優(yōu)值 這個(gè)算法主要解決給定一個(gè)觀察序列 o d l 0 2 0 7 和初始模型九 4 鼠 通過(guò)計(jì)算確定一個(gè)模型旯 彳 b 萬(wàn) 使得觀察序 列o q 0 2 q 產(chǎn)生的概率最大的 u j 題 首先定義所 f 為t 時(shí)刻處于 狀態(tài)的概率 缶 f 為給定模型入和觀察序列的條件下 從s 到s 的轉(zhuǎn)移概率 則缶 f 2p q f q r 2 l 0 旯 又根據(jù)前面前向變量q f 1 1 和后向變量屈 f 1 5 的定義 毒 f 可進(jìn)一步寫(xiě)成 毒c f 墨魚(yú) 三毫鏟 竺2 9 蘭三墨學(xué)2l 三 蘭 耄畿 1 初始化 乃 f 2 乃 2 迭代計(jì)算 根據(jù)形 f 和毒 f 的定義可以得出 形 瀘 毒 f j i 3 參數(shù)鶯估 1 1 7 1 18 7 i7 l 由于 形 f 表示整個(gè)過(guò)程中從狀態(tài)i 轉(zhuǎn)出次數(shù)的預(yù)期 專 f 表示整個(gè)過(guò)程中從狀態(tài)s 轉(zhuǎn) t lt l 移到狀態(tài)j 的次數(shù)的預(yù)期 所以根據(jù)狀態(tài)轉(zhuǎn)移概率的定義 乃 點(diǎn) i 1 19 蘭州人學(xué)碩 i 學(xué)位論文 r i 參 f 二1 7 一l 棚 i 7 門(mén) l 6 七 等l 以 l 1 2 0 1 2 1 4 結(jié)束 當(dāng)il o gp oa 一l o gp ol 九 i