大作业指导文档.PDFVIP

大作业指导文档 一、 问题描述 用O(m)时间复杂度找出一个长度为m 的短字符串在一个长度为n 的长字符串中的精 确匹配，nm。 二、 数据 有三个长串还有对应的三组短串集合。 每个字符串都是一段蛋白质序列，只有四类字符 最长的一个长串大小有900M，最后要求对最长的长串成功匹配即可。 三、 实现步骤 首先要实现Burrows-Wheeler transform 算法并建立FM 索引。 1. 建立BWT 结构 首先对整个字符串每次右移一位生成新的字符串，所以对于长度为n 的字符串会 生成n 个字符串。 对这n 个字符串按字典序排序，然后将第一列和最后一列取出。 需要注意的是若将字符串排序需要先创建O （n^2 ）的空间，但因为长串大小为 900M，所以不可能生成整个字符串矩阵，需要分段生成BWT，每段分别于短串做 精确匹配，再将结果合并即可。这时有可能会出现段与段衔接部分的字符串匹配 到短串的问题，所以需要段与段之间设置一定长度的重叠，重叠的长度只要大于 等于短串长度即可解决该问题。 在做字典序排序的时候我们要同时建立FM-index，也就是suffix array 。意思是我们 排好序以后的第k 个字符串是原字符串左移几位得到的，下图是个源字符串为 abraca$ 的例子，后缀数组S[i]存的是排序后第i 个字符串是源字符串左移的位数。 有了这个数组我们就可以通过匹配排序后的结果位置来定位源字符串中的位置。 比如我们在排序后的第4 个字符串的前三个字符匹配到了“aca”，那我们就可以通 过suffix array，S[3] = 3 来知道这个aca 是在源字符串的第4 个位置开始的。 2. 通过BWT 生成的第一列字符串与最后一列字符串计算辅助数据结构 （C 数组和 OCC 数组） C 数组的元素C[X]表示的意思是在字典序排序中（即第一列的字符串），比字符X 小的有多少个。C 数组可以通过遍历第一列字符串来建立。拿上图的例子来说 C[a] = 0, C[b] = 3, C[c] = 4, C[r] = 5 OCC 数组是个二维数组，它的的元素OCC[X, i]表示的意思是在最后一列字符串中， 前i 个字符里有几个字符X 。同样拿上图的例子来说以字符a 为例，因为最后一列 字符串的第一个字符是c，所以OCC[a, 1] = 0，第二个字符是a 所以OCC[a, 2] = 1， 同理OCC[a,3] = 1, OCC[a, 4] = 2, OCC[a, 5] = 3, OCC[a, 6] = 3 因为我们最后的数据集中只有四种字符，所以通过最后一列字符串建立OCC 数组 也只需要O(n)的时间。 3. 通过以上数据结构计算精确匹配 我们从这个第一列和最后一列字符串的构建方法上可以得到两个性质 第一个性质是第一列的第i 个字符和最后一列的第i 个字符在源字符串中是挨着的，并 且最后一列的第i 个字符在第一列第i 个字符前面。这样我们就可以把短串从后往前匹配， 先匹配目标串S 的最后一个字符，然后拿到最后字符的在第一列字符串中的位置之后看这 些位置的最后一列字符是否与S 的倒数第二个字符匹配 如图里所示，需要匹配的小串是aca，我们先取最后一个a，在第一列中用C 数组得到 了a 的位置范围为[1，3]，查看倒数第二个字符c 是不是在最后一列字符串[1,3] 的位置中存 在，事实发现确实有一个c，然后我们就定位到ca 这个前缀在第一列中的位置5，通过检 查该位置在最后一个字符串中的字符为a，发现确实与小串aca 完全匹配，再定位到aca 为 前缀的位置3 即可，最后通过FM-index 建立的suffix array 就可以找到aca 在源字符串的位 置了。 第二个性质是第一列字符串中的字符与最后一列字符串中的相同字符有顺序不变性， 即第一列字符串中的第二个a 与最后一列字符串中的第二个a 在源字符串中的位置相同， 即同一个a 。通过这个性质我们就可以把刚才的匹配方法中从[1,3]的区间