[医药卫生]基因识别PPT课件

-,1,3.5基因识别,生化教研室邢军,-,2,3.5.7基于剪切比对的基因识别方法3.5.8基于动态规划的基因结构预测方法3.5.9其他基因识别程序介绍,-,3,3.5.7基于剪切比对的基因识别方法,基于剪切比对的基本思想基于剪切比对的方法PROCRUSTES程序特点,-,4,1.基于剪切比对(splicedalignment)的基本思想,利用数据库中的同源信息进行基因识别，包括DNA、RNA和蛋白质数据库。,-,5,首先通过分析所有可能的剪切接受体位点和剪切给体位点，构建一组候选的外显子。然后进一步分析候选外显子，探查所有可能的外显子组合，寻找一个与已知目标蛋白质或其他表达序列最匹配的组合。,2.方法,-,6,alternativesplicing,-,7,geneA,alternativesplicing,-,8,预选选择所有长度大于50bp并介于保守的剪切接受位点和给体位点之间的ORF，作为候选的外显子；减小搜索范围对于候选的外显子计算其6目编码度量值，并从大到小将它们排列起来；搜索，筛选对照蛋白质序列数据库进行搜索，寻找相似体。,3.一种半自动的综合方法识别基因过程,-,9,PROCRUSTES程序V4.01(/software/procrustes/)利用已知蛋白质和cDNA的相似信息识别基因或预测基因的结构。首先生成一系列候选的外显子，PROCRUSTES考察所有候选外显子组合而成的可能的链（代表一种候选基因结构），并找出一个与目标蛋白质（对应的密码子序列）具有最大全局相似性的候选基因结构。,-,10,4.特点,虽然可能的外显子组合很多，但剪切比对算法仍然很快，可以处理大量的包含多基因的基因组序列片段仅当存在可以参考的功能序列时才有效更适用于真核基因识别不能用于识别新基因,-,11,3.5.8基于动态规划的基因结构预测方法,动态规划算法介绍多阶段决策过程的最优化基于动态规划的基因结构预测,-,12,1.动态规划算法介绍,（1）定义：动态规划（dynamicprogramming）一种可以有效地探求一定复杂问题的各种可能的解决方案的程序；将一个问题合理地分解成一些小的子问题，然后利用部分计算解得到最终答案。,-,13,（2）动态规划算法的基本思想：将待求解的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的解,-,14,（3）动态规划的应用是序列比对的基本工具HMM模型联合使用,-,15,20世纪50年代初R.E.Bellman等人在研究多阶段决策过程(Multistepdecisionprocess)的优化问题时，提出了著名的最优化原理(Principleofoptimality)把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法-动态规划。,-,16,2.多阶段决策过程的最优化,(1)多阶段决策问题动态规划是把多阶段决策问题作为研究对象。求解的全过程划分为若干个相互联系的阶段(即将问题划分为许多个相互联系的子问题)。在它的每一阶段都需要作出决策，并且在一个阶段的决策确定以后再转移到下一个阶段。,-,17,多阶段决策过程(Multi-Stagedecisionprocess)前一个阶段的决策要影响到后一个阶段的决策，从而影响整个过程。各个阶段所确定的决策就构成了一个决策序列，称为一个策略。,-,18,最优策略：在所有可供选择的策略中，对应效果最好的策略称为最优策略。把一个问题划分成若干个相互联系的阶段选取其最优策略，这类问题就是多阶段决策问题。,-,19,多阶段决策过程最优化的目标是要达到整个活动过程的总体效果最优。决策者在每段决策时不应仅考虑本阶段最优，还应考虑对最终目标的影响，从而作出对全局来讲是最优的决策。动态规划就是符合这种要求的一种决策方法。,-,20,(2)多阶段决策问题举例例如：1)工厂生产过程2)设备更新问题3)连续生产过程的控制问题问题的发展过程都与时间因素有关,-,21,4）资源分配问题5）运输网络问题,-,22,运输网络图示,-,23,3.基于动态规划的基因结构预测（1）基因识别最终任务是建立完整的基因结构模型一个理想的基因识别程序应该能够发现完整的基因结构（,e1,i1,in-1,en,）,-,24,（2）外显子组装方法利用编码度量、剪切位点得分、起始密码、终止密码及非编码区特征信息等（3）直接实现组合存在的问题所有参数转化为一个有意义且唯一的指数和困难；真实基因的外显子数量较多，计算上会产生数据组合爆炸；,-,25,（4）构建基因模型方法剪切位点形成外显子和内含子的边界搜集候选外显子候选基因,DNA片段及候选位点,exon,受体位点起始密码子,给体位点终止密码子,exon,exon,给体位点,受体位点,intron,ag,ag,gt,gt,-,26,基因剪切位点接受体（acceptor）位点-“ag”剪切给体（donor）位点-“gt”每一个位点可以被赋于一个加权值（表示成为功能位点的可能性），该加权值取决于对应位点附近的序列，可以利用前面介绍的编码区域识别方法，通过计算而得到。,DNA片段及候选剪切位点,-,27,基因的可变剪切,-,28,geneA,基因可变剪切示意,-,29,候选外显子列表,-,30,候选基因是一条非相交的外显子和内含子的链，表示为（i0,e1,i1,ij,el,en,in）其中ij代表内含子（0jn）el代表外显子（1ln）i0和in并非真实的内含子，它们分别代表基因两侧的非编码序列,-,31,候选基因位于给定的DNA序列满足下列一致性条件：1）所有外显子加起来的长度是3的整数倍；2）在各个外显子内部（除最后一个外显子的最后一个密码子），没有终止编码；3）第一个内含子-外显子边界（i0,e1）是翻译起始编码，而最后一个外显子-内含子边界（en,in）是终止编码。,-,32,给定一个标明位点或一系列候选外显子和候选内含子的序列，我们可以构造一个无循环有向图G，使得该图中一条完整的路径代表一个完整的基因结构。基因识别问题就转化为图G的路径分析问题，可以用动态规划来解决。如何解决，还依赖于所用的特定的打分函数，依赖于选择外显子的过程。,-,33,位点图无循环有向图G每个顶点代表候选的转录剪切位点、起始密码子或终止密码子。图中的顶点分为两层，将外显子的左边界置于上层，而将外显子的右边界置于下层。按照各位点在原序列中的位置，从左至右将两层中的顶点依次连接起来，形成有向边，或者称为弧。,-,34,-,35,-,36,位点图（分层标注剪切位点）,另设两个特殊的顶点，即起点（source）和终点（sink）从起点到终点的任何一条路径代表一个可能的基因结构,-,37,该路径上从代表起始密码子的顶点开始，到代表终止密码子的顶点为止，其中的每一条自上而下的弧代表一个外显子，自下而上的弧代表一个内含子。过滤不满足一致性条件（1）（3）的路径，使得仅仅保留没有框内终止编码的外显子及连接各顶点的具有一致性阅读框的内含子。这样，图中的每一条路径对应于一个经过处理的候选基因。,-,38,过滤不满足一致性条件的路径,一个候选基因结构在位点图上对应的路径,-,39,候选基因所对应的道路图中的路径,-,40,利用动态规划算法寻找最优的路径，从而构造代价最小（或得分最高）的基因。这种方式在GeneParser和GRAIL中得到应用。,-,41,动态规划法求最优路径每一条弧附加一个权值外显子、内含子度量每个节点附加权值剪切位点度量,-,42,综合评价一个基因结构的得分可按下式计算,A剪切受体位点得分D剪切给体位点得分C编码得分L外显子长度N相继外显子个数与是对于参数在学习样本上的均值和标准方差,-,43,真正的外显子在许多高得分的结构中出现对打分以后的基因按递减顺序进行排队最后仅考虑排在前面的一部分候选基因筛选掉排在后面的基因。,-,44,应用程序,GRAILEXP(/grailexp/),GeneParser(/eesnyder/geneparser.htm),-,45,GRAIL,-,46,-,47,-,48,GRAILquery,-,49,GRAILresults,-,50,3.5.9其他基因识别程序介绍,基于规则的识别方法(GeneID)语义学的方法(GenLang)决策树方法(MORGAN)Zcurve,-,51,1.GeneID是一个基于规则的基因识别系统,识别的依据是编码度量和信号强度。识别转录剪切位点、起始密码子和终止密码子，并对识别结果打分。根据所识别的功能位点构造外显子，以相应的功能位点得分加上编码DNA序列马尔柯夫模型的对数似然比值作为外显子的得分。利用启发式的规则将这些外显子组装成基因模型。,-,52,2.语义学方法用形式语法描述基因结构和生物分子序列的许多其它特征，通过句法模式识别技术检测这些特征。GenLang使用的就是这类方法，用于识别真核编码基因。在语义学上下文环境中，将编码度量和信号强度解释为各个规则的代价。GenLang通过训练优化得到一个形式语法，并用它来产生最小代价的基因模型。,-,53,3.MORGAN(multiframeoptimalrule-basegeneanalyzer)是一个寻找基因的集成系统，该系统使用多种技术，该系统使用了决策树(decisiontree)分类器。将决策树与其它识别起始密码子、剪切位点的新方法结合在一起，发现DNA序列中的外显子和内含子结构。,-,54,4.Zcurve(天津大学生物信息中心)Z曲线是表示DNA序列的一个等价的三维空间曲线。通过对Z曲线的研究来对基因组序列进行研究是一种几何学的途径。几何学名词与概念，如座标系、空间、投影、曲线、曲率等构成了分析基因组序列的工具。例：酿酒酵母基因组基因识别软件ZCURVE_Y冠状病毒基因组基因识别软件ZCURVE_CoV,-,55,天津大学生物信息中心网站服务项目信息TUBIC-天津大学生物信息中心网站ZCURVE1.02细菌和古细菌全基因组abinitio基因识别Zcurve_C1.0细菌和古细菌基因组中单个基因识别Zcurve_Y1.0酿酒酵母基因组基因识别Zcurve_CoV2.0冠状病毒（含SARS-CoV）基因组基因识别GS-Finder1.0细菌和古细菌基因起始密码子位点识别Zcurve_DB1.01000余种生物基因组的Z曲线数据库DEG1.1细菌和古细菌必需基因数据库,-,56,基因识别程序及访问地址（HP主页；ESE-mail服务器；WSweb服务器；CL客户/服务器协议；EX有可执行代码；SC有源代码）,-,57,各程序的性能比较（敏感性(1)被预测出的真实编码核酸的%；敏感性(2)被正确识别出的编码外显子的%；特异性(1)预测出的编码核酸为真实编码核酸的%；特异性(2)预测出外显子为真实外显子的%）,-,58,基因组识别方法小结,最长ORF法密码子频率剪切比对动态规划神经网络隐马尔可夫模型其他,-,59,Predictionofgenestructure(exons,splicingsites,promotors)AAT(AnalysisandAnnotationToolforFindingGenesinGenomicSequences)Michigan(USA)AGenDA(gene-predictiontoolthatisbasedoncross-speciessequencecomparison)Bielefeld(Germany)ATGpr(identifiestheinitiationcodonsincDNAsequences)HRI(Japan)AUG_EVALUATOR(forstartcodonsprediction)ITBA(Italy)BacterialPromoter,OperonandGeneFindingSoftBerryBioProspector(DiscoveringConservedDNAMotifsinUpstreamRegulatoryRegionsofCo-ExpressedGenes)Stanford(USA)BCMGeneFinder(exons,splicingsites,promoter,codingregion)BCM,seealsoGeneFeatureSearchesCassandra(Recognitionofprotein-codingsegmentsineukaryoticDNA)USC(USA)CDS(SearchCodingRegions)Pasteur,seealsoadvancedform(French)CHECKTRANS(ORFpropertystatistics)Pasteur(French)Cister(Cis-elementClusterFinder)Boston(USA)Cister(Cis-elementClusterFinder)Boston(USA)ConPro(consensuspromoterpredictor)Michigan(USA)Core-PromoterFinderCSHL(USA),-,60,基因识别