加载中…
个人资料
铁汉1990
铁汉1990
  • 博客等级:
  • 博客积分:0
  • 博客访问:1,336,032
  • 关注人气:828
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
正文 字体大小:

【T】每日一生信--从状态到马尔可夫链(1)

(2013-10-28 14:38:28)
标签:

马尔可夫链

状态

分类: bioinformatic
    前面我们提到了空位罚分的原则,那里面我们是将产生gao open和gap exending 等同来看的,但是gap 和gap extending 应该区分来看待,分别给予不同的罚分:
      Penalty = d + (n-1)*e 
    在计算的过程中,要想区分gap open和gap extending ,我们需要引入状态的概念,也就是需要记住之前是否open 了一个gap.之前我们也提到两条序列比对的过程中,两条序列中需要比对的两个碱基X,Y,要么比对上,可以是不完全比对上,要么X对上空格,要么Y对上空格。如下图
【T】每日一生信--从状态到马尔可夫链(1)
    当我们将gap extending考虑进来,算法就如下罗,M(i,j)是横左边为i,纵坐标为j时,那个方格子里面最高的分数(总分数),它来源三种情况。一次类推。

【T】每日一生信--从状态到马尔可夫链(1)
    跟之前的F相似,我们用动态规划矩阵,将三组转化关系表示在三个平面间的填充,只是对于每一个平面而言,回溯关系既可能来自本平面,也可能来自另外一个平面,或者说另外一个状态,我们构造一个马尔可夫链(由俄国数学家,一个基于概率的随机过程模型,用于刻画一组存在关联的随机事件)
【T】每日一生信--从状态到马尔可夫链(1)

马尔可夫链:A Markov chain describes a discrete stochastic process at successive times. The transitions from one state to all other states, including itself, are governed by a probability
distribution。(用于描述一组弥散状态间在不同时刻的转移关系,值得注意的是,这里的转移关系不需要是已确定的,只需要由一个概率分布描述即可。唯一的要求是t时刻的状态分布又且只由之前有限个m时刻状态分布概率来确定,称为m阶马尔可夫链)
    事实上,我们通常只考虑最简化的情形,1阶马尔可夫链,当前的状态且只于前一个状态相关。我们引入转移概率的概念。在t时刻从k态转移到l态的概率,并构成一个转移矩阵,从定义上我们知道这个矩阵沿对角线不是对称的。
【T】每日一生信--从状态到马尔可夫链(1)
    通常,我们会假定这个转移概率与t无关,也就是所谓的齐次马尔可夫链,这也刚好是我们线性组合罚分的情形。我们对每一种可能的延伸分配一个概率。首选考虑M到X,Y,也就是gap open的概率,以及X,Y到自身,也就是gap extending的概率。然后我们可以得到其他的几个概率分布,从而得到完整的转移概率矩阵。我们可以简单的根据乘法定理来计算出任何一个比对的概率值。比如如下图的这个例子,我们将相应的概率依次乘起来,就可以得到对应的概率值。事实上,我们可以对任意比对计算出概率值,也就是说我们通过引入马尔可夫链,给出了序列的概率解释
【T】每日一生信--从状态到马尔可夫链(1)

马尔可夫链几个问题?
There isn’t direct transition between X and Y in our model, do you think it’s reasonable?
Explain your answer.
Is it possible to have global alignment based on the rephrased Markov Chain‐based model?
Explain your answer.

注:博文整理的内容来自高歌老师课件。



0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有