（想看高清视频，请用文章下方的高清视频链接，在电脑上打开观看）
字幕内容
我们已经讨论过在线和离线算法的区别。离线算法预处理文本T，而在线算法不对文本T进行预处理。
我们还决定了简单精确匹配算法和Boyer-Moore算法都属于在线算法。而网页搜索引擎、和我们关注的问题，也就是测序序列比对问题，都更适合用离线算法。
所以，在我们关注的测序序列比对问题中，我们有了大量的测序序列。我们想找出，这些序列在一个长的参考基因组中，最匹配的地方。
我们确定，我们需要用离线解决方案，因为参考基因组不会随实验而改变，但是测序得到的序列总是在变。
因此，预处理文本T，也就是参考基因组，就变得很合理。因此，我们将预处理文本T，而T是很长的。
要了解我们如何做的，我们可以用几个类比来进行说明。
所以，我们可以把文本当作是一本书。常用的预处理一本书的方法，就是给它编制索引。所以，这是从一本书中摘录的索引。一个索引，基本上都是关键术语的列表。每个关键术语都与一系列页码相关联，这在个书的第几页，这个术语被提到。
所以，当我们试图找到更多的信息，例如：要找“memory”这个词。这里我们可以在索引中查找“memory"这个词，这是非常方便的。因为索引是按字母表的顺序排列的。然后索引告诉我们哪些页面，可以找到更多有关“momery”的信息。这是很方便。这相比对于扫描整本书来说，显然是更方便的方法。以找到“memory”这个词在书中出现的地方。因此，查找一个关键术语，例如在这里找到“momery”这个词。
在索引中，我称之为“查寻”索引。所以，当我们脑子里有一个关键词、或一个关键术语。我们想知道，在一本书中，这个关键术语出现在哪里，我们称之为“查询”。
这里有另一个类比。当你去杂货店买一些牛奶，你不必看杂货店里的每一个货架，最后你才找到你要的牛奶。你知道，牛奶是与其他乳制品放在一起的，因为杂货店就是这样组织货品的。它们按照相关项目，被组织在一起。像奶制品、或者纸制品这样的东西，（会被分别按组别，被组织在一起）。所以在杂货店里，很容易找到一类项目（的货品）。但是，（杂货店里的）项目并不是按照字母顺序排列，或按基它类似顺序排列。因为，杂化店是分组进行排列的，一个项目（的货品）是组织在一起的。
所以这两个例子，突出了我们有两个不同的基本工具，用来组织数据的工具。有了这样的工具，我们很容易找到我们想要的项目了。
这样，就很容易查询。或者，就像书按照字母排序做索引那样，进行排序；或者进行分组，如杂货店把货品按组别，安排到各个（货品种类）走廊那样分组。
现在，让我们为一个DNA字符串建立一个索引。我们构建的这个索引，将更像是一本书的索引，我们将使用排序的想法（来组织索引）。
这是我们的文本T。我们把我们的索引，放在中间这个橙色的方块中。和我们书的索引不一样，基因组不是由词来组成的。在这个意义上，它不像一本书。它只是一个大的、长的字符串。所以，我们必须把它分解成单词。
一种操作方法是，在文本T中，取得每一个具有一定长度子字符串。我们将每个子字符作为一个词。在这个例子中，我们取长度为5的子字符串。
并将取得的子字符串放入我们的索引，让我们取第一个5字符的子字符串，就象为书做索引一样，我们把子字符串插入到索引中。
我们的索引就在这里。它是一个把：子字符串、和子字符串在文本中的偏移值，进行关联（的列表）。所以，对于这个长度为5的第一个子字符串，我们关联它的偏移值“0”。
OK。让我们做第二个长度为5的子字符串。好，同样。现在做第三个，再第四个。关于子字符串，有一个有趣的事情，比如这第4个子字符串，第5个也是。
按字母顺序，它排在两个已经被索引好的子字符串之间，所以我们必须把它（3）按顺序插在它们（0，1）之间。以保持总体顺序，是按字母顺序排列的。OK。现在让我们添加下一个长度为5的子字符串。现在这个子字符串是我们之前见过的。
所以不是在索引中添加新条目，而是简单地给这个偏移增加一个新的偏移值。在这个子字符串已有的偏移值之后，再新加一个偏移值。所以我们在“0”的列表后面，加上一个“4”。
然后我们继续这样做，直到我们添加好所有的长度为5的子字符的偏移值串为止。这样。这就是我们的索引。
它非常象一本书的索引。除了，我们构建的是长度为5的所有子字符串的索引（这一点与书略有不同）。
所以借用一个词汇，我们使用术语“K-mer”来指代长度为“K”的子字符串。因此，对于长度为“5”的子字符串，我们会说“5-mer”。
所以这个索引，是建立在“5-mer”的基础之上的。并插入到索引中，以便对每个5-mer，都能够定位到基因组，确定它的偏移值。我们将之称为“5-mer索引”。
好的，我们现在有了索引。我们如何查询这个索引？
我们有一个模式字符串P，我们要解决精确匹配的问题。我们要在5-mer索引的帮助下，找到P出现位置的偏移值。
我们这样做，让我们取P的第一个5-mer，拿它来查询索引。
我们问索引，你在哪里看到过这个5-mer？索引回复说：在偏移值为3的位置看到过它。所以我们知道中，P的前5个字符，能匹配到从T的第3个字符开始的5个字符。
但我们还没有完成这个比对，因为我们不知道，P的其余部分是否能匹配到T上。我们必须在这里多做一个字符比较，我们把这个额外工作称为验证。我们在文本中，击中了5-mer出现的索引位置。这是第一步。但随后这个额外的工作，我们必须做，以确定P和T是完全匹配的。这就是我们所说的“验证”。
在这个例子中，验证成功，因为P中的“C”能匹配到T中“C”。因此，总体上我们可以得出结论：P出现在T中，在偏移值为3的位置。
这是一个变化。如果不是从P中取第一个5-mer，而是采取第二个5-mer。在某种意义上说，这并不重要，因为索引包含了所有来自T的5-mer。因此，无论我们用P的第一个5-mer，还是第二个5-mer，都应该能正常工作。他们两者，都会在T内找到P的匹配位置
我们继续，从P取第二个5-mer，并查询索引。这次，我们的5-mer在文本“T”中出现两次。一次偏移0，另一次偏移4。所以，我们必须做两个不同的验证。因此，让我们从偏移为0的，开始验证。
好。我们的验证在这里失败，因为T的左边没有字符。P左边有一个字符，而T的左边没有字符，T的偏移量为0（已顶到最左边）。所以，在这里，P不可能与T匹配上。所以，现在让我们尝试偏移值为4。在我们的验证中，我们要检查这个P开头的这个“G”能否匹配到T上的“G”。它能匹配上。这说明，使用该模式时，用哪个5-mer并不重要。它们中的任何一个，都会引导出正确的P和T匹配的偏移值。这里，我们再次找到同样的匹配，匹配的偏移值是3。
这里是一个修改后的例子。这就像前面的例子，但是我们在P中做了一个替换。这里的最后一个碱基，现在改成“A”。
所以，因为这个变化，P不再与T匹配。但是，但让我们走一遍我们这个过程。让我们拿第一个5-mer，我们将查询索引，我们看到5-mer击中在偏移量为3的这个地方。
然后，我们要去验证。我们做这个字符比较。我们比较这个“A”和这个“C”。我们发现P与T不匹配。这很好。这是正确的答案。在这种情况下，P与T不匹配。
现在，这里是另一个修改后的例子。这次，我们把这个字符修改为“A”。这是我们做的改变。所以，再一次，模式不出现在文本“T”中。事实上，在这种情况下，我们可以更快放弃更快。我们可以更快注意到这一点。因为在这种情况下，我们从P取得的第一个5-mer，甚至不在索引中。所以，如果一个我们要查询的字符串P的5-mer子字符串不出现在文本中，那么整个字符串就不可能与文本匹配。所以，我们可以在这一时点就放弃。
所以，我就用一个专用词汇来描述。当我们使用索引，可以确定在P内有5-mer。这只是一个提示，我们应该在那个特定地区更加努力。这称为“击中索引”，对于索引报告的每个偏移量，称为“击中索引”。
所以，例子中用P的第二个5-mer进行查询，得到2个击中，偏移值为0和4。
所以当P在T内有匹配时，我们会称之为“匹配”或“发生”。但是索引“命中”可以对应于“匹配”，也可以不对应于“匹配”。
“击中”只是一个提示，提示我们应该在那个特定的地方，更加努力地进行比对。
并非所有的索引“击中”都会得到“匹配”。
---------------------------------------------------------------
高清视频链接：http://v.qq.com/x/page/r0345a5fkwm.html
原视频链接：https://www.youtube.com/watch?v=2UsmUgJtwAI&t=334s&list=PLMYiAoWjBNaE767PvAp8OXzZLtPMBCt5c&index=4