生物信息学计算机算法,生物信息学算法分析报告

利用双序列的比对(pairwise

sequence alignment 可以反映不同序列之间的相似性，并是多序列对比算法的核心要素。对于已知的一对两个序列，在实施它们之间的对比过程时，请识别出它们之间的 edit distance（Edit）。

Distance计算问题）主要是为了计算序列之间的匹配程度（包括Match与Gap得分为主要指标，并考虑Mismatch以及PAM250等特征）。其中Gap部分采用特定罚分函数（记为W），该函数基于gap段长度k进行赋值。通常采用以下几种形式来表示（如线性递增形式）： W(k)=...

k * d(k)＝ init + (k -

1，其中d表示每个核苷Gap表示开始一个Gap为继续一个Gap。

例：

Mismatch ACTCT

ACGCT Gap:

ACCT和序列ACTCT AC -CT

由于ACTCT序列中出现了Gap现象，并且第二个序列相对于第一个序列发生了Insertion事件。这种比对算法建立在动态规划方法的基础之上，并采用局部最优对齐策略。相比之下，在早期的研究中最初建立在动态规划框架下的全局最优比对方法则被命名为Needleman-Wunsch算法：

－W算法在时间和空间上都耗费了很多资源，对于长度分别为n(n2

，Mismatch的罚分均为0F(i,j) =max{ F(i-1,j-1)

+s(xi,yj), max{F(i-k,

j-1)–W(k)+s(xi,yj)},

max{F(i-1, j-l) –W(l)

+s(xi,yj)}}

表示对应于两个序列中的i位置的最后得分。S(xi,

yj)表示i位置的核苷xi匹配(Match)上的得分。而W(k)时的gap的罚分。

计算所需要的时间为2*(i-1)+2*(j-1)+1＋j－1，0..m-1比较次数为i+j-2 for (i = 1; i < n; i++)

for (j = 1; j < n; j++)

F(i,j) =max{ F(i-1,j-1)

+s(xi,yj),

max{H(i-k,

j-1)–W(k)+s(xi,yj)},

max{F(i-1, j-l) –W(l)

+s(xi,yj)}}

总共需要的加法次数为(4n-5)*(n-1)

2/2，则应为O(n3)，而比较次数为(n-1)3，则也为O(n3)。

F(i,j) =max{ F(i-1,j-1) +s(xi,yj),

F(i-1, j-1)–d, F(i-1, j-1) –d}

其中d代表出现gap时的罚分，在这种情况下，则计算量缩减至O(n²)；然而实际应用中始终采用这一变体。

而序列最终的比对结果可以按照分值和中间的记录反方向查找得到。

在Waterman进行序列比对的过程中，并非必须关注整个序列的所有内容；实际上只要求关注到某个特定的部分即可满足需求；此外，在Crossmatch过程中会剔除掉那些Vector

F(i,j) =max{ F(i-1,j-1)

+s(xi,yj), max{F(i-k,

j)–W(k)}, max{F(i, j-l)

–W(l)}，0}

在简单形式下s(ai, bj) = match = 1; Wk = 1 + 1/3 * k; Wl = 1 +

1/3 *

l；通常情况下，则主要采用基于替换矩阵的得分来评估。类似前面N－W算法，在实际应用中也可采取类似的方式以降低时间复杂度：

F(i,j) =max{

F(i-1,j-1)＋s(xi,yj), F(i-1,

j)－d, F(i, j-1)–d，0}

相对于简化形式而言，在程序中采用了单一罚分值d的方式，并通过一些技巧降低了空间复杂度；但仅改变了其常数因子。

设i)序列，j是查询序列：

s_ij位和查询的j对j的最高得分

t_ij：目标的i位对齐、且i对GAP u_ij：目标的i位对齐、且j对GAP则 s_ij = max( max

(s_{i-1,j-1},t_{i-1,j-1},u_{i-1,j-1}) + score(x_i,y_j), 0)

(对角线) t_ij = max(s_{i-1,j}

+ gap_init, t_{i-1,j} + gap_ext, u_{i-1,j} + gap_init)

u_ij = max(s_{i,j-1} +

gap_init, t_{i,j-1} + gap_init, u_{i,j-1} + gap_ext)

(i)

s_ij中存放max (s,t,u) + gap_init。这样t_ij=max(maxstu_{i-1,j},

t_{i-1,j} + gap_ext)。

(ii) 存储一行maxstu_ij。而u只需存放一个值。