1、3.5 基因識別 生化教研室 邢軍3.5.7 基于剪切比對的基因識別方法3.5.8 基于動態規劃的基因結構預測方法3.5.9 其他基因識別程序介紹3.5.7 基于剪切比對的基因識別方法基于剪切比對的基本思想基于剪切比對的方法PROCRUSTES程序特點1. 基于剪切比對(spliced alignment)的基本思想 利用數據庫中的同源信息進行基因識別，包括DNA、RNA和蛋白質數據庫。首先通過分析所有可能的剪切接受體位點和剪切給體位點，構建一組候選的外顯子。然后進一步分析候選外顯子，探查所有可能的外顯子組合，尋找一個與已知目標蛋白質或其他表達序列最匹配的組合。2. 方法alternative

2、 splicing gene Aalternative splicing 預選 選擇所有長度大于50bp并介于保守的剪切接受位點和給體位點之間的ORF，作為候選的外顯子；減小搜索范圍 對于候選的外顯子計算其6目編碼度量值，并從大到小將它們排列起來；搜索，篩選 對照蛋白質序列數據庫進行搜索，尋找相似體。3. 一種半自動的綜合方法識別基因過程PROCRUSTES程序 V4.01 (http:/www-/software/procrustes/) 利用已知蛋白質和cDNA的相似信息識別基因或預測基因的結構。 首先生成一系列候選的外顯子， PROCRUSTES考察所有候選外顯子組合而成的可能的鏈（代表

3、一種候選基因結構），并找出一個與目標蛋白質（對應的密碼子序列）具有最大全局相似性的候選基因結構。 4. 特點雖然可能的外顯子組合很多，但剪切比對算法仍然很快，可以處理大量的包含多基因的基因組序列片段 僅當存在可以參考的功能序列時才有效更適用于真核基因識別不能用于識別新基因3.5.8 基于動態規劃的基因結構預測方法動態規劃 算法 介紹多階段決策過程的最優化基于動態規劃的基因結構預測1. 動態規劃算法 介紹（1）定義： 動態規劃（ dynamic programming ） 一種可以有效地探求一定復雜問題的各種可能的解決方案的程序； 將一個問題合理地分解成一些小的子問題，然后利用部分計算解得到最終

4、答案。（2）動態規劃算法的基本思想： 將待求解的問題分解成若干個相互聯系的子問題，先求解子問題，然后從這些子問題的解得到原問題的解（3）動態規劃的應用 是序列比對的基本工具 HMM 模型聯合使用20世紀50年代初 R.E.Bellman等人在研究多階段決策過程( Multistep decision process )的優化問題時，提出了著名的最優化原理( Principle of optimality ) 把多階段過程轉化為一系列單階段問題，逐個求解，創立了解決這類過程優化問題的新方法-動態規劃。2.多階段決策過程的最優化 (1)多階段決策問題 動態規劃是把多階段決策問題作為研究對象。 求解

5、的全過程劃分為若干個相互聯系的階段(即將問題劃分為許多個相互聯系的子問題)。 在它的每一階段都需要作出決策，并且在一個階段的決策確定以后再轉移到下一個階段。多階段決策過程 (Multi-Stage decision process) 前一個階段的決策要影響到后一個階段的決策，從而影響整個過程。 各個階段所確定的決策就構成了一個決策序列，稱為一個策略。最優策略：在所有可供選擇的策略中，對應效果最好的策略稱為最優策略。 把一個問題劃分成若干個相互聯系的階段選取其最優策略，這類問題就是多階段決策問題。 多階段決策過程最優化的目標是要達到整個活動過程的總體效果最優。 決策者在每段決策時不應僅考慮本階段

6、最優，還應考慮對最終目標的影響，從而作出對全局來講是最優的決策。動態規劃就是符合這種要求的一種決策方法。(2)多階段決策問題舉例例如： 1)工廠生產過程 2)設備更新問題 3)連續生產過程的控制問題 問題的發展過程都與時間因素有關 4）資源分配問題 5）運輸網絡問題 運輸網絡圖示3. 基于動態規劃的基因結構預測（1）基因識別最終任務是建立完整的基因結構模型 一個理想的基因識別程序應該能夠發現完整的基因結構 （,e1, i1, , in-1, en , ） ATG-外顯子1內含子外顯子外顯子n-UAG（2）外顯子組裝方法 利用編碼度量、剪切位點得分、起始密碼、終止密碼及非編碼區特征信息等（3）直

