SMITH WATERMAN算法
<span style="color: #003366; font-family: arial, helvetica, verdana, sans-serif;">1.1 序列相似性比较生物信息学中，对各种生物大分子序列进行分析是一件非常基本的工作。从序列的片段测定，拼接，基因的表达分析，到RNA和蛋白质的结构功能预测，物种亲缘树的构建都需要进行生物分子序列相似性的比较。在遗传物质长期的演化过程中，原本相同的DNA序列由于其中一条序列缺失了几个片断，或增加了几个片断，或某段子序列发生了位置的变化等，从而导致他们发生了不同，这两条序列不一定能进行精确的匹配，但是他们有一定的相似度。我们应该如何判定序列之间的这种相似性？对于这种情况，生物学家提出了一种用来评定序列相似性的方法，称为记分函数的方法。
定义1：如果http://www.bioinfo.org.cn/figs.files/Image1.gif是一个序列，那么http://www.bioinfo.org.cn/figs.files/Image2.gif表示http://www.bioinfo.org.cn/figs.files/Image1.gif中的字符长度，http://www.bioinfo.org.cn/figs.files/Image3a.gif表示序列的第http://www.bioinfo.org.cn/figs.files/Image4.gif个字符。如果序列http://www.bioinfo.org.cn/figs.files/Image1.gif和序列http://www.bioinfo.org.cn/figs.files/Image5.gif相同，必须满足如下条件：
（1）、http://www.bioinfo.org.cn/figs.files/Image6.gif；
（2）、http://www.bioinfo.org.cn/figs.files/Image7.gif；
定义2：如果http://www.bioinfo.org.cn/figs.files/Image8a.gif和http://www.bioinfo.org.cn/figs.files/Image9.gif是两个字符，那么http://www.bioinfo.org.cn/figs.files/Image10.gif表示http://www.bioinfo.org.cn/figs.files/Image8a.gif和http://www.bioinfo.org.cn/figs.files/Image9.gif字符在进行比较时所得的分值，http://www.bioinfo.org.cn/figs.files/Image11.gif称为一个记分函数，记分函数还包括当http://www.bioinfo.org.cn/figs.files/Image8a.gif为空字符或http://www.bioinfo.org.cn/figs.files/Image9.gif为空字符的情况，在序列中一个所谓的空字符表示序列中空字符的位置可能缺失一个未知的字符，我们只能使用空字符来表示这种缺失；
定义3：如果http://www.bioinfo.org.cn/figs.files/Image1.gif和http://www.bioinfo.org.cn/figs.files/Image5.gif是两个序列，那么http://www.bioinfo.org.cn/figs.files/Image12a.gif的一个相似性比较http://www.bioinfo.org.cn/figs.files/Image13.gif可以用http://www.bioinfo.org.cn/figs.files/Image14.gif和http://www.bioinfo.org.cn/figs.files/Image15.gif来表示，其中：
（1）、http://www.bioinfo.org.cn/figs.files/Image16.gif；
（2）、将http://www.bioinfo.org.cn/figs.files/Image17.gif和http://www.bioinfo.org.cn/figs.files/Image18.gif中的空字符除去后所得的序列分别和http://www.bioinfo.org.cn/figs.files/Image1.gif、http://www.bioinfo.org.cn/figs.files/Image5.gif相同；
相似性比较http://www.bioinfo.org.cn/figs.files/Image13.gif就是http://www.bioinfo.org.cn/figs.files/Image17.gif和http://www.bioinfo.org.cn/figs.files/Image18.gif中字符一一比对，相似性比较http://www.bioinfo.org.cn/figs.files/Image13.gif的得分http://www.bioinfo.org.cn/figs.files/Image19.gif可以用如下公式表示：
http://www.bioinfo.org.cn/figs.files/Image20.gif；
其中http://www.bioinfo.org.cn/figs.files/Image21.gif；
定义4：对于两个序列http://www.bioinfo.org.cn/figs.files/Image1.gif和http://www.bioinfo.org.cn/figs.files/Image5.gif，它们的最优相似性比较http://www.bioinfo.org.cn/figs.files/Image13.gif是指在http://www.bioinfo.org.cn/figs.files/Image1.gif和http://www.bioinfo.org.cn/figs.files/Image5.gif的所有相似性比较中得分最高的一个，序列相似性比较算法的主要目标就是如何寻找出序列间的最优相似性比较。
http://www.bioinfo.org.cn/figs.files/Image1.gif
http://www.bioinfo.org.cn/figs.files/Image5.gif
1
2
i-1
I
1
http://www.bioinfo.org.cn/figs.files/Image34.gif
http://www.bioinfo.org.cn/figs.files/Image35.gif
2
http://www.bioinfo.org.cn/figs.files/Image36.gif
http://www.bioinfo.org.cn/figs.files/Image37.gif
j-1
http://www.bioinfo.org.cn/figs.files/Image38.gif
http://www.bioinfo.org.cn/figs.files/Image39.gif
J
http://www.bioinfo.org.cn/figs.files/Image40.gif
http://www.bioinfo.org.cn/figs.files/Image41.gif
1.2 Smith Waterman算法
在寻找序列最优相似比较的算法中有两种算法使用最为广泛：Blast算法和Smith Waterman算法，Blast算法的运行速度要比Smith Waterman算法快，但是Smith Waterman算法要比BLAST算法更为精确。Smith Waterman算法先用迭代方法计算出两个序列的所有可能相似性比较的分值，然后通过动态规划的方法回溯寻找最优相似性比较。
Smith Waterman算法的具体描述如下：
对于两个序列http://www.bioinfo.org.cn/figs.files/Image1.gif和http://www.bioinfo.org.cn/figs.files/Image5.gif，http://www.bioinfo.org.cn/figs.files/Image22.gif和http://www.bioinfo.org.cn/figs.files/Image23.gif，其中http://www.bioinfo.org.cn/figs.files/Image24.gif，都属于某个字符集http://www.bioinfo.org.cn/figs.files/Image25.gif，对http://www.bioinfo.org.cn/figs.files/Image26.gif中的任何元素和空符号，他们两两之间都有一个记分值，用记分函数http://www.bioinfo.org.cn/figs.files/Image10.gif表示，http://www.bioinfo.org.cn/figs.files/Image27.gif表示序列http://www.bioinfo.org.cn/figs.files/Image1.gif的前缀http://www.bioinfo.org.cn/figs.files/Image28.gif和序列http://www.bioinfo.org.cn/figs.files/Image5.gif的前缀http://www.bioinfo.org.cn/figs.files/Image29.gif之间的最优相似性比较的得分。那么有如下公式：
http://www.bioinfo.org.cn/figs.files/Image30.gif\
通过公式我们可以得到如下的一个得分矩阵http://www.bioinfo.org.cn/figs.files/Image31.gif：
通过得分矩阵进行动态规划回溯法获得相似性比较的算法如下：
http://www.bioinfo.org.cn/figs.files/Image32.gif
http://www.bioinfo.org.cn/figs.files/Image33.gif
http://www.bioinfo.org.cn/figs.files/Image42.gif
http://www.bioinfo.org.cn/figs.files/Image43.gif
http://www.bioinfo.org.cn/figs.files/Image44.gif
http://www.bioinfo.org.cn/figs.files/Image45.gif
http://www.bioinfo.org.cn/figs.files/Image46.gif
http://www.bioinfo.org.cn/figs.files/Image47.gif
其中http://www.bioinfo.org.cn/figs.files/Image48.gif函数表示在一个序列b的第c个位置插入一个字符a
Smith Waterman算法中，假设http://www.bioinfo.org.cn/figs.files/Image49.gif,http://www.bioinfo.org.cn/figs.files/Image50.gif, 在开始计算得分矩阵http://www.bioinfo.org.cn/figs.files/Image31.gif时需要计算矩阵的每一个得分值，计算复杂度为http://www.bioinfo.org.cn/figs.files/Image51.gif。从上面的回溯算法中可以看到，第二步回溯算法的计算复杂度为http://www.bioinfo.org.cn/figs.files/Image52.gif。这样Smith Waterman算法的整体时间复杂度为http://www.bioinfo.org.cn/figs.files/Image53.gif。使用Smith Waterman算法计算两个序列最大相似性比较时绝大部分计算时间将消耗在计算得分矩阵上http://www.bioinfo.org.cn/figs.files/Image31.gif。
的值。当http://www.bioinfo.org.cn/figs.files/Image54.gif，http://www.bioinfo.org.cn/figs.files/Image55.gif和http://www.bioinfo.org.cn/figs.files/Image56.gif已经计算出来后，我们称http://www.bioinfo.org.cn/figs.files/Image57.gif是可计算的。如下图所示：
<span style="font-size: small;"> at g c 0 1 2 3 ->a1 0 1-> t2 1 -> g 3 -> c ->
页:
[1]