genscan算法介紹-中國(guó)科學(xué)院計(jì)算技術(shù)研究所前瞻研究

1、Genscan 介紹,劉 瑋 2001.11.1,Genscan的用途,基因的識(shí)別外顯子內(nèi)含子基因間區(qū)域轉(zhuǎn)錄信號(hào)翻譯信號(hào)剪接信號(hào)等等……,基因結(jié)構(gòu),基因識(shí)別的方法,利用同源比對(duì).(blast)基于基因中編碼序列和非編碼序列區(qū)域堿基的統(tǒng)計(jì)差異性.根據(jù)真核基因的生物結(jié)構(gòu)，建立整體的基因預(yù)測(cè)模型.(Genscan),Genscan,Genscan程序是通過(guò)設(shè)計(jì)基因序列模型來(lái)得到

2、真核生物的基因.其編碼區(qū)使用五階的馬可夫模型,而不使用來(lái)自同源信息的模型,使得Genscan的結(jié)果不依靠于目前的蛋白庫(kù)中的相似基因,從而提供了于同源基因識(shí)別不一樣的方法.,基因序列結(jié)構(gòu)模型,該模型本質(zhì)是不完全的馬可夫模型(semi Markov),Genscan中使用state duration HMM 來(lái)說(shuō)明.模型可以看成序列φ:順序的狀態(tài)集 q＝{q1,q2,......,qn}狀態(tài)相對(duì)應(yīng)的長(zhǎng)度集(持續(xù)時(shí)間) d＝

3、{d1,d2,......,dn},對(duì)每一個(gè)狀態(tài), 使用分別概率模型P形成長(zhǎng)度為L(zhǎng)＝∑di (I=1...n)的DNA序列,模型通過(guò)以下步驟形成的長(zhǎng)度為L(zhǎng)的序列：1.由初始狀態(tài)集π得到初始狀態(tài)q12.狀態(tài)q1相對(duì)應(yīng)的長(zhǎng)度d1是由長(zhǎng)度分配集?Q給出3.在q1,d1的條件下,應(yīng)用同q1相對(duì)應(yīng)的概率模型,形成長(zhǎng)度為d1的序列片斷s14.后續(xù)狀態(tài)q2是根據(jù)q1由狀態(tài)轉(zhuǎn)換矩陣T(一階馬可夫)得到這個(gè)過(guò)程一直重復(fù)直到長(zhǎng)度達(dá)到或超過(guò)L。

4、序列就是片斷s的連接。,模型的四個(gè)主要元素：,初始概率向量π狀態(tài)轉(zhuǎn)移概率矩陣T長(zhǎng)度分配集?序列產(chǎn)生模型集P,模型的使用,由模型的四個(gè)參數(shù),可求出長(zhǎng)度為d,狀態(tài)是q的序列片斷為基因的概率(即是先得到一個(gè)基因的概率模型,之后給定一個(gè)序列,通過(guò)比較模型和序列的相似程度來(lái)預(yù)測(cè)基因.)使用到了向前算法和Viterbi算法.,模型參數(shù),初始概率和轉(zhuǎn)移概率根據(jù)CG含量的不同,將訓(xùn)練集分成四類(lèi)根據(jù)統(tǒng)計(jì)得到.模型的片斷的長(zhǎng)度有以下幾點(diǎn)內(nèi)含子和

5、基因間的長(zhǎng)度符合幾何分布,根據(jù)CG的不同分別的由參數(shù)q來(lái)決定5 UTR（從轉(zhuǎn)錄起始點(diǎn)到翻譯起始點(diǎn)）長(zhǎng)度為7693 UTR （終止密碼子到PloyA尾）長(zhǎng)度為457外顯子長(zhǎng)度l＝3c＋I(xiàn)（c為生成的完整密碼子個(gè)數(shù)，I為相對(duì)應(yīng)的內(nèi)含子狀態(tài)（0，1，2，））。,序列產(chǎn)生模型集P編碼區(qū)(外顯子)模型 外顯子使用3-periodic五階馬可夫模型.根據(jù)六聚體的結(jié)尾所處的密碼子的位置使用不同的轉(zhuǎn)移矩陣C1 C2 C3.非編碼區(qū)模

6、型(F,T,N,Ik) 使用五階的馬可夫模型,信號(hào)模型一些信號(hào)使用WMM(重量矩陣方法) 受體剪接位點(diǎn)中使用改進(jìn)的WAM(重量隊(duì)列模型)供體剪接位點(diǎn)中使用MDD(最大相關(guān)分解),轉(zhuǎn)錄和翻譯信號(hào)PolyA信號(hào)是6bp的WMM模型翻譯起始信號(hào)是12bp的WMM模型,其中開(kāi)始的6bp是起始密碼子.啟動(dòng)子由于30%的真核生物沒(méi)有TATA信號(hào),模型中以0.7的概率使用TATA-containing啟動(dòng)子,0.3的概率使用TATA