7、接實現組合存在的問題 所有參數轉化為一個有意義且唯一的指數和困難； 真實基因的外顯子數量較多，計算上會產生數據組合爆炸；（4）構建基因模型方法 剪切位點形成外顯子和內含子的邊界 搜集候選外顯子 候選基因DNA片段及候選位點exon受體位點起始密碼子給體位點終止密碼子exonexon給體位點受體位點intronagaggtgt基因剪切位點 接受體（acceptor）位點- “ag” 剪切給體（donor）位點- “gt”每一個位點可以被賦于一個加權值（表示成為功能位點的可能性），該加權值取決于對應位點附近的序列，可以利用前面介紹的編碼區域識別方法，通過計算而得到。 DNA片段及候選剪切位點基因的

8、可變剪切gene A基因可變剪切示意候選外顯子列表候選基因是一條非相交的外顯子和內含子的鏈，表示為 （i0, e1, i1, , ij,el ,en, in） 其中ij代表內含子（0jn） el代表外顯子（1ln） i0和in并非真實的內含子，它們分別代表基因兩側的非編碼序列候選基因位于給定的DNA序列滿足下列一致性條件： 1）所有外顯子加起來的長度是3的整數倍； 2）在各個外顯子內部（除最后一個外顯子的最后一個密碼子），沒有終止編碼； 3）第一個內含子-外顯子邊界（i0, e1）是翻譯起始編碼，而最后一個外顯子-內含子邊界（en, in）是終止編碼。給定一個標明位點或一系列候選外顯子和候選內

9、含子的序列，我們可以構造一個無循環有向圖G，使得該圖中一條完整的路徑代表一個完整的基因結構。基因識別問題就轉化為圖G的路徑分析問題，可以用動態規劃來解決。如何解決，還依賴于所用的特定的打分函數，依賴于選擇外顯子的過程。位點圖無循環有向圖G 每個頂點代表候選的轉錄剪切位點、起始密碼子或終止密碼子。 圖中的頂點分為兩層，將外顯子的左邊界置于上層，而將外顯子的右邊界置于下層。 按照各位點在原序列中的位置，從左至右將兩層中的頂點依次連接起來，形成有向邊，或者稱為弧。位點圖（分層標注剪切位點）另設兩個特殊的頂點，即起點（source）和終點（sink）從起點到終點的任何一條路徑代表一個可能的基因結構該路

10、徑上從代表起始密碼子的頂點開始，到代表終止密碼子的頂點為止，其中的每一條自上而下的弧代表一個外顯子，自下而上的弧代表一個內含子。過濾不滿足一致性條件（1）（3）的路徑，使得僅僅保留沒有框內終止編碼的外顯子及連接各頂點的具有一致性閱讀框的內含子。這樣，圖中的每一條路徑對應于一個經過處理的候選基因。 過濾不滿足一致性條件的路徑一個候選基因結構在位點圖上對應的路徑候選基因所對應的道路圖中的路徑 利用動態規劃算法尋找最優的路徑，從而構造代價最小（或得分最高）的基因。這種方式在GeneParser和 GRAIL中得到應用。動態規劃法求最優路徑 每一條弧附加一個權值外顯子、內含子度量每個節點附加權值剪切位

11、點度量 綜合評價一個基因結構的得分可按下式計算 R=A-NANA+D-N DNDC-L CLCA 剪切受體位點得分D 剪切給體位點得分C 編碼得分L 外顯子長度N 相繼外顯子個數與是對于參數在學習樣本上的均值和標準方差 真正的外顯子在許多高得分的結構中出現對打分以后的基因按遞減順序進行排隊最后僅考慮排在前面的一部分候選基因篩選掉排在后面的基因。 應用程序GRAILEXP (http:/grailexp/)GeneParser (http:/eesnyder/geneparser.htm)GRAILGRAIL queryGRAIL results3.5.9 其他基因識別程序介紹基于規則的識別方法

