我非常荣幸有这个机会站在这对着大家来讲讲我们这个组的工作。
这里边的东西主要来自我们看的这两篇文献——70年的Needleman-Wunsch和81年的Smith-Waterman的一些体会。
主要比较了一下当时一些算法方面细节的东西和现在我们后来用的一些东西的区别，，然后就在这里和大家分享一下。
可能有很多不成熟和有问题的地方，希望等我讲完以后大家再给我指出。
大概就是分为这些东西。
简单介绍一下背景；Needleman-Wunsch的global alignment；
然后讲一下它的Gap Penalty和打分的方程；然后还有关于序列比对的显著性；
后面就是Smith-Waterman的local alignment；还有这两个方法的一个比较。
首先讲一下这个背景，第一个就是我们为什么要做alignment，然后很快我们就看到这句话了。
第二个问题就是我们为什么要做序列比对呢。序列比对一个比较重要的东西就是它和无论是蛋白质还是核酸的演化过程都有非常重要的关系。
而且还可以提供保守性的信息，也可以为很多研究提供思路。
下面是为什么那电脑做， 用电脑做的原因其实很简单 手做太慢了 而且当时电脑已经在科研中开始应用了。
另外，用电脑还可以同时做多序列比对。大家有可能在NCBI上做过，长序列比对的时候，用电脑做会更有效。
而且拿那电脑做 无论谁 只要用同样的算法 而且这也是个标准化的过程，尤其是在PAM 等打分矩阵出来之后 ，这是一个标准化的东西。
这也是后来为什么基于序列分析的研究方法被广泛应用， 因为他可以重复。
下面是为什么用动态规划这个方法。
序列比对有两个特性：分解为重叠子问题和优化之后能得到最小子结构，这两个正好是符合动态规划的思路。
这个就是needle-wunsch原始文章给出来的，首先他给出来的就是一个二维的回溯矩阵。
它的横轴和纵轴都是两条氨基酸序列。
大家可能看到有一些不像氨基酸的缩写，那只是年代比较长了，因为当时氨基酸缩写的形式有点现在已经不用了。
他们使用的打分矩阵很简单，两个氨基酸一样就算作1，不一样就算作0。
这样就可以先去对矩阵进行初始化，得到表上的0和1.
也可以在当你走到每一步的时候可以查查表看看是0还是1.文章说这是最简单的方法，因为可以从这个数目可以算出最后有多少个匹配的序列。
然后根据这个，文章中给出的递归函数，之后等多填了几行之后我会解释为什么是这个公式。
它这个和高老师讲的有点不同，
比如说我现在填到了这一列，然后我怎么做呢？
然后， 我们在这一行和这一列中，所有的数都找一遍 ，找一个最大的分数.。
就是下面的这个框里，我找一个最大的，比如说这个最大的是几，是4，对吧？对。
再加上这个格本来的分 我们得到了5 。
这样的话就能保证什么？我从这开始，一个一个数过去，从右下角到左上角，当然现在是从左上角到右下角，但其实没有什么区别就是个人的一个喜好
这样就可以保证每一个数都是下面这个矩阵 的最优值，也就是最多的匹配。所以，如果我们将整个表格填满之后，
理论上就应该在这两条边上找到最优匹配，这里得到的是8。
但是你有可能在这两条边的任意位置看到它。
大家有没有发觉这个和我们上一节课讲的有什么区别。它这边没有初始化空位罚分，是不是？
下面开始回溯 现在得到了最优分值，一共是8个，它肯定是来自于下面的结果，我们就可以记录这是从哪一个数得来的。
比如说这个肯定是从7开始的。如此重复，每次我们都找最大的。如果要是有两个一样的，那么它们得分的权值是一样的。
然后从左上角一直到右下角回溯。
什么时候回溯停止呢 ？原始文章是说在回溯进行到最后一行或者最后一列时。为什么这样呢？
因为两个序列开始比对的时候从有相同的地方开始，到全部比对完成时结束。我们只要保证它在末行或者末列，它就可以找到比对上的一个区域。
其实，我感觉这里面暗含了一点局部比对的感觉，后面我会提到的。
这里介绍打分方程、打分矩阵和空位罚分的问题。
由于在70年完成的这篇文章，78年才出现PAM250，当时没有替换方程，替换矩阵的概念，尽管可能Dayhoff在69年提过一个类似的概念。
但是这篇文章里对于每一个氨基酸配对，完全一样的得一分。对于不一样的，分成几种，比较有意思的一个是根据密码子的变化来衡量。
这是由于当时已经知道了所有氨基酸都是三个密码子构成的，于是他在找这氨基酸替换有可能是什么情况。
这两个（氨基酸的）密码子，每个都有三个碱基，有可能有两个相同的，一个不同。他就认为这有可能是发生了一个mutation。
还有可能是有一个是一样的，两个是不一样的，还有可能是三个都是不一样的。
感觉三个都是不一样的发生的概率会小一些，同源性会更差一些，
有一个一样的就好一些，有两个一样的就更好，他是推荐用这种方法进行罚分的。
他当时也说了，包括一些其他的打分，例如高老师提到的一些亲水性，疏水性，酸碱性，蛋白质的位置，蛋白质序列的位置，前后位置的关系
都可以作为罚分的标准，所以说这应该是一个复杂的方程。
尽管他这里面的例子比较简单，但是在后面实际做的时候还是考虑了较多的东西。
关于空位罚分，这里面推荐的是一个线性的罚分，gap越多罚分就越多。
所以把上面的东西放到一起，就得到了Needleman-Wunsch 算法现在较为常见的一个形式。
首先初始化了两行罚分，这里是为了gap的罚分。
然后这个S（Ai,Bj）就是它的打分函数。
看上去的话，没有什么太大的区别，除了在上面加上了gap罚分的两行。
在这种状况下每次扫描相当于扫描了下面的一行和一列，但其实没有必要扫那么多。
因为那样的话具有O（n^3）的复杂度，如果是只扫下面离它最近的三个的话，则是O（n^2）的复杂度，这样做起来会节省很多的时间。
这个是一个例子。这是一个核苷酸的序列。
在没有罚分的情况下，我们看到可以得到这样一个结果。就是利用刚才提到的方法，得到是一个这样的结果。由于结果是手动填的，所以可能会有错。
然后标出了一部分（的回溯结果），因为可以看到左上角有两个8，从两个回来都是这样比较复杂的一堆路，
然后你要再把所有的路都找出来，然后在里面找一个作为最优，这其实也是很麻烦的事情。
大家可以看一下，我们其实做了一下模拟。
然后这是序列1和序列2，我把他们两个顺序互换之后，在程序里面跑出来，得到的结果是不一样的。
第一个有5个gap，第二个给了6个gap，有可能他们两个都是最优的，因为得分是一样的，但是我给他们的顺序互换之后，是不稳定的。
所以说这种情况下如果我给定一个罚分的话，就可以看到两个是一样的了。
虽然有一定的可能是这两个结果，恰好是从许多不同的路里面被选出的同一个路径。但是至少可以说明如果有罚分的话，稳定性会好一些，
然后是关于显著性的分析。
在做序列比对的时候有一个非常重要的问题，就是怎么知道得到的是具有关系，就是有关系的。说他们是可以匹配上的，就是可以匹配上的。
我要是随机找一些序列，也可以得到近似的匹配结果，或者打分都差不多的话，这怎么办呢？
所以这篇文章里给了两个评价显著性的方法。
一个是先找许多的一对一对的都是随机的序列，然后比较得到的打分，看得到的打分是一个什么分布。
然后看想要匹配的这两个序列，看得到的打分是一个怎样的一个分布
如果得到的结果和（随机得到的）分布具有显著性差异的话，那就说明我这个匹配得到的结果和随机得到的结果是不一样的。
然后另一种是用许多随机的序列去和匹配序列中的一条去比较，再把得到的分数的分布和真正想要计算的序列得到的分数进行比较。
然后去看一下，这两条序列的结果，和随机序列和其中一条序列的结果是否具有显著性差异。
然后终于到了局部比对的地方。
如果大家细心的话就会发现，这里也有多出了两个max函数以及k的限制条件。过一会会解释一下为什么回事这个样子，
这个与我们现在用的Smith-Waterman也是不一样的。
这个是摘了一个我感觉还不错的图，假如看这个图的话，会发现与（Needleman-Wunsch）的算法是一样的，
会把其同一行和同一列以及（斜对角上的）前一个以及0进行比较。“由于Smith-Waterman比较厉害的地方就是加了一个0，
将负分全部清零之后就可以得到一个（局部）最优解。
然后将上述所有值的大小（比较一下），然后将得到的最大的结果附到下面的格子中。
这样初始化一遍矩阵之后就得到了Smith-Waterman最早的方法。
然后回溯的方法其实差不多，但是有一个不同的地方，接下来会说到。
就是他以整个这个矩阵最大的地方开始，只要回溯到0，这个局部匹配就结束了。
然后其实我们发现不用将之前所有的结果都计算出来，其实对于每一个点来讲，
只要计算与其最近的三个，即（i-1，j），（i-1，j-1），（i，j-1）这三个就可以得到一个全局最优的解了。
所以说现在看到的这个就是我们现在用的Smith-Waterman算法。
然后局部匹配算法和全局匹配算法的区别。
首先就是用0来结束比对。他的错配一定具有负分的。
因为如果没有负分的话，好多东西加在一起的话，就会与之前的结果相似，产生一个比较混乱的情况，不能找到一个更直观的路径。
然后（Needleman-Wunsch）还有一些性质，比如再找一些非常保守的字串的时候是很快的，因为相当于就是从一个串匹配的算法中修改得到的。
(Smith-Waterman)还可以保证全局最优。
但是处理一些问题，例如序列有几个部分分别和上面的序列是匹配的，中间的一些部分是匹配的非常不好的，得到的结果就不太理想。
利用Smith-Waterman去处理刚才的序列就会可以看到。
Gap的数量减少了，只有5个gap，在这条序列里就只有5个gap了
而且在前面的序列里面最后还有一个gap，因为最后具有两个A，在这里面就直接停掉了，因为只要遇到数到是0的地方就停掉了。
然后这几个算法的比较做了一个比较简单的比较
如果用简化的Needleman-Wunsch算法，也可以比较出来这里面的字串。
但是加了罚分的话，就会得到一个非常乱的数。
而且如果在这里面算最大值的话，得到的是最左边的路，而不是我们认为看上去比较像的路。
而如果是用Smith-Waterman去做的话，就很明显就可以看到这条就是，而且周围没有什么干扰路径。
所以这个在局部比对的话是有一个非常好的效果。
感谢我们组的成员们，亲爱的老师们，还有感谢我们这些做出了巨大贡献的前辈们。
谢谢大家。