c - 是否可以允许 KMP 算法不匹配？

Question

我正在寻找一种有效的算法，以在将 pattern 与文本进行比较时允许不匹配(最多 3 个)。原始 KMP 在我的数据上有效地完成了这项工作，但正在考虑扩展该算法以适应不匹配情况。

对于我的情况:GACCCT 被认为与 GGGGGAGGTTTTTTT 在第二个序列中的起始位置为 4

我需要在两个文件之间进行成对比较。每个包含大约 500,000 个序列。一个文件中的序列相对较短(~50 个碱基)，而另一个文件中的序列较长(~200)

我尝试了 Python 中的 Regex 包、Levenshtein 算法和编辑距离。但是它们很慢，我将不得不等待几周才能完成工作。

Answer 1

我认为你的数据不是太大，所以也许这会起作用:
我认为你应该创建一个 suffix tree为您的数据。完成此操作后，查找子字符串将非常容易，无论您是否要计算不匹配:您只需遍历包含要查找的字符的树，直到找到子字符串或命中最多的字符您可以容忍的不匹配。