12、(GeneID)語義學的方法(GenLang)決策樹方法 (MORGAN)Z curve1. GeneID 是一個基于規則的基因識別系統, 識別的依據是編碼度量和信號強度。識別轉錄剪切位點、起始密碼子和終止密碼子，并對識別結果打分。根據所識別的功能位點構造外顯子，以相應的功能位點得分加上編碼DNA序列馬爾柯夫模型的對數似然比值作為外顯子的得分。利用啟發式的規則將這些外顯子組裝成基因模型。 2. 語義學方法 用形式語法描述基因結構和生物分子序列的許多其它特征，通過句法模式識別技術檢測這些特征。 GenLang使用的就是這類方法，用于識別真核編碼基因。在語義學上下文環境中，將編碼度量和信號強度解釋

13、為各個規則的代價。 GenLang通過訓練優化得到一個形式語法，并用它來產生最小代價的基因模型。3. MORGAN (multiframe optimal rule-base gene analyzer) 是一個尋找基因的集成系統，該系統使用多種技術，該系統使用了決策樹(decision tree)分類器。 將決策樹與其它識別起始密碼子、剪切位點的新方法結合在一起，發現DNA序列中的外顯子和內含子結構。 4. Z curve(天津大學生物信息中心) Z 曲線是表示DNA 序列的一個等價的三維空間曲線。通過對Z 曲線的研究來對基因組序列進行研究是一種幾何學的途徑。 幾何學名詞與概念，如座標系、空

14、間、投影、曲線、曲率等構成了分析基因組序列的工具。 例： 釀酒酵母基因組基因識別軟件ZCURVE_Y 冠狀病毒基因組基因識別軟件ZCURVE_CoV 天津大學生物信息中心網站服務項目信息TUBIC - http:/ 天津大學生物信息中心網站ZCURVE 1.02 細菌和古細菌全基因組ab initio 基因識別Zcurve_C 1.0 細菌和古細菌基因組中單個基因識別Zcurve_Y 1.0 釀酒酵母基因組基因識別Zcurve_CoV 2.0 冠狀病毒（含SARS-CoV）基因組基因識別GS-Finder 1.0 細菌和古細菌基因起始密碼子位點識別Zcurve_DB 1.0 1000 余種生物

15、基因組的Z 曲線數據庫DEG 1.1 細菌和古細菌必需基因數據庫 基因識別程序及訪問地址（HP主頁；ESE-mail服務器；WSweb服務器；CL客戶/服務器協議；EX有可執行代碼；SC有源代碼）各程序的性能比較（敏感性(1)被預測出的真實編碼核酸的%；敏感性(2)被正確識別出的編碼外顯子的%；特異性(1)預測出的編碼核酸為真實編碼核酸的%；特異性(2)預測出外顯子為真實外顯子的%）基因組識別方法小結最長ORF法密碼子頻率剪切比對動態規劃神經網絡隱馬爾可夫模型其他Prediction of gene structure (exons, splicing sites, promotors) AA

16、T (Analysis and Annotation Tool for Finding Genes in Genomic Sequences) Michigan (USA) AGenDA (gene-prediction tool that is based on cross-species sequence comparison) Bielefeld (Germany) ATGpr (identifies the initiation codons in cDNA sequences) HRI (Japan) AUG_EVALUATOR (for start codons predictio

17、n) ITBA (Italy) Bacterial Promoter, Operon and Gene Finding SoftBerry BioProspector (Discovering Conserved DNA Motifs in Upstream Regulatory Regions of Co-Expressed Genes) Stanford (USA) BCM Gene Finder (exons, splicing sites, promoter, coding region) BCM, see also Gene Feature Searches Cassandra (R

18、ecognition of protein-coding segments in eukaryotic DNA) USC (USA) CDS (Search Coding Regions) Pasteur, see also advanced form (French) CHECKTRANS (ORF property statistics) Pasteur (French) Cister (Cis-element Cluster Finder) Boston (USA) Cister (Cis-element Cluster Finder) Boston (USA) ConPro (consensus promoter predictor) Michigan (USA) Core-Promoter Finder CSHL (USA) 基因識別方法存在的問