问预测可能的匹配以避免使用Levenshtein算法
EN

Stack Overflow用户

提问于 2015-05-23 17:14:27

回答 1查看 173关注 0票数 1

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

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

我需要尽快评估这场比赛根本不起作用

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

示例：

发布于 2015-05-23 17:25:56

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

票数 0

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/30415508

复制

相似问题

问预测可能的匹配以避免使用Levenshtein算法EN