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

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

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

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

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

5、基因間的長度符合幾何分布,根據(jù)CG的不同分別的由參數(shù)q來決定5 UTR（從轉(zhuǎn)錄起始點到翻譯起始點）長度為7693 UTR （終止密碼子到PloyA尾）長度為457外顯子長度l＝3c＋I（c為生成的完整密碼子個數(shù)，I為相對應(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) 使用五階的馬可夫模型,信號模型一些信號使用WMM(重量矩陣方法) 受體剪接位點中使用改進的WAM(重量隊列模型)供體剪接位點中使用MDD(最大相關(guān)分解),轉(zhuǎn)錄和翻譯信號PolyA信號是6bp的WMM模型翻譯起始信號是12bp的WMM模型,其中開始的6bp是起始密碼子.啟動子由于30%的真核生物沒有TATA信號,模型中以0.7的概率使用TATA-containing啟動子,0.3的概率使用TATA