python机器学习-乳腺癌细胞挖掘（博主亲自录制视频）https://study.163.com/course/introduction.htm?courseId=1005269003&utm_campaign=commission&utm_source=cp-400000000398149&utm_medium=share
http://www.360doc.com/content/14/0106/00/14641369_342933143.shtml参考
史密斯-沃特曼算法（Smith-Waterman algorithm）是一种进行局部序列比对（相对于全局比对）的算法，用于找出两个核苷酸序列或蛋白质序列之间的相似区域。该算法的目的不是进行全序列的比对，而是找出两个序列中具有高相似度的片段。
该算法由坦普尔·史密斯（Temple F. Smith）和迈克尔·沃特曼（Michael S. Waterman）于1981年提出。史密斯-沃特曼算法是尼德曼-翁施算法的一个变体，二者都是动态规划算法。这一算法的优势在于可以在给定的打分方法下找出两个序列的最优的局部比对（打分方法使用了置换矩阵和空位罚分）。该算法和尼德曼-翁施算法的主要区别在于该算法不存在负分（负分被替换为零），因此局部比对成为可能。回溯从分数最高的矩阵元素开始，直到遇到分数为零的元素停止。分数最高的局部比对结果在此过程中产生。在实际运用中，人们通常使用该算法的优化版本
生物学上一个基本问题是，一个基因或者蛋白是否和别的基因或者蛋白存在联系。蛋白质在序列层次的关联暗示了其同源性，同时暗示了它们可能有类似的功能。通过分析多个DNA或者蛋白质序列，我们可能会发现一些保守序列和区域。这种基因序列或者蛋白质序列之间关联性的分析就是通过序列比对来完成的。如今，人们完成了许多不同生物体的基因组分析，获得了大量的基因和蛋白质序列数据。序列比对能够向我们揭示某一生物体中蛋白质之间的关联以及蛋白质在不同生物体中的关联，从而进一步理解生命和进化。
序列比对起源于1970年。Saul B. Needleman和Christian D. Wunsch于1970提出了一个启发式的同源算法，称为尼德曼-翁施（Needleman-Wunsch）算法。该算法使用迭代的方法计算出一个矩阵，从而达到全局比对的效果。一些其他的启发式分析方法也在70年代被提出。Sankoff，Reichert，Beyer等人提出了一些严谨的数学的算法用来分析序列。然而这些方法通常难以揭示序列的生物学意义。 Sellers提出了一套测量序列距离的方法。沃特曼等于1976年在该方法的基础上，增加了插入和删除任意长度片段的方法。该方法解决了如何用最小的基因突变的次数将一个序列转变成另一个序列的问题。之后，坦普尔·史密斯和迈克尔·沃特曼于1981年提出了史密斯-沃特曼算法，解决了局部比对问题。
史密斯-沃特曼算法通过字母的匹配，删除和插入操作，把两条序列进行排列。实际上插入和删除都是引入空位的操作（在不同序列上）。序列1上某一位置的插入相当于在序列2上对应位置的删除。在实际计算中，只需要考虑何时引入空位即可。
该算法主要分两步，计算得分矩阵和寻找最优比对序列。可以简单描述为：
-
确定置换矩阵及空位罚分方法。置换矩阵赋予每一碱基对或残基对匹配或错配的分数，相同或类似则赋予正值，不同或不相似赋予0分或者负分。空位罚分决定了引入或延长空位的分值。研究者应当根据比对的目的选择合适的置换矩阵及空位罚分。另外通过比较不同的置换矩阵及空位罚分的组合所带来的比对结果也可以帮助研究者进行选择。
-
初始化得分矩阵。得分矩阵的长度和宽度分别为两序列的长度+1。其首行和首列所有元素均设为0。额外的首行和首列得以让一序列从另一序列的任意位置开始进行比对，分值为零使其不受罚分。
-
打分。对得分矩阵的每一元素进行从左到右、从上到下的打分，考虑匹配或错配（对角线得分），引入空位（水平或垂直得分）分别带来的结果，取最高值作为该元素的分值。如果分值低于0，则该元素分值为0。打分的同时记录下每一个分数的来源用来回溯。
-
回溯。通过动态规划的方法，从得分矩阵的最大分值的元素开始回溯直至分数为0的元素。具有局部最高相似性的片段在此过程中产生。具有第二高相似性的片段可以通过从最高相似性回溯过程之外的最高分位置开始回溯，即完成首次回溯之后，从首次回溯区域之外的最高分元素开始回溯，以得到第二个局部相似片段。
与尼德曼-翁施算法的比较
史密斯-沃特曼算法为局部比对算法，用于找出两序列中最相似的区域。尼德曼-翁施算法为全局比对算法，用于完整匹配两个序列。这两种算法的目不同，因此研究者在选择算法时要根据实际需求来决定。
两种算法都使用了置换矩阵，空位罚分，得分矩阵，以及回溯的方法，具有一定的相似度。然而，史密斯-沃特曼算法与尼德曼-翁施算法的三个主要区别在于：
| 史密斯-沃特曼算法 | 尼德曼-翁施算法 | |
|---|---|---|
| 初始化阶段 | 第一行和第一列全填充为 0 | 首行和首列需要考虑空位罚分 |
| 打分阶段 | 若得分为负，则分数为零 | 得分可以为负 |
| 回溯阶段 | 从最高分开始，回溯直至得分为 0 | 从右下角开始，回溯至左上角 |
其中，打分阶段分数不为负是非常重要的一点区别。它使得对序列局部的比对成为可能。当任何位置分数低于0，即表示此前的序列不具有相似性；而此时将此元素分数设为0，即达到了“重设”的效果，使得从此位置开始的比对不受之前位置的影响。初始化阶段的区别使得史密斯-沃特曼算法中从一序列任意位置开始匹配另一序列不受罚分，而尼德曼-翁施算法因为要匹配完整的序列，所以两端的空位也需要罚分
https://study.163.com/provider/400000000398149/index.htm?share=2&shareId=400000000398149（博主视频教学主页）
