c++ - 预测可能的匹配以避免使用 Levenshtein 算法

Question

我的问题是，我必须扫描具有给定最大替换、插入和删除数量的 DNA 序列。

为此，我已经能够修改 Levenshtein 算法来确定这一点，即从序列中的每个字符开始。但这是减慢速度的方法，我想知道是否有一种方法可以预测每个字符都不可能匹配，这样我就可以避免使用 Levenshtein 算法并跳到序列中的下一个字符。

我需要尽快评估这个匹配根本行不通

当我在每个序列中一个字符一个字符地迭代时，这是否可能或是否有另一种方法来处理这个问题？

例子:

• 模式:ATTATACA[1,1,1]
• 序列:ATCGCACBTTATACATTATACAATCGCACBTTATACATTATACA

Answer 1

对于单一模式，有 Knuth-Morris-Prat 算法。当然这取决于数据，但它是最快的算法。对于多模式，有 Aho-Corasick 算法。您可以使用 php @codeplex.com (phpahocorasick) 尝试我的实现。它还允许使用通配符。