我们继续我们关于解决序列比对问题的旅程。
我们学习了“简单比对法”，它非常简单，包含有两个嵌套的循环。一个循环迭代可能的比对，另一个循环迭代字符比较。
接下来，我们要看一个叫作“Boyer-Moore”的算法。Boyer-Moore算法在有些方面，与简单比对算法是相似性。它还是尝试比对，对于每个比对，它都要尝试字符比较。但，可以用聪明的方法跳过许多的、不必要的比对。
Boyer-Moore算法是一个用得很广泛的算法。它已经被用了很长时间了。它真的是精确比较算法中的标杆。还有许多Boyer-Moore算法的变种，已经被人提出来。
它已经在许多不同的系统中被实施应用。很有可能，你在做网上、或在硬盘中找文件时，用的就是Boyer-Moore算法。
所以，我们深入地来看一下Boyer-Moore算法。
这里是简单算法的一个概要。我们要把模式中的“word”这个词，比对到文本中的字符上。最后，我们找到了一个不匹配的地方，模式中的“r”与文本中的“u”不匹配。所以，正常情况下， 如果我们用简单匹配算法，那么，当我们遇到错配时，我们就中断内部循环，我们会进入到外部循环的下一个迭代，在这下一个迭代中我们会试下一个比对。
但是我们现在得到了一个提示，这个提示说，下一个比对还是会匹配不上。那我们是如何知道这一点的？因为这个在文本中发生错配的“u”，在模式P中从来没有出现过，所以，任何想把模式P比对到文本上有“u”的位置，都是没有结果的。
因为在模式“P”中没有字符“u”，所以不可能有一个匹配上的结果。所以，我们知道可以跳过下2个比对。这下2个比对，还是会把P放在文本中与“u”有交叉的这个位置。所以，我们不需要试它们（这2个比对）。我们可以跳过它们，因为我们知道它们不会有匹配上的结果。
所以，我们可以把这通用化成一个适用于许多情况的规则。
事实上，我们接下来要讨论的算法，就是Boyer-Moore算法，就是把这个规则应用到最大的可能范围。
就是我们这个从字符比较中学到的规则。以跳过那些可以确证，不会带来能匹配上的结果的比对（步骤）。
在Boyer-Moore算法中，我们要知道的第一点是：在简单匹配算法中，我们是按照从左向右的顺序进行比对的；但是，（在Boyer-Moore算法中）我们要从相反的方向来比较，从右到左进行比较。
这是一个演示。比对（alignment），我们还是从左到右进行比对。
这是一个给出的比对的（例子）。对于这个例子，我们来做字符的比较。从右边开始进行比较。
在这个例子中，我们比较模式中的“d”到文本中的“d”。然后，我们向左移一步，比较模式的中“r”，发现它与文本中的“l”不匹配。
Boyer-Moore算法的下一个组成部分，叫作“坏字符规则”。这个规则说，当我们做字符比较，并且发生错配时，一旦发生错配，我们就跳过下面的比对，直到发生以下这两件事之一：要么“错配”变成了一个“匹配”，或者模式“P”完全跳过了这个错配的字符。
这是一个例子。这是一个文本“T”，和一个模式“P”。我们在这里试这个比对。这个比对是左边的第一个比对，我们要再从右向左进行字符比较。
所以，首先我们比较C和C ,找到了一个能匹配上的，然后再比较G和G，后面，我们比较T和T。然后，我们碰到了一个错配。我们比较“T”字符在这个文本里（原视频中的口误）。对不起，模式里是一个“T”，而文本里是一个“C”，是错配的。
现在问题是在这个错配变成匹配之前，我们要跳多少远。这样，这个问题就变成是我们要把P移动多少距离，然后文本中的“C”会和模式中的“C”匹配上。好，我们可以通过看“P”里面左边的情况（来得出结论）。
如果我们看P中，找下一个C，我们可以在这里找到（第2个C）。所以，我们要移动P，使错配的“C”变成匹配的，我们要移3个位置。换而言之，我们跳过了2个比对。如果我们是跳到下面第3个比对，也就是跳过了2个比对。
所以，让我们继续，跳过2个比对，让我们继续这样操作。让我们再一次用“坏字符”规则，这是我们新的比对，我们从右边开始，我们要找到与C碱基匹配的（位置）。
我们会碰到一个错配，模式里是“G”，而文本里是“A”。所以，我们再次用坏字符规则。
但是，在这个情况下，错配的字符“A”，在模式P里剩下的部分不出现。在模式P里，“A”从来没有出现过。那就意味着，我们会把模式P完全移过这个错配的字符。对。如果（模式Ｐ）左面没有“A”，那么我们完全不必把Ｐ和“A”比对。
所以，我们就要完全地移过这个错配的字符。
所以，用坏字符规则有2步，这也是用Boyer-Moore算法的规则之一。
Boyer-Moore算法的后一个组成部分，是另一个规则，它被称为“好后缀规则”。这个规则说，让“t”等于内部循环中，匹配的子字符串，所以，我们用小写的“t”来代表这个匹配上的子字符串。
在这个例子中，我们从右面开始比较字符。我们比上了“C”，然后比上了“A”，然后比上了“T”。然后，我们碰到了一个错配，模式中的“T”与文本中的“C”不匹配。所以，我们把这个子字符串叫作小“t”。
所以，我们要跳到直到模式“P”和小“t”没有错配的地方，或者直到把“P”整个移出小“t”所在的地方。
所以，你可以看到这与“坏字符”规则的相关性。坏字符规则说，当我们遇到错配时，我们移动P，直到错配变成匹配。好字符规则是针对我们能够匹配上的字符的，我们要移动P，移动的结果，是不会把匹配的，变成错配的。
所以，在这个特定的例子中，我们用“好后缀规则”。我要跳多远？
好，让我们找P中左侧的下一个小“t”，也就是“TAC”。你可以看到，这里有一个，所以，我们可以移动“Ｐ”的最短距离，就是模式“P”中的下一个“TAC”到了文本“T”中的“TAC”下面。所以，在这种情况下，我们要跳过３个比对。
我们一旦做好移动之后，这是我们新的比对，我们移动了P，这是下一个比对的位置。
我们有几个匹配的，这里有小“t”，也就是我们比对上的文本部分。
现在，我们要把“P”移多远，才没有错配？在P和小“t”之间没有新的错配，这在一开始，有点难以看出来。但是，你会在那里看到一个“P”的前缀，“CTTAC”和小“t”的一个后缀能匹配上，这里的“CTTAC”与这里的“CTTAC”能匹配上，好。当我们应该停止移动时，这也就是“好后缀规则”告诉我们要移动多远。
所以，我们就在那里跳过3个比对。所以，好后缀规则有2步。
现在，我们有2个规则，“坏字符规则”把不匹配的转到匹配的。
我们还有了好后缀规则。它试图把匹配上，保持匹配的状态，让它不要变成错配的。
-------------
高清视频地址：http://v.qq.com/page/k/p/i/k0343rok8pi.html
原视频地址：https://www.youtube.com/watch?v=4Xyhb72LCX4&index=2&list=PLMYiAoWjBNaE767PvAp8OXzZLtPMBCt5c
