《医药卫生基因识别》由会员分享，可在线阅读，更多相关《医药卫生基因识别（61页珍藏版）》请在金锄头文库上搜索。
1、3.5 基因识别基因识别 生化教研室生化教研室 邢军邢军3.5.7 基于剪切比对的基因识别方法基于剪切比对的基因识别方法3.5.8 基于动态规划的基因结构预测方法基于动态规划的基因结构预测方法3.5.9 其他基因识别程序介绍其他基因识别程序介绍3.5.7 基于剪切比对的基因识别方法基于剪切比对的基因识别方法l基于剪切比对的根本思想基于剪切比对的根本思想l基于剪切比对的方法基于剪切比对的方法lPROCRUSTES程序特点程序特点1. 基于剪切比对基于剪切比对(spliced alignment)的根本思想的根本思想 利用数据库中的利用数据库中的同源信息同源信息进行基因识别，进行基因识别，包括包括
2、DNA、RNA和蛋白质数据库。和蛋白质数据库。l首先通过分析所有可能的剪切接受体位点和剪首先通过分析所有可能的剪切接受体位点和剪切给体位点，构建一组候选的外显子。切给体位点，构建一组候选的外显子。l然后进一步分析候选外显子，探查所有可能的然后进一步分析候选外显子，探查所有可能的外显子组合，寻找一个与目标蛋白质或其他表外显子组合，寻找一个与目标蛋白质或其他表达序列最匹配的组合。达序列最匹配的组合。2. 方法方法alternative splicing gene Aalternative splicing l预选预选 选择所有长度大于选择所有长度大于50bp并介于并介于保守的剪切接受位点和给体位点
3、之间的保守的剪切接受位点和给体位点之间的ORF，作为候选的外显子；，作为候选的外显子；l减小搜索范围减小搜索范围 对于候选的外显子计对于候选的外显子计算其算其6目编码度量值，并从大到小将它们目编码度量值，并从大到小将它们排列起来；排列起来；l搜索，筛选搜索，筛选 对照蛋白质序列数据库对照蛋白质序列数据库进行搜索，寻找相似体。进行搜索，寻找相似体。3. 一种半自动的综合方法识别基因过程一种半自动的综合方法识别基因过程PROCRUSTES程序程序 V4.01 ( :/www-/) 利用蛋白质和利用蛋白质和cDNA的相似信息识别基因或预测基因的的相似信息识别基因或预测基因的结构。结构。 首先生成一系
4、列候选的外显子，首先生成一系列候选的外显子， PROCRUSTES考察所有候选外显子组合而成的可能的链考察所有候选外显子组合而成的可能的链代表一种候选基因结构，并找出一个与目标蛋白质对代表一种候选基因结构，并找出一个与目标蛋白质对应的密码子序列具有最大全局相似性的候选基因结构。应的密码子序列具有最大全局相似性的候选基因结构。 4. 特点特点l虽然可能的外显子组合很多，但剪切比对算法仍虽然可能的外显子组合很多，但剪切比对算法仍然很快，可以处理大量的包含多基因的基因组序然很快，可以处理大量的包含多基因的基因组序列片段列片段 l仅当存在可以参考的功能序列时才有效仅当存在可以参考的功能序列时才有效l更
5、适用于真核基因识别更适用于真核基因识别l不能用于识别新基因不能用于识别新基因3.5.8 基于动态规划的基因结构预测方法基于动态规划的基因结构预测方法l动态规划动态规划 算法算法 介绍介绍l多阶段决策过程的最优化多阶段决策过程的最优化l基于动态规划的基因结构预测基于动态规划的基因结构预测1. 1. 动态规划算法动态规划算法 介绍介绍1定义：定义： 动态规划动态规划 dynamic programming 一种可以有效地探求一定复杂问题的各种一种可以有效地探求一定复杂问题的各种可能的解决方案的程序；可能的解决方案的程序； 将一个问题合理地分解成一些小的子问将一个问题合理地分解成一些小的子问题，然后
6、利用局部计算解得到最终答案。题，然后利用局部计算解得到最终答案。2 2动态规划算法的根本思想：动态规划算法的根本思想： 将待求解的问题分解成假设干个相互将待求解的问题分解成假设干个相互联系的子问题，先求解子问题，然后从这联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的解些子问题的解得到原问题的解3 3动态规划的应用动态规划的应用 是序列比对的根本工具是序列比对的根本工具 HMM HMM 模型联合使用模型联合使用20世纪世纪50年代初年代初 等人在研究等人在研究多阶段决策过程多阶段决策过程( Multistep decision process )的优化问题时，提出了著名的优化问题时
7、，提出了著名的的最优化原理最优化原理( Principle of optimality ) 把多阶段过程转化为一系列单阶段问题，把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方逐个求解，创立了解决这类过程优化问题的新方法法-动态规划动态规划。2.2.多阶段决策过程的最优化多阶段决策过程的最优化 (1) (1)多阶段决策问题多阶段决策问题 动态规划是把多阶段决策问题作为研究对象。动态规划是把多阶段决策问题作为研究对象。 求求解解的的全全过过程程划划分分为为假假设设干干个个相相互互联联系系的的阶阶段段( (即将问题划分为许多个相互联系的子问题即将问题划分为许多个相互联
8、系的子问题) )。 在在它它的的每每一一阶阶段段都都需需要要作作出出决决策策，并并且且在在一一个个阶段的决策确定以后再转移到下一个阶段。阶段的决策确定以后再转移到下一个阶段。多阶段决策过程多阶段决策过程 (Multi-Stage decision process) (Multi-Stage decision process) 前一个阶段的决策要影响到后一个阶段的决策，前一个阶段的决策要影响到后一个阶段的决策，从而影响整个过程。从而影响整个过程。 各个阶段所确定的决策就构成了一个各个阶段所确定的决策就构成了一个决策序列决策序列，称为一个称为一个策略策略。最优策略：最优策略：在所有可供选择的策略中
9、，对应效果最好的在所有可供选择的策略中，对应效果最好的策略称为最优策略。策略称为最优策略。 把一个问题划分成假设干个相互联系的阶段把一个问题划分成假设干个相互联系的阶段选取其最优策略，这类问题就是多阶段决策问题。选取其最优策略，这类问题就是多阶段决策问题。 多阶段决策过程最优化的目标是要到达整个活多阶段决策过程最优化的目标是要到达整个活动过程的总体效果最优。动过程的总体效果最优。 决策者在每段决策时不应仅考虑本阶段最优，决策者在每段决策时不应仅考虑本阶段最优，还应考虑对最终目标的影响，从而作出对全局来讲还应考虑对最终目标的影响，从而作出对全局来讲是最优的决策。是最优的决策。动态规划就是符合这种
10、要求的一种决策方法。动态规划就是符合这种要求的一种决策方法。(2)(2)多阶段决策问题举例多阶段决策问题举例例如：例如： 1) 1)工厂生产过程工厂生产过程 2) 2)设备更新问题设备更新问题 3) 3)连续生产过程的控制问题连续生产过程的控制问题 问题的开展过程都与时间因素有关问题的开展过程都与时间因素有关l 4资源分配问题资源分配问题l 5运输网络问题运输网络问题 运输网络图示运输网络图示3. 3. 基于动态规划的基因结构预测基于动态规划的基因结构预测1 1基因识别最终任务是建立完整的基因基因识别最终任务是建立完整的基因结构模型结构模型 一个理想的基因识别程序应该能够发现一个理想的基因识别
11、程序应该能够发现完整的基因结构完整的基因结构 ,e1, i1, , in-1, en , ,e1, i1, , in-1, en , ATG-外显子1内含子外显子外显子n-UAG2外显子组装方法外显子组装方法 利用编码度量、剪切位点得分、起始密码、利用编码度量、剪切位点得分、起始密码、终止密码及非编码区特征信息等终止密码及非编码区特征信息等3直接实现组合存在的问题直接实现组合存在的问题 所有参数转化为一个有意义且唯一的指数所有参数转化为一个有意义且唯一的指数和困难；和困难； 真实基因的外显子数量较多，计算上会产真实基因的外显子数量较多，计算上会产生数据组合爆炸；生数据组合爆炸；4构建基因模型方
12、法构建基因模型方法 剪切位点形成外显子和内含子的边界剪切位点形成外显子和内含子的边界 搜集候选外显子搜集候选外显子 候选基因候选基因DNA片段及候选位点片段及候选位点exon受体位点受体位点起始密码子起始密码子给体位点给体位点终止密码子终止密码子exonexon给体位点给体位点受体位点受体位点intronagaggtgt基因剪切位点基因剪切位点 接受体接受体acceptor位点位点- “ag 剪切给体剪切给体donor位点位点- “gt每一个位点可以被赋于一个加权值表示成为功能位点每一个位点可以被赋于一个加权值表示成为功能位点的可能性，该加权值取决于对应位点附近的序列，可以利的可能性，该加权值
13、取决于对应位点附近的序列，可以利用前面介绍的编码区域识别方法，通过计算而得到。用前面介绍的编码区域识别方法，通过计算而得到。 DNA片段及候选剪切位点片段及候选剪切位点基因的可变剪切基因的可变剪切gene A基因可变剪切示意基因可变剪切示意候选外显子列表候选外显子列表候选基因是一条非相交的外显子和内含子的链，候选基因是一条非相交的外显子和内含子的链，表示为表示为 i0, e1, i1, , ij,el ,en, in 其中其中ij代表内含子代表内含子0jn el代表外显子代表外显子1ln i0和和in并非真实的内含子，它们分别代表基因两并非真实的内含子，它们分别代表基因两侧的非编码序列侧的非编
14、码序列候选基因位于给定的候选基因位于给定的DNA序列序列满足以下一致性条件：满足以下一致性条件： 1所有外显子加起来的长度是所有外显子加起来的长度是3的整数倍；的整数倍； 2在各个外显子内部除最后一个外显子的最后在各个外显子内部除最后一个外显子的最后一个密码子，没有终止编码；一个密码子，没有终止编码； 3第一个内含子第一个内含子-外显子边界外显子边界i0, e1是翻译起是翻译起始编码，而最后一个外显子始编码，而最后一个外显子-内含子边界内含子边界en, in是终止编码。是终止编码。给定一个标明位点或一系列候选外显子和候选内给定一个标明位点或一系列候选外显子和候选内含子的序列，我们可以构造一个含
15、子的序列，我们可以构造一个无循环有向图无循环有向图G，使得使得该图中一条完整的路径代表一个完整的基因结构。该图中一条完整的路径代表一个完整的基因结构。基因识别问题就转化为图基因识别问题就转化为图G的路径分析问题，可的路径分析问题，可以用以用动态规划动态规划来解决。来解决。如何解决，还依赖于所用的特定的打分函数，依如何解决，还依赖于所用的特定的打分函数，依赖于选择外显子的过程。赖于选择外显子的过程。位点图位点图无循环有向图无循环有向图G G 每个顶点代表候选的转录剪切位点、起始密每个顶点代表候选的转录剪切位点、起始密码子或终止密码子。码子或终止密码子。 图中的顶点分为两层，将外显子的图中的顶点分
16、为两层，将外显子的左边界左边界置置于于上层上层，而将外显子的，而将外显子的右边界右边界置于置于下层下层。 按照各位点在原序列中的位置，从左至右将按照各位点在原序列中的位置，从左至右将两层中的顶点依次连接起来，形成两层中的顶点依次连接起来，形成有向边有向边，或，或者称为者称为弧弧。位点图分层标注剪切位点位点图分层标注剪切位点另设两个特殊的顶点，即起点另设两个特殊的顶点，即起点source和终点和终点sink从起点到终点的任何一条路径代表一个可能的基因结构从起点到终点的任何一条路径代表一个可能的基因结构该路径上从代表起始密码子的顶点开始，到代表该路径上从代表起始密码子的顶点开始，到代表终止密码子的
17、顶点为止，其中的每一条自上而下的弧代终止密码子的顶点为止，其中的每一条自上而下的弧代表一个外显子，自下而上的弧代表一个内含子。表一个外显子，自下而上的弧代表一个内含子。过滤不满足一致性条件过滤不满足一致性条件1 3的路径，使的路径，使得仅仅保存没有框内终止编码的外显子及连接各顶点的得仅仅保存没有框内终止编码的外显子及连接各顶点的具有一致性阅读框的内含子。这样，图中的每一条路径具有一致性阅读框的内含子。这样，图中的每一条路径对应于一个经过处理的候选基因。对应于一个经过处理的候选基因。 过滤不满足一致性条件的路径过滤不满足一致性条件的路径一个候选基因结构在位点图上对应的路径一个候选基因结构在位点图
18、上对应的路径候选基因所对应的道路图中的路径候选基因所对应的道路图中的路径 利用动态规划算法寻找最优的路径，从而利用动态规划算法寻找最优的路径，从而构造代价最小或得分最高的基因。这种方构造代价最小或得分最高的基因。这种方式在式在GeneParser和和 GRAIL中得到应用。中得到应用。动态规划法求动态规划法求最优路径最优路径 每一条弧附加一个权值每一条弧附加一个权值外显子、内含子度量外显子、内含子度量每个节点附加权值每个节点附加权值剪切位点度量剪切位点度量 综合评价综合评价一个基因结构的得分可按下式计算一个基因结构的得分可按下式计算 R=A-NANA+D-N DNDC-L CLCA 剪切受体位
19、点得分剪切受体位点得分D 剪切给体位点得分剪切给体位点得分C 编码得分编码得分L 外显子长度外显子长度N 相继外显子个数相继外显子个数 与与 是对于参数是对于参数 在学习样本上的均值和标准方差在学习样本上的均值和标准方差 l真正的外显子在许多高得分的结构中出现真正的外显子在许多高得分的结构中出现l对打分以后的基因按递减顺序进行排队对打分以后的基因按递减顺序进行排队l最后仅考虑排在前面的一局部候选基因最后仅考虑排在前面的一局部候选基因l筛选掉排在后面的基因。筛选掉排在后面的基因。 应用程序应用程序GRAILEXP ( :/)GeneParser ( :/obesitygene.pbrc.edu/
20、eesnyder/geneparser.htm)GRAILGRAIL queryGRAIL results3.5.9 其他基因识别程序介绍其他基因识别程序介绍l基于规那么的识别方法基于规那么的识别方法(GeneID)l语义学的方法语义学的方法(GenLang)l决策树方法决策树方法 (MORGAN)lZ curve1. GeneID 1. GeneID 是一个基于规那么的基因识别系统是一个基于规那么的基因识别系统, , 识别的依据是编码度量和信号强度。识别的依据是编码度量和信号强度。识别转录剪切位点、起始密码子和终止密码子，并识别转录剪切位点、起始密码子和终止密码子，并对识别结果打分。对识别结
21、果打分。根据所识别的功能位点构造外显子，以相应的功能根据所识别的功能位点构造外显子，以相应的功能位点得分加上编码位点得分加上编码DNADNA序列马尔柯夫模型的对数序列马尔柯夫模型的对数似然比值作为外显子的得分。似然比值作为外显子的得分。利用启发式的规那么将这些外显子组装成基因模型。利用启发式的规那么将这些外显子组装成基因模型。 2. 语义学方法语义学方法 用形式语法描述基因结构和生物分子序列用形式语法描述基因结构和生物分子序列的许多其它特征，通过句法模式识别技术检测的许多其它特征，通过句法模式识别技术检测这些特征。这些特征。 GenLang使用的就是这类方法，用于识别真使用的就是这类方法，用于
22、识别真核编码基因。在语义学上下文环境中，将编码核编码基因。在语义学上下文环境中，将编码度量和信号强度解释为各个规那么的代价。度量和信号强度解释为各个规那么的代价。 GenLang通过训练优化得到一个形式语通过训练优化得到一个形式语法，并用它来产生最小代价的基因模型。法，并用它来产生最小代价的基因模型。3. MORGAN3. MORGAN (multiframe optimal rule-base gene analyzer)(multiframe optimal rule-base gene analyzer) 是一个寻找基因的集成系统，该系统使用是一个寻找基因的集成系统，该系统使用多种技术，
23、该系统使用了决策树多种技术，该系统使用了决策树(decision decision treetree)分类器。分类器。 将决策树与其它识别起始密码子、剪切位将决策树与其它识别起始密码子、剪切位点的新方法结合在一起，发现点的新方法结合在一起，发现DNADNA序列中的外显序列中的外显子和内含子结构。子和内含子结构。 4. Z curve( (天津大学生物信息中心天津大学生物信息中心) ) Z Z 曲线是表示曲线是表示DNA DNA 序列的一个等价的三维空间序列的一个等价的三维空间曲线。通过对曲线。通过对Z Z 曲线的研究来对基因组序列进行研曲线的研究来对基因组序列进行研究是一种几何学的途径。究是一
24、种几何学的途径。 几何学名词与概念，如座标系、空间、投影、几何学名词与概念，如座标系、空间、投影、曲线、曲率等构成了分析基因组序列的工具。曲线、曲率等构成了分析基因组序列的工具。 例：例： 酿酒酵母基因组基因识别软件酿酒酵母基因组基因识别软件ZCURVE_YZCURVE_Y 冠状病毒基因组基因识别软件冠状病毒基因组基因识别软件ZCURVE_CoVZCURVE_CoV 天津大学生物信息中心网站效劳工程信息天津大学生物信息中心网站效劳工程信息TUBIC - :/ TUBIC - :/ 天津大学生物信息中心网站天津大学生物信息中心网站ZCURVE 1.02 ZCURVE 1.02 细菌和古细菌全基因
25、组细菌和古细菌全基因组ab initio ab initio 基因识别基因识别Zcurve_C 1.0 Zcurve_C 1.0 细菌和古细菌基因组中单个基因识别细菌和古细菌基因组中单个基因识别Zcurve_Y 1.0 Zcurve_Y 1.0 酿酒酵母基因组基因识别酿酒酵母基因组基因识别Zcurve_CoV 2.0 Zcurve_CoV 2.0 冠状病毒含冠状病毒含SARS-CoVSARS-CoV基因组基因识别基因组基因识别GS-Finder 1.0 GS-Finder 1.0 细菌和古细菌基因起始密码子位点识别细菌和古细菌基因起始密码子位点识别Zcurve_DB 1.0 1000 Zcur
26、ve_DB 1.0 1000 余种生物基因组的余种生物基因组的Z Z 曲线数据库曲线数据库DEG 1.1 DEG 1.1 细菌和古细菌必需基因数据库细菌和古细菌必需基因数据库 基因识别程序及访问地址基因识别程序及访问地址HP主页；主页；ESE-mail效劳器；效劳器；WSweb效劳器；效劳器；CL客户客户/效劳器协议；效劳器协议；EX有可执行代码；有可执行代码；SC有源代码有源代码各程序的性能比较敏感性各程序的性能比较敏感性(1)被预测出的真实编码核酸的被预测出的真实编码核酸的%；敏感性敏感性(2)被正确识别出的编码外显子的被正确识别出的编码外显子的%；特异性特异性(1)预测出的编码核酸为真实
27、编码核酸的预测出的编码核酸为真实编码核酸的%；特异性特异性(2)预测出外显子为真实外显子的预测出外显子为真实外显子的%基因组识别方法小结基因组识别方法小结最长最长ORF法法密码子频率密码子频率剪切比对剪切比对动态规划动态规划神经网络神经网络隐马尔可夫模型隐马尔可夫模型其他其他Prediction of gene structure (exons, splicing sites, promotors) lAAT (Analysis and Annotation Tool for Finding Genes in Genomic Sequences) Michigan (USA) lAGenDA
28、(gene-prediction tool that is based on cross-species sequence comparison) Bielefeld (Germany) lATGpr (identifies the initiation codons in cDNA sequences) HRI (Japan) lAUG_EVALUATOR (for start codons prediction) ITBA (Italy) lBacterial Promoter, Operon and Gene Finding SoftBerry lBioProspector (Disco
29、vering Conserved DNA Motifs in Upstream Regulatory Regions of Co-Expressed Genes) Stanford (USA) lBCM Gene Finder (exons, splicing sites, promoter, coding region) BCM, see also Gene Feature Searches lCassandra (Recognition of protein-coding segments in eukaryotic DNA) USC (USA) lCDS (Search Coding R
30、egions) Pasteur, see also advanced form (French) lCHECKTRANS (ORF property statistics) Pasteur (French) lCister (Cis-element Cluster Finder) Boston (USA) lCister (Cis-element Cluster Finder) Boston (USA) lConPro (consensus promoter predictor) Michigan (USA) lCore-Promoter Finder CSHL (USA) 基因识别方法存在的
31、问题和局限性基因识别方法存在的问题和局限性 1关于基因的定义不明确关于基因的定义不明确 统一定义统一定义 2目前的方法仅仅识别蛋白质编码基因目前的方法仅仅识别蛋白质编码基因 转录信号转录信号 3现有的许多方法仅检测单个基因现有的许多方法仅检测单个基因局部基因、多重基因局部基因、多重基因 4基于同源分析的方法是保守的基于同源分析的方法是保守的不可能发现新的基因不可能发现新的基因 5 无视关于基因结构的生物学知识无视关于基因结构的生物学知识基因表达的真实分子机制基因表达的真实分子机制 习题习题l简述基于剪切比对的基因识别的方法步骤简述基于剪切比对的基因识别的方法步骤 l表达候选基因位于给定的表达候选基因位于给定的DNA序列需满足的一序列需满足的一致性条件。致性条件。l考虑下面一条基因序列，标出其中可能的起始考虑下面一条基因序列，标出其中可能的起始密码子和终止密码子，并标出可能的基因转录密码子和终止密码子，并标出可能的基因转录剪切位点，并做出位点图。剪切位点，并做出位点图。 cgatgttcgtcccggagaccatgggcgcgtacatcggattcgaagctctgaggct
