序列比对与动态规划

生物信息的思考方式

biological question

• 生物学问题
• 有什么意义

data

• 输入数据是什么
• 哪些可接受的数据格式A

model

• 如何用计算的方法解决
• 什么是数据的model

algorithm

• 算法是什么
• 效率如何，有哪些局限性

序列比对

问题

• 如何判断两条序列的相似性
• 相似序列带来可能的相似功能

网站实例

• 根据替换矩阵来衡量打分
• 替代矩阵是三角阵，冒号是比较相似，点是不太相似，线是完匹配
• indel（insertion or deletion 的缩写）=gap 空位罚分
• gap opening 和 extending 不同 penalty=d+(n-1)*e
• Affine gap penalty: opening a gap receivesa penaltyof d; extending a gap receives apenalty of e. So thetotal Penalty for a gapwith length n would be:Penalty= d + (n-1)* e
• Final Score = (sum of substitution scores) + (-1) *(sum of Gap Penalty)

序列比对使用穷举法是不现实的

算法

残基的比对方式只有两种

• 空位
• 比对到另一个残基

比对分数为各个残基比对分数之和

参数

• gap: 插入或者缺失
• cost(x,y)：the cost of aligning character x withcharacter y
• 最简单情况：cost(x,x) = 0 and cost(x,y) = mismatchpenalty 罚分为0

目标

• Can compute the edit distance by finding thelowest cost alignment
• Cost of an alignment：
  • sum of the cost(x,y) for the pairs of charactersthat are aligned + gap × number of - characters inserted

打分规则图解

识别比对图解

The best alignment that ends at a given pair symbols is the best alignment of the sequencesup to at point, plus the best alignment for thetwo ditional symbols.

动态规划 Dynamic Programming

Dynamic Programming solves problems bycombiningthe solutions to sub‐problems

三步策略 （现在好的加之前最好的是总体最好的）

• Break the problem into smaller sub‐problems.
• Solve these sub‐problems optimallyrecursively.
• Use these optimal solutions to construct anoptimal solution for the original problem

动态规划公式

• 公式解读1

  img

• 公式解读2

  img

• 公式解读3

  img

  • 公式的迭代转换为对矩阵进行填空（动态规划矩阵），从上到下，从左到右进行迭代

  • 迭代过程

    img
    • 以F(1,1)为例，可以是0+2；-5-5；-5-5，选最大的是2,
    • 以F(2,1)为例，可以说-5+2；2-5；-10-5, 有两个途径可以，且最大值是-3
    • 以此类推，迭代至终点

  • 回溯过程，得到最终比对

    img

  • 尝试理解

    img

---

加入靠谱熊基地，和大家一起交流