[医药卫生]基因识别.ppt

3.5 基因识别,生化教研室 邢军,3.5.7 基于剪切比对的基因识别方法 3.5.8 基于动态规划的基因结构预测方法 3.5.9 其他基因识别程序介绍,3.5.7 基于剪切比对的基因识别方法,基于剪切比对的基本思想 基于剪切比对的方法 PROCRUSTES程序特点,1. 基于剪切比对(spliced alignment)的基本思想,利用数据库中的同源信息进行基因识别，包括DNA、RNA和蛋白质数据库。,首先通过分析所有可能的剪切接受体位点和剪切给体位点，构建一组候选的外显子。 然后进一步分析候选外显子，探查所有可能的外显子组合，寻找一个与已知目标蛋白质或其他表达序列最匹配的组合。,2. 方法,alternative splicing,gene A,alternative splicing,预选 选择所有长度大于50bp并介于保守的剪切接受位点和给体位点之间的ORF，作为候选的外显子； 减小搜索范围 对于候选的外显子计算其6目编码度量值，并从大到小将它们排列起来； 搜索，筛选 对照蛋白质序列数据库进行搜索，寻找相似体。,3. 一种半自动的综合方法识别基因过程,PROCRUSTES程序 V4.01 (/software/procrustes/) 利用已知蛋白质和cDNA的相似信息识别基因或预测基因的结构。 首先生成一系列候选的外显子， PROCRUSTES考察所有候选外显子组合而成的可能的链（代表一种候选基因结构），并找出一个与目标蛋白质（对应的密码子序列）具有最大全局相似性的候选基因结构。,4. 特点,虽然可能的外显子组合很多，但剪切比对算法仍然很快，可以处理大量的包含多基因的基因组序列片段 仅当存在可以参考的功能序列时才有效 更适用于真核基因识别 不能用于识别新基因,3.5.8 基于动态规划的基因结构预测方法,动态规划 算法 介绍 多阶段决策过程的最优化 基于动态规划的基因结构预测,1. 动态规划算法 介绍,（1）定义： 动态规划（ dynamic programming ） 一种可以有效地探求一定复杂问题的各种可能的解决方案的程序； 将一个问题合理地分解成一些小的子问题，然后利用部分计算解得到最终答案。,（2）动态规划算法的基本思想： 将待求解的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的解,（3）动态规划的应用 是序列比对的基本工具 HMM 模型联合使用,20世纪50年代初 R.E.Bellman等人在研究多阶段决策过程( Multistep decision process )的优化问题时，提出了著名的最优化原理( Principle of optimality ) 把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法-动态规划。,2.多阶段决策过程的最优化,(1)多阶段决策问题 动态规划是把多阶段决策问题作为研究对象。 求解的全过程划分为若干个相互联系的阶段(即将问题划分为许多个相互联系的子问题)。 在它的每一阶段都需要作出决策，并且在一个阶段的决策确定以后再转移到下一个阶段。,多阶段决策过程 (Multi-Stage decision process) 前一个阶段的决策要影响到后一个阶段的决策，从而影响整个过程。 各个阶段所确定的决策就构成了一个决策序列，称为一个策略。,最优策略： 在所有可供选择的策略中，对应效果最好的策略称为最优策略。 把一个问题划分成若干个相互联系的阶段选取其最优策略，这类问题就是多阶段决策问题。,多阶段决策过程最优化的目标是要达到整个活动过程的总体效果最优。 决策者在每段决策时不应仅考虑本阶段最优，还应考虑对最终目标的影响，从而作出对全局来讲是最优的决策。 动态规划就是符合这种要求的一种决策方法。,(2)多阶段决策问题举例 例如： 1)工厂生产过程 2)设备更新问题 3)连续生产过程的控制问题 问题的发展过程都与时间因素有关,4）资源分配问题 5）运输网络问题,运输网络图示,3. 基于动态规划的基因结构预测 （1）基因识别最终任务是建立完整的基因结构模型 一个理想的基因识别程序应该能够发现完整的基因结构 （,e1, i1, , in-1, en , ）,（2）外显子组装方法 利用编码度量、剪切位点得分、起始密码、终止密码及非编码区特征信息等 （3）直接实现组合存在的问题 所有参数转化为一个有意义且唯一的指数和困难； 真实基因的外显子数量较多，计算上会产生数据组合爆炸；,（4）构建基因模型方法 剪切位点形成外显子和内含子的边界 搜集候选外显子 候选基因,DNA片段及候选位点,exon,受体位点 起始密码子,给体位点 终止密码子,exon,exon,给体位点,受体位点,intron,ag,ag,gt,gt,基因剪切位点 接受体（acceptor）位点- “ag” 剪切给体（donor）位点- “gt” 每一个位点可以被赋于一个加权值（表示成为功能位点的可能性），该加权值取决于对应位点附近的序列，可以利用前面介绍的编码区域识别方法，通过计算而得到。,DNA片段及候选剪切位点,基因的可变剪切,gene A,基因可变剪切示意,候选外显子列表,候选基因是一条非相交的外显子和内含子的链， 表示为 （i0, e1, i1, , ij,el ,en, in） 其中ij代表内含子（0jn） el代表外显子（1ln） i0和in并非真实的内含子，它们分别代表基因两侧的非编码序列,候选基因位于给定的DNA序列 满足下列一致性条件： 1）所有外显子加起来的长度是3的整数倍； 2）在各个外显子内部（除最后一个外显子的最后一个密码子），没有终止编码； 3）第一个内含子-外显子边界（i0, e1）是翻译起始编码，而最后一个外显子-内含子边界（en, in）是终止编码。,给定一个标明位点或一系列候选外显子和候选内含子的序列，我们可以构造一个无循环有向图G，使得该图中一条完整的路径代表一个完整的基因结构。 基因识别问题就转化为图G的路径分析问题，可以用动态规划来解决。 如何解决，还依赖于所用的特定的打分函数，依赖于选择外显子的过程。,位点图无循环有向图G 每个顶点代表候选的转录剪切位点、起始密码子或终止密码子。 图中的顶点分为两层，将外显子的左边界置于上层，而将外显子的右边界置于下层。 按照各位点在原序列中的位置，从左至右将两层中的顶点依次连接起来，形成有向边，或者称为弧。,位点图（分层标注剪切位点）,另设两个特殊的顶点，即起点（source）和终点（sink） 从起点到终点的任何一条路径代表一个可能的基因结构,该路径上从代表起始密码子的顶点开始，到代表终止密码子的顶点为止，其中的每一条自上而下的弧代表一个外显子，自下而上的弧代表一个内含子。 过滤不满足一致性条件（1）（3）的路径，使得仅仅保留没有框内终止编码的外显子及连接各顶点的具有一致性阅读框的内含子。这样，图中的每一条路径对应于一个经过处理的候选基因。,过滤不满足一致性条件的路径,一个候选基因结构在位点图上对应的路径,候选基因所对应的道路图中的路径,利用动态规划算法寻找最优的路径，从而构造代价最小（或得分最高）的基因。这种方式在GeneParser和 GRAIL中得到应用。,动态规划法求最优路径 每一条弧附加一个权值 外显子、内含子度量 每个节点附加权值 剪切位点度量,综合评价一个基因结构的得分可按下式计算,A 剪切受体位点得分 D 剪切给体位点得分 C 编码得分 L 外显子长度 N 相继外显子个数 与是对于参数在学习样本上的均值和标准方差,真正的外显子在许多高得分的结构中出现 对打分以后的基因按递减顺序进行排队 最后仅考虑排在前面的一部分候选基因 筛选掉排在后面的基因。,应用程序,GRAILEXP (/grailexp/),GeneParser (/eesnyder/geneparser.htm),GRAIL,GRAIL query,GRAIL results,3.5.9 其他基因识别程序介绍,基于规则的识别方法(GeneID) 语义学的方法(GenLang) 决策树方法 (MORGAN) Z curve,1. GeneID 是一个基于规则的基因识别系统, 识别的依据是编码度量和信号强度。 识别转录剪切位点、起始密码子和终止密码子，并对识别结果打分。 根据所识别的功能位点构造外显子，以相应的功能位点得分加上编码DNA序列马尔柯夫模型的对数似然比值作为外显子的得分。 利用启发式的规则将这些外显子组装成基因模型。,2. 语义学方法 用形式语法描述基因结构和生物分子序列的许多其它特征，通过句法模式识别技术检测这些特征。 GenLang使用的就是这类方法，用于识别真核编码基因。在语义学上下文环境中，将编码度量和信号强度解释为各个规则的代价。 GenLang通过训练优化得到一个形式语法，并用它来产生最小代价的基因模型。,3. MORGAN (multiframe optimal rule-base gene analyzer) 是一个寻找基因的集成系统，该系统使用多种技术，该系统使用了决策树(decision tree)分类器。 将决策树与其它识别起始密码子、剪切位点的新方法结合在一起，发现DNA序列中的外显子和内含子结构。,4. Z curve(天津大学生物信息中心) Z 曲线是表示DNA 序列的一个等价的三维空间曲线。通过对Z 曲线的研究来对基因组序列进行研究是一种几何学的途径。 几何学名词与概念，如座标系、空间、投影、曲线、曲率等构成了分析基因组序列的工具。 例： 酿酒酵母基因组基因识别软件ZCURVE_Y 冠状病毒基因组基因识别软件ZCURVE_CoV,天津大学生物信息中心网站服务项目信息 TUBIC - 天津大学生物信息中心网站 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 余种生物基因组的Z 曲线数据库 DEG 1.1 细菌和古细菌必需基因数据库,基因识别程序及访问地址 （HP主页；ESE-mail服务器；WSweb服务器；CL客户/服务器协议； EX有可执行代码；SC有源代码）,各程序的性能比较（敏感性(1)被预测出的真实编码核酸的%； 敏感性(2)被正确识别出的编码外显子的%； 特异性(1)预测出的编码核酸为真实编码核酸的%； 特异性(2)预测出外显子为真实外显子的%）,基因组识别方法小结,最长ORF法 密码子频率 剪切比对 动态规划 神经网络 隐马尔可夫模型 其他,Prediction of gene structure (exons, splicing sites, promotors) AAT (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 prediction) 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 (Recognition 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),基因识别方法存在