Week 2. Sequence Alignment (序列比对)

MOOC Course_note

---

解决问题：相似序列的同源性和功能域分析

利用全局算法进行动态比对

例子：使用Pairwise Seq A 分析两条氨基酸序列

使用软件：Pairwise Seq A

填入待分析蛋白质的氨基酸序列并开始分析

标记行含义：

符号	含义
|	相同氨基酸
: \ .	替代氨基酸(substitution)，:表示比较相似，.表示不太相似[1]
(空格)	空白片段的插入或者删除(Insert/Deletion)[^f2]

空白罚分：

$$Penalty = d + (n-1) \times e$$
$$Final score = \sum{substitution} + (-1) \times \sum{Gap penalty}$$
d: Opening gap penalty, 10
e: Extention gap penalty, 0.5
n: Number of gap

全局对比原理解释

从一个极端的情况说起

假设有两条序列S1和S2，在设计算法时，我们先假设一个极端的情况，即每一个位子都对应空位（假设每条序列上有2个氨基酸）。则有如下六种情况：

_AB_	AB__	_A_B	A_B-	__AB	A__B
a__b	__ab	a_b_	_a_b	ab__	ab

可以看成，比如上面一条氨基酸链有4个位子，任选两个位子作为空格$C_4^{2}=6$。

所以，如果有n个氨基酸，全部空位相对的可能情况就有$C_{2n}^{n}$
老师的式子没看懂，貌似是用矩阵的解法？

一对残基的三种情况

就一对残基来说，一共有如下三种情况：S-T, S-Gap, Gap-T

这三种情况用数学式表示则为：
1. $F(i-1,j-1)+S(i,j)$
2. $F(i-1,j)+d$
3. $F(i,j-1)+d$

动态分析（Dynamic Programming）

原理：全局最优解就是局部最优解的总和

基本思路：
1. 将问题分解成若干小问题
2. 逐一找到小问题的最优解
3. 用小问题的最优解构建大问题的最优解

因此，比较一对残基的三种解法的最优解的基本思路就是：
好的+好的=好的

ex: Dynamic Programming Matrix
空位罚分统一记为-5

-	A	C	G	T
A	2	-7	-5	-7
C	-7	2	-7	-5
G	-5	-7	2	-7
T	-7	-5	-7	2

-	-	A	A	G	T
	0	-5	-10	-15	-20
A	-5	2	-3	-8	-13
G	-10	-3	-3	-1	-6
C	-15	-8	-8	-6	-6
T	-20	-13	-13	-13	-4

先依次填入全部空位的分数，0，-5，-10和-15。然后，每个空格按照一对残基的三种情况填入最优的分数。

回溯可得两个最优解：

Solution 1	Solution 2
AAG_T	AAG_T
A_GCT	_AGCT

从全局比对到局部比对

全局比对的问题

全局比对又被称作Needleman-Wunsch Algorithm

全局比对有两个问题：
1. 两条氨基酸链虽然在全局比对时差异较大，但可能有相同的功能域
2. 70年代发现了内含子，核酸序列比对从此需要处理内含子

局部比对(Smith Waterman算法)

在全局比对的基础上加上下限0，则：

1. $F(i-1,j-1)+S(i,j)$
2. $F(i-1,j)+d$
3. $F(i,j-1)+d$
4. $0$

-	-	A	A	G	T
	0	0	0	0	0
A	0	2	2	0	0
G	0	0	0	4	0
C	0	0	0	0	0
T	0	0	0	0	2