利用双序列的比对(pairwise alignment)可显示出序列间的类似性，也是多序列比对算法的基础。对已知的两个序列，要进行序列比对，要发现这两个序列之间的距离（Edit Distances），就是要计算序列之间有多少匹配（Match和Gap的得分和Mismatch、PAM250等。Gap的罚分是另外定义的函数：W），其中k的长度，而W（k的罚分值，通常使用的有W）＝ k * d（k）＝ init + （k - 1，其中d表示每个核苷Gap表示开始一个Gap为继续一个Gap。

例：

       Mismatch       ACTCT

              ACGCT       Gap:

       ACCT和序列ACTCT              AC -CT

       ACTCT就出现了Gap，而第二个序列相对于第一个序列出现了Insertion       算法是基于动态规划的算法，是一种最优局部比对的方法，而最初的基于动态规划的最优全局比对的方法是Needleman－Wunsch       Needleman算法：

       －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}

<![endif]-->

其中d为出现gap时的罚分，这种情况下则计算量会缩小为O(n2)，而实际上应用的总是这种变体。

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

－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只需存放一个值。

Banded－Waterman算法：

当使用序列比较时，大部分情况是将序列和数据库中的序列进行逐个比对，而数据库中的序列很多都是和当前序列无关的，为了减少计算量，减少和不必要的序列进行全序列的比对（局部和全局），因而设计了Banded－W算法。如图所示，计算是处在条带之间的填充颜色的区域：

如果在区域内完全没有达到一个预期的比对域值，则序列之间基本上是没有可能得到很好的比对分值的，可以说这种方法是一种启发式算法，可以参考后面的多序列比对的启发式算法部分。空间复杂度应该为O＋n），其中k的宽度，而n为序列的长度，通常数据库序列要比Suject（k*n），而k来说是个常数，因此空间和时间复杂度均为O）。

：

的工作意图和NCBI的功能类似，都是用来寻找序列中可能是Vecotor的流程是：读入参数 -> 寻找Word、设置索引表index_words，word_block等 -> 匹配subject sequence和query sequence的Word进行 -> 。

一个Word中的连续若干个核苷的核酸子列，这里有两个参数：min_match_size，前者表示比较的Word的真实长度；而后者表示存储散列表中索引的Word。Index_word_size计算散列分值时使用的Word，而min_match_size的长度，缺省值为14长度的字符串按alphabet_size序列为4）对前index_word_size。然后find_subject_matches()（）对目标序列中的每个字（长度>=minmatch散列表中查找匹配的字并记录有关信息，然后再使用find_scores函数用来计算Banded函数，目的是为了找出序列中全部的Vector增加-minmatch的命令参数可以大幅度的减少做比对的时间。-bandwidth参数表示了使用Banded－W算法的真实的Band（band = 2 * bandwidth + 1是减少了运行时间，但是丢失了一定的敏感度（sensitivity和FastA之类的启发式算法中，也是要在Sensitivity和运行时间上做折衷。

在N、S－W中，进行比对时采用的替换矩阵的分值都是整数。基本上大规模的运算中并没有包含浮点运算。由于序列的一般都至少有几百个bp－W－W算法和各种简化版中都会用到一行中前面的元素。一种简单的并行化方法是每个计算单元计算一对序列的比较，因为一般情况下是将序列和数据库中的所有或一些序列进行比较。第二种计算方式是先求解一行中只依赖于前面一行的数据，即依赖于F(i-1,j-1)和F(i-1,j)的结果，这时可以使用一些矢量计算等，然后依赖于同一行的前面数据的则采用顺序计算。当然这时也可以采用一些展开的方法进行计算。例如已经计算出i，则F(i,j) = max(G(i,j), F(i, j-1)-d, 0) = max( G(i, j), max( G(i, j-1), F(i,  j-2)-d )-d, 0 ), 0 ) = max(G(i, j), G(i, j-1) – d, F(i, j-2) – 2*d, 0)，则F(i, j-1)则可以同时开始计算。但是存在着问题是计算两个的计算量是不同的，而且计算公式会变得复杂，特别是同时计算的数据量提高更多。

还有一种简单并行方式可以使用对角线的共同并行计算的方式，参考下图

<![endif]-->

       或者共享存储的机器。

：专门用来组装Shotgun序列数据的程序。它允许使用数据的质量（data quality的情况下。Contig）来产生数据。

       1）读入序列数据和质量数据。

2）寻找具有Word。，利用S－W－W分值，并消除完全相同的复制数据。

3）寻找并屏蔽掉Vector4）寻找接近复制的数据。

5）寻找Node－Reject。

循环6）：

6）标示出Read）

7）基于数据质量和Match（Log Likelihood Ration）分值