序列模式识别课件

生物信息学：预测生物信息学：预测r1.生物信息学最核心的问题：预测生物信息学最核心的问题：预测r2.生物信息学工具的作用：预测生物信息学工具的作用：预测r3.生物信息学所有的分析：预测生物信息学所有的分析：预测r4.基本假设基本假设(贝叶斯的哲学理念贝叶斯的哲学理念)：我们能够通过对：我们能够通过对已知世界的观察，总结经验，并以此来预测未知世已知世界的观察，总结经验，并以此来预测未知世界已经存在或者即将发生的事物界已经存在或者即将发生的事物/事件事件r5.在生物信息学中的应用：对现有的数据，使用在生物信息学中的应用：对现有的数据，使用合适的算法，进行训练，构建计算模型和计算工具，合适的算法，进行训练，构建计算模型和计算工具，预测未知的现象预测未知的现象本章内容提要本章内容提要r1.统计学基础统计学基础r2.序列模式序列模式r3.预测性能检验预测性能检验r4.位点特异性打分矩阵位点特异性打分矩阵(PSSM)r5.模体发现：模体发现：GibbsSampler等等r6.马尔科夫及隐马尔科夫模型马尔科夫及隐马尔科夫模型r7.模式识别的其他算法简介模式识别的其他算法简介1.统计学基础统计学基础排列组合排列组合r从从N个物品中取出个物品中取出k个物品的个物品的排列排列数（排序）数（排序）：r从从N个物品中取出个物品中取出k个物品的个物品的组合组合数（不排数（不排序）序）：概率模型概率模型r概率模型概率模型:一个能够通过不同的概率产生不同结果一个能够通过不同的概率产生不同结果的模型。概率模型可以模拟或者仿真某一类型的所的模型。概率模型可以模拟或者仿真某一类型的所有事件，并且对每个事件赋予一个概率。有事件，并且对每个事件赋予一个概率。r色子模型：一个色子存在色子模型：一个色子存在6个概率值：个概率值：p1,p2,p6，其中，掷出，其中，掷出i的概率为的概率为pi(i=1,2,6)。因此：。因此：pi0，且，且r考虑三次连续的掷色子，结果为考虑三次连续的掷色子，结果为1，6，3，则总，则总概率为：概率为：p1p6p3概率分布概率分布r1.考虑连续变量考虑连续变量x，例如：物体的重量。则，例如：物体的重量。则当重量确切为当重量确切为1公斤时的概率，为公斤时的概率，为0。r2.变量的区间：变量的区间：P(x0 xx1)r3.当区间无限小当区间无限小-0时，上式：时，上式：P(x-x/2xx+x/2)=f(x)xr4.f(x)称为概率密度函数称为概率密度函数r5.因此：因此：且二项分布二项分布r1.事件只有两种可能出现的结果。例如掷硬事件只有两种可能出现的结果。例如掷硬币，正面记为币，正面记为“1”，反面记为，反面记为“0”。r2.则，掷硬币则，掷硬币N次，有次，有k次是次是1的概率为：的概率为：二项分布的期望值二项分布的期望值r期望值代表了随机变量的期望值代表了随机变量的“平均平均”值。它值。它是把每个可能取值乘以对应的概率，然后是把每个可能取值乘以对应的概率，然后累加起来。累加起来。期望值期望值E(x)=二项分布的与标准方差二项分布的与标准方差r标准方差描述了随机变量中具有正概率值标准方差描述了随机变量中具有正概率值的分散性。所有可能的值离期望值的距离的分散性。所有可能的值离期望值的距离的平方，再乘以对应的概率。的平方，再乘以对应的概率。方差方差VarX=2泊松分布泊松分布r1.稀有事件发生的概率：在一个连续的时稀有事件发生的概率：在一个连续的时间或空间中，稀有离散变量出现的概率间或空间中，稀有离散变量出现的概率r2.N-,E(x)=e=2.71828泊松分布与二项分布的近似泊松分布与二项分布的近似r对于大的对于大的N及小的及小的p值的二项分布，能够相值的二项分布，能够相当准确地用一个参数为当准确地用一个参数为=Np的泊松分布近的泊松分布近似。似。r当实验次数很多而概率很小时：当实验次数很多而概率很小时：二项分布二项分布泊松分布泊松分布例例1：鸟枪法的覆盖率：鸟枪法的覆盖率r假设：需要测序的假设：需要测序的BAC长度长度200kbp;总共测序的序列数量：总共测序的序列数量：N;每次测序：每次测序：500bp；每次测序的覆盖率每次测序的覆盖率p：500/200kbp=0.0025因此：总覆盖率因此：总覆盖率=Np(每个点平均覆盖到的次数每个点平均覆盖到的次数)rk:测序能够覆盖到点测序能够覆盖到点X的次数。的次数。鸟枪法：覆盖率鸟枪法：覆盖率点点X X被覆盖被覆盖k k次的概率：（二项分布次的概率：（二项分布泊松分布泊松分布)当点当点X X一次都不被覆盖时，一次都不被覆盖时，k=0;k=0;此时的概率为：此时的概率为：覆盖率覆盖率vs.准确性准确性泊松分布：例泊松分布：例2rProf.Gene发现一条发现一条1mbp的序列上存在的序列上存在5个某种个某种调控信号，该调控信号在人的基因组上平均每调控信号，该调控信号在人的基因组上平均每500kbp出现一个。那么，完全是随机产生该种情出现一个。那么，完全是随机产生该种情况的概率是多少？况的概率是多少？r本例中，本例中，N=3.0*109bp-,E(x)=2(1mbp)r统计性显著：统计性显著：p-value0.05r非常显著：非常显著：p-value0.01超几何分布超几何分布r与二项分布的区别：不放回抽样。与二项分布的区别：不放回抽样。r例：有例：有N个球，其中红球个球，其中红球M个，白球个，白球N-M个，每个，每次拿出一个球次拿出一个球再再放回，总共放回，总共n次，其中有次，其中有m个球个球是红球的概率为是红球的概率为(二项式分布二项式分布)：p=M/N超几何分布超几何分布(2)r上例改为：有上例改为：有N个球，其中红球个球，其中红球M个，白球个，白球N-M个，每次拿出一个球个，每次拿出一个球不不放回，总共放回，总共n次，次，其中有其中有m个球是红球的概率为：个球是红球的概率为：并且，并且，0mMN超几何分布右尾概率超几何分布右尾概率r上例再改为：有上例再改为：有N个球，其中红球个球，其中红球M个，白个，白球球N-M个，每次拿出一个球个，每次拿出一个球不不放回，总共放回，总共n次，其中有次，其中有至少有至少有m个球是红球的概率为：个球是红球的概率为：并且，并且，0mMN超几何分布左尾概率超几何分布左尾概率r上例再改为：有上例再改为：有N个球，其中红球个球，其中红球M个，白个，白球球N-M个，每次拿出一个球个，每次拿出一个球不不放回，总共放回，总共n次，其中有次，其中有最多有最多有m个球是红球的概率为：个球是红球的概率为：并且，并且，0mMN超几何分布双尾概率超几何分布双尾概率r方法一：方法一：所有出现概率所有出现概率 0.05统计性不显著！统计性不显著！序列模式识别序列模式识别2.序列模式序列模式r1.功能结构域，功能结构域，functionaldomainr2.模块，模块，BLOCKr3.模体，模体，motifr4.模式，模式，pattern/profile功能结构域功能结构域r1.具有完整的、独立的三级结构具有完整的、独立的三级结构r2.具有特定的生物学功能具有特定的生物学功能r3.一般长度，几十到几百个氨基酸一般长度，几十到几百个氨基酸r4.允许插入允许插入/缺失，即允许存在缺失，即允许存在gap模块模块/BLOCKr1.几个到几十个氨基酸几个到几十个氨基酸r2.无无gap，从全局多序列比对的结果直接处理得到，从全局多序列比对的结果直接处理得到r3.描述蛋白质家族或者一类蛋白质的序列保守性描述蛋白质家族或者一类蛋白质的序列保守性BLOCK模体模体/Motifr1.不具有独立的三级结构不具有独立的三级结构r2.具有特定的生物学功能：结合，修饰，细胞亚定位，具有特定的生物学功能：结合，修饰，细胞亚定位，维持结构，等维持结构，等r3.长度一般几个到几十个氨基酸或者碱基；长度一般几个到几十个氨基酸或者碱基；r4.例如，例如，SUMO化的序列模体：化的序列模体：-K-X-E(:A,I,L,V,M,F,P;X:任意氨基酸任意氨基酸)模式模式/Pattern/Profiler1.在算法上用来描述一类功能结构域、模体或者在算法上用来描述一类功能结构域、模体或者模块的表示方式模块的表示方式r2.根据序列数据，构建的预测模型根据序列数据，构建的预测模型r3.数据形式：正则表达式数据形式：正则表达式r4.用来预测新的可能符合特定模式的序列用来预测新的可能符合特定模式的序列r5.例如，直接将例如，直接将-K-X-E视为视为SUMO化位点的，化位点的，普适的普适的“模式模式”，则可以预测所有包含该模式的，则可以预测所有包含该模式的蛋白质序列蛋白质序列3.预测性能的计算和检验预测性能的计算和检验r1.样本样本/检验数据：阳性数据检验数据：阳性数据(P)，阴性数据，阴性数据(N)a.阳性数据阳性数据(P)：真实的，被实验所证实的数据：真实的，被实验所证实的数据b.阴性数据阴性数据(N)：被实验所证明为无功能的数据：被实验所证明为无功能的数据r2.对于预测结果的评测，定义：对于预测结果的评测，定义：a.真阳性真阳性(TP):阳性数据中被预测为阳性的数据阳性数据中被预测为阳性的数据b.假阳性假阳性(FP):阴性数据中被预测为阳性的数据阴性数据中被预测为阳性的数据c.真阴性真阴性(TN):阴性数据中被预测为阴性的数据阴性数据中被预测为阴性的数据d.假阴性假阴性(FN):阳性数据中被预测为阴性的数据阳性数据中被预测为阴性的数据TPFPFNTNCutoff常用的检验指标常用的检验指标r1.灵敏度灵敏度(Sensitivity,Sn)对于真实的数据，能够预测成对于真实的数据，能够预测成“真真”的比例是多少的比例是多少r2.特异性特异性(Specificity,Sp)对于阴性的数据，能够预测成对于阴性的数据，能够预测成“假假”的比例是多少的比例是多少r3.准确性准确性(Accuracy,Ac)对于整个数据集对于整个数据集(包括阳性和阴性数据包括阳性和阴性数据)，预测总共的准确，预测总共的准确比例是多少比例是多少r4.马修相关系数马修相关系数(Mathewcorrelationcoefficient,MCC)当阳性数据的数量与阴性数据的数量差别较大时，能够更当阳性数据的数量与阴性数据的数量差别较大时，能够更为公平的反映预测能力，值域为公平的反映预测能力，值域-1,1常用的检验指标常用的检验指标(2)ROCcurverX轴：轴：1-SprY轴：轴：SnrROC的面积越的面积越大，表明其预测大，表明其预测能力越强能力越强预测性能的计算预测性能的计算rSelf-consistencyrLeave-one-outvalidationrn-foldcross-validationSelf-consistencyr1.将训练数据当成测试数据将训练数据当成测试数据训练数据中所有的阳性数据为测试数据中的阳性训练数据中所有的阳性数据为测试数据中的阳性数据数据训练数据中所有的阴性数据为测试数据中的阴性训练数据中所有的阴性数据为测试数据中的阴性数据数据r2.反映当前预测工具对目前已知的数据的预反映当前预测工具对目前已知的数据的预测能力测能力r3.假设：根据目前已知的数据所构建的计算假设：根据目前已知的数据所构建的计算模型能够反映未知的数据的模式模型能够反映未知的数据的模式r4.缺点：不能反映计算模型的稳定性缺点：不能反映计算模型的稳定性Leave-one-outvalidationr每次从数据集中去掉一个重新进行训练，每次从数据集中去掉一个重新进行训练，构建预测模型，并对去除的数据进行预测。构建预测模型，并对去除的数据进行预测。r保证每个数据去掉一次保证每个数据去掉一次n-foldcross-validationr将数据集分成将数据集分成n组，并保证阳性数据与阴性组，并保证阳性数据与阴性数据的比例与原数据相同数据的比例与原数据相同r随意将随意将n-1组作为训练数据，组作为训练数据，1组作为检验组作为检验数据，计算性能数据，计算性能r重复若干次，例如，重复重复若干次，例如，重复20次次r计算平均值计算平均值r缺点：每次计算结果有偏差缺点：每次计算结果有偏差预测性能及稳定性预测性能及稳定性r1.Self-consistency:反映检验性能（对已知数据反映检验性能（对已知数据的预测能力）的预测能力）r2.Leave-one-outvalidation&n-foldcross-validation:反映预测系统的稳定性（对未知数据反映预测系统的稳定性（对未知数据的预测能力）的预测能力）r3.预测性能预测性能vs.检验性能检验性能a.差距较小：系统稳定差距较小：系统稳定b.差距过大：系统不稳定，数据过训练差距过大：系统不稳定，数据过训练过训练过训练r1.根据已知数据构建的模型只能很好的适根据已知数据构建的模型只能很好的适用于训练数据用于训练数据r2.不适合用来预测未知数据不适合用来预测未知数据r3.对训练数据的微小改变对于预测性能影对训练数据的微小改变对于预测性能影响过大响过大r4.预测工具过训练：只能很好的符合训练预测工具过训练：只能很好的符合训练数据，而对新数据则性能很差数据，而对新数据则性能很差4.位点特异性打分矩阵位点特异性打分矩阵r(1)PositionSpecificScoringMatrix(PSSM)/WeightMatrixModel(WMM)r(2)对蛋白质家族进行多序列比对分析，发对蛋白质家族进行多序列比对分析，发现结果中保守的现结果中保守的BLOCKr(3)根据根据BLOCK序列推导相应的序列推导相应的PSSMr(4)不考虑不考虑gap的影响的影响r(5)BLOCK长度一般在几个长度一般在几个几十个残基几十个残基/碱碱基基BLOCK-PSSM代表每一列代表每一列二十种二十种氨基酸氨基酸矩阵中的数值：当前位置上，某矩阵中的数值：当前位置上，某种氨基酸出现的频率的种氨基酸出现的频率的log值值第二种第二种PSSMr每一个位置上显示每种氨基酸或者碱基出现的每一个位置上显示每种氨基酸或者碱基出现的频率频率碱基的位置碱基的位置四种碱基四种碱基第三种第三种PSSMr每一个位置显示氨基酸每一个位置显示氨基酸/碱基出现的概率碱基出现的概率PSSM矩阵使用矩阵使用rP(S|+)，根据阳性训练数据计算出来的概率；，根据阳性训练数据计算出来的概率；未知序列：未知序列：ACGGTACGG背景概率选择背景概率选择,P(S|-)r1.负样本负样本/阴性数据的概率计算阴性数据的概率计算r2.计算方法：计算方法：A.DNA序列，四种碱基出现的频率序列，四种碱基出现的频率B.蛋白质序列，蛋白质序列，20种氨基酸出现的频率种氨基酸出现的频率OddsRatioLog-oddsRatio计算流程：滑动窗口计算流程：滑动窗口r窗口宽度窗口宽度9bp，依次打分，依次打分r设定阈值（设定阈值（Threshold），凡是高于阈值的），凡是高于阈值的预测为阳性，低于阈值的预测为阴性预测为阳性，低于阈值的预测为阴性5.模体发现：模体发现：GibbsSamplerrGibbsSampler是一种是一种Monte-Carlo类的方法类的方法r随机抽样随机抽样r对于输入序列，找到一个最大的似然函数对于输入序列，找到一个最大的似然函数GibbsSampler算法算法(1)r1.从每条序列上从每条序列上随机随机的抽取一段序列，序列的抽取一段序列，序列长度固定长度固定所有所有序列序列motifGibbsSampler算法算法(2)r2.构建构建PSSM/权重矩阵权重矩阵GibbsSampler算法算法(3)r3.随机挑选一条序列随机挑选一条序列GibbsSampler算法算法(4)r4.用构建好的用构建好的PSSM对该序列上所有可能对该序列上所有可能的的motif进行打分进行打分(窗口滑动，每次窗口滑动，每次1个氨个氨基酸或者碱基基酸或者碱基)GibbsSampler算法算法(5)r5.根据似然性的计算，得到似然值最大的模根据似然性的计算，得到似然值最大的模体，即新的体，即新的motifGibbsSampler算法算法(6)r6.更新更新PSSM矩阵矩阵GibbsSampler算法算法(7)r7.反复迭代计算，直到似然性结果与反复迭代计算，直到似然性结果与PSSM不再发生变化不再发生变化StrongMotifACGTAGCAGibbsSampler:总结总结r1.模体发现的一种随机算法模体发现的一种随机算法(MonteCarlo)r2.寻找次优解的算法寻找次优解的算法r3.根据根据PSSM/WMM对随机抽取的序列进行对随机抽取的序列进行打分来调整采样，直到结果收敛打分来调整采样，直到结果收敛r4.不能够保证每次运算的结果一致：需要不能够保证每次运算的结果一致：需要多运算几次，并进行比较多运算几次，并进行比较r5.对蛋白质、对蛋白质、DNA、RNA序列模体的发现序列模体的发现有帮助有帮助期望最大化算法期望最大化算法r1.ExpectationMaximizationAlgorithmr2.已开发工具：已开发工具：MultipleEMforMotifElicitation(MEME)r3.motif大致的位置与长度是确定的大致的位置与长度是确定的r4.重点：确定重点：确定motif在每条序列上的起始位在每条序列上的起始位置置r5.分为两步：分为两步：Estep:估计估计motif起始位置的期望最大化起始位置的期望最大化Mstep:motif似然性的期望最大化似然性的期望最大化期望最大化算法期望最大化算法(2)r1.例，假设例，假设10条序列，条序列，长度长度20个碱基个碱基r2.进行多序列比对，大进行多序列比对，大致确定致确定motif的位置的位置r3.待找待找motif长度为长度为4个个碱基碱基Motif的概率的概率vs.背景概率背景概率r1.计算计算motif中每个位置的碱基的概率分布中每个位置的碱基的概率分布r2.背景概率背景概率:根据剩下的序列计算四种碱基的概率根据剩下的序列计算四种碱基的概率分布分布似然性概率值的计算似然性概率值的计算似然性概率值的计算似然性概率值的计算(2)r计算每条序列，在不同的起始位置，其似然性的概率计算每条序列，在不同的起始位置，其似然性的概率值值Estep:起始位置估计起始位置估计rZ值：值：motif在不同位置起始的几率值在不同位置起始的几率值r假设，假设，motif在任意位置起始的概率相同，则在任意位置起始的概率相同，则rZ值最大化，即为值最大化，即为“最可能的起始位置最可能的起始位置”Mstep：P值最大化值最大化r根据选择的最大根据选择的最大Z值，重新计算矩阵，并计值，重新计算矩阵，并计算算P值最大的值最大的motif；P P值最大值最大原先的原先的motifmotifEM算法：迭代算法：迭代Gibbs&EM:总结总结r1.基本假设：所有序列都拥有，且仅拥有基本假设：所有序列都拥有，且仅拥有一个一个motifr2.估算两个关联的函数：估算两个关联的函数：Gibbs(WMM&似然性似然性)，EM(motif起始位置，起始位置，Z值值&似然似然性性)r3.利用两个函数的其中之一修正另一个，利用两个函数的其中之一修正另一个，采取迭代采取迭代/反复计算的方法，使结果收敛反复计算的方法，使结果收敛r4.不保证得到的结果为最优，近似算法不保证得到的结果为最优，近似算法有待解决的问题有待解决的问题r1.给定的一组序列，可能的给定的一组序列，可能的motif仅在部分仅在部分序列中出现，怎么解决？序列中出现，怎么解决？r2.给定一组序列，其中存在某种给定一组序列，其中存在某种motif可能可能在序列上出现两次以上，如何解决？在序列上出现两次以上，如何解决？6.马尔科夫及隐马尔科夫模型马尔科夫及隐马尔科夫模型r1870年，俄国有机化学家年，俄国有机化学家VladimirV.Markovnikov首首次提出马尔科夫模型次提出马尔科夫模型r马尔科夫模型马尔科夫模型r马尔科夫链马尔科夫链r隐马尔科夫模型隐马尔科夫模型Vladimir V.MarkovnikovVladimir V.Markovnikov马尔科夫模型马尔科夫模型r马尔科夫模型：随机过程的一种，主要特马尔科夫模型：随机过程的一种，主要特点为点为“无后效性无后效性”，即根据当前的状态即，即根据当前的状态即可完全确定将来的状态可完全确定将来的状态马尔科夫性马尔科夫性&马尔科夫马尔科夫链链r1.定义：对于随机变量定义：对于随机变量X1,X2,X3,这些变量的范围，这些变量的范围，即他们所有可能取值的即他们所有可能取值的集合集合，被称为，被称为“状态空间状态空间”，而，而Xn的值则是在时间的值则是在时间n的状态。如果的状态。如果Xn+1对于过对于过去状态的去状态的条件概率分布条件概率分布仅是仅是Xn的一个的一个函数函数，则符合，则符合马尔科夫性马尔科夫性：r2.具有马尔科夫性的过程称为马尔科夫过程具有马尔科夫性的过程称为马尔科夫过程r3.时间时间(先后顺序先后顺序)和状态都离散的马尔科夫和状态都离散的马尔科夫过程称为马尔科夫链过程称为马尔科夫链马尔科夫模型：参数估计马尔科夫模型：参数估计r转移概率：转移概率：K-order马尔科夫模型马尔科夫模型r一阶马尔科夫模型：当前位置仅依赖前一位一阶马尔科夫模型：当前位置仅依赖前一位rk阶马尔科夫模型：当前位置依赖前一位，阶马尔科夫模型：当前位置依赖前一位，而前一位依赖前两位而前一位依赖前两位,前前k-1位依赖前位依赖前k位位r0阶马尔科夫模型：位点独立阶马尔科夫模型：位点独立Markov&PSSMr1.对真实的数据进行训练，对真实的数据进行训练，PSSM=0阶阶马尔科夫模型马尔科夫模型r2.对新序列的扫描：从头至尾，每次移动对新序列的扫描：从头至尾，每次移动1n位（窗口滑动的方法）位（窗口滑动的方法）r3.分别计算窗口内的序列，是分别计算窗口内的序列，是(+)和和(-)的概的概率，计算率，计算log-oddsratior4.设定阈值，若高于阈值，则预测为阳性设定阈值，若高于阈值，则预测为阳性另外另外r长度不确定！长度不确定！r起始位置不知！起始位置不知！rMarkovmodels&PSSM:Notwork!隐马尔科夫模型隐马尔科夫模型(HMM)r隐隐马尔科夫模型：马尔科夫模型：1.表示状态的可观察符号出现概率表示状态的可观察符号出现概率已知已知2.状态之间的转移概率状态之间的转移概率未知未知r与马尔可夫模型的本质区别：与马尔可夫模型的本质区别：隐马模型观察到的符号并不是与状态一一对隐马模型观察到的符号并不是与状态一一对应，而是通过一组概率分布相联系应，而是通过一组概率分布相联系ProfileHMMr1.多序列比对的结果中，氨基酸之间存在多序列比对的结果中，氨基酸之间存在的关系有匹配的关系有匹配(M),插入插入(I)和缺失和缺失(D):三种三种状态状态r2.HMM：三种状态之间的转换关系未知：三种状态之间的转换关系未知-hidden-转移概率转移概率r3.每个位置上的氨基酸每个位置上的氨基酸/碱基以及插入、缺碱基以及插入、缺失的频率失的频率/概率可以通过观测求得概率可以通过观测求得-nothiddenr4.模型训练：通过训练，估算转移概率模型训练：通过训练，估算转移概率例：例：CpG岛的岛的HMMr1.CpG岛：在人的基因组中，如果双碱基对岛：在人的基因组中，如果双碱基对CG出现，则出现，则C通常被甲基化。并且，甲基化的通常被甲基化。并且，甲基化的C很快会突变成很快会突变成T。因此基。因此基因组中因组中CpG岛非常少。然而，在基因的起始位置，例如岛非常少。然而，在基因的起始位置，例如promotor区域，因为功能的保守性，其序列很少突变，区域，因为功能的保守性，其序列很少突变，CpG的含量能够保持在的含量能够保持在4060%r2.Howtopredict?PSSM&Markovarenotworkatall!CpG岛：岛：HMMr存在两种状态：是存在两种状态：是CpG岛岛(CpGIsland,I)，不是，不是CpG岛岛(Genome,G)CpG岛：岛：HMMr1.Hidden:对当前未知的碱基，跳转到下一个位置，对当前未知的碱基，跳转到下一个位置，究竟是究竟是I还是还是G的概率，未知的概率，未知r2.Observable:I和和G中的四种碱基分布的概率能够通中的四种碱基分布的概率能够通过实际数据的观测进行计算过实际数据的观测进行计算转移概率转移概率发散概率发散概率预测预测CpGIsland:Viterbi算法算法r1.给定序列：给定序列：ATCGCA,预测预测CpG的位置的位置?初始概率初始概率：0.5CpGIsland:Viterbi算法算法(1)vATCGCA1C+G+A+0.1T+C-G-A-0.15T-0.5*0.20.5*0.3CpGIsland:Viterbi算法算法(2)vATCGCA1C+G+A+0.1T+0.015C-G-A-0.15T-0.02250.15*0.5*0.20.15*0.5*0.30.1*0.5*0.30.1*0.5*0.2CpGIsland:Viterbi算法算法(3)vATCGCA1C+0.0034G+A+0.1T+0.015C-0.00225G-A-0.15T-0.02250.0225*0.5*0.20.015*0.5*0.30.0225*0.5*0.30.015*0.5*0.2CpGIsland:Viterbi算法算法(4)vATCGCA1C+0.0034G+0.0005A+0.1T+0.015C-0.00225G-0.00034A-0.15T-0.02250.00225*0.5*0.20.00225*0.5*0.30.0034*0.5*0.20.0034*0.5*0.3CpGIsland:Viterbi算法算法(4)vATCGCA1C+0.00340.000075G+0.0005A+0.1T+0.015C-0.002250.00005G-0.00034A-0.15T-0.02250.0005*0.5*0.30.0005*0.5*0.20.0034*0.5*0.30.0034*0.5*0.2CpGIsland:Viterbi算法算法(5)vATCGCA1C+0.00340.000075G+0.0005A+0.10.0000075T+0.015C-0.002250.00005G-0.00034A-0.150.0000112T-0.02250.000075*0.5*0.20.000075*0.5*0.30.00005*0.5*0.30.00005*0.5*0.3CpGIsland:Viterbi算法算法(6)vATCGCA1C+0.00340.000075G+0.0005A+0.10.0000075T+0.015C-0.002250.00005G-0.00034A-0.150.0000112T-0.0225CpGIsland:预测结果预测结果r1.ATCGCA:其中，CGC被预测为CpG Island ATCGCAr2.Viterbi算法：求出在当前结果最大的概率值，以及保存相应的路线r3.递归算法：动态规划的算法r4.该例中，我们假设状态转移概率矩阵已知r5.如何推算状态的概率矩阵？参数估计：参数估计：Baum-Welch(EM)算法r目的：给定观察值序列目的：给定观察值序列O，通过计算确定一，通过计算确定一个模型个模型H H，使得使得P(O|H)最大最大r算法步骤：算法步骤：1.初始模型（待训练模型）初始模型（待训练模型）H H0,2.基于基于H H0以及观察值序列以及观察值序列O O，训练新模型训练新模型H H；3.如果如果logP(O|H H)-log(P(O|H H0)算法设计及程序实现算法设计及程序实现-预测，为实验提供指导预测，为实验提供指导-反馈，进一步优化生物反馈，进一步优化生物学模型学模型序列模式识别：总结序列模式识别：总结r1.PSSM:简单、高效，实为居家旅行之必备简单、高效，实为居家旅行之必备工具工具r2.Gibbssampler:motif识别的瑞士军刀识别的瑞士军刀r3.HMM:生物信息学的生物信息学的“万能算法万能算法”，大杀器，大杀器r4.然而然而,仍有待改进！仍有待改进！