序列比对与动态规划

2017-08-13, 708 words, 3 min read

生物信息的思考方式

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
公式解读 2
公式解读 3
- 公式的迭代转换为对矩阵进行填空（动态规划矩阵），从上到下，从左到右进行迭代
- 迭代过程
  - 以 F(1,1) 为例，可以是 0+2；-5-5；-5-5，选最大的是 2,
  - 以 F(2,1) 为例，可以说-5+2；2-5；-10-5, 有两个途径可以，且最大值是-3
  - 以此类推，迭代至终点
- 回溯过程，得到最终比对
- 尝试理解