近似字符串匹配算法

  • Z时代
  • 2024-01-10
  • 分类：问答

在这里，我们经常需要从字符串列表中找到与其他输入字符串最接近的字符串。当前，我们正在使用Needleman-

Wunsch算法。该算法通常会返回很多错误的正数（如果我们将最小得分设置得太低），有时它在何时应该找到匹配项（当最小得分太高时），并且在大多数情况下，我们需要手工检查结果。我们认为我们应该尝试其他选择。

您对算法有经验吗？您知道算法之间的比较吗？

我真的很感谢一些建议。

PS：我们正在用C＃进行编码，但您不必在意-我是在询问一般的算法。

哦，对不起，我忘了提了。

不，我们不使用它来匹配重复数据。我们有一个我们要寻找的字符串列表-

我们称之为搜索列表。然后，我们需要处理来自各种来源的文本（例如RSS提要，网站，论坛等）-我们提取这些文本的一部分（有完整的规则集，但这无关紧要），并且需要匹配那些针对搜索列表的内容。如果字符串与搜索列表中的字符串之一匹配-

我们需要对该事物进行一些进一步的处理（这也是无关紧要的）。

我们无法执行正常的比较，因为从外部源中提取的字符串通常都包含一些多余的单词等。

无论如何，它不是用于重复检测。

回答：

好的，Needleman-Wunsch（NW）是来自生物信息学文献的经典端到端（“全局”）比对仪。很早以前在FASTA软件包中就可以将其用作“

align”和“ align0”。所不同的是，“ 0”版本在避免终止间隔方面没有偏见，这通常使得更容易支持高质量的内部匹配。我怀疑您知道，Smith-

Waterman是本地对准器，并且是BLAST的原始基础。FASTA也有自己的本地校准器，但略有不同。所有这些基本上都是启发式方法，用于估算与各个字符对的评分指标相关的Levenshtein距离（在生物信息学中，通常由Dayhoff

/“ PAM”，Henikoff＆Henikoff，

让我们对标签不那么珍贵：至少在实践中提到的Levenshtein距离基本上是编辑距离，您必须对其进行估算，因为通常无法计算出该距离，即使在有趣的特殊情况下，精确地计算也很昂贵：很快就深入到这里，因此我们有了启发性的长期良好声誉的方法。

现在是关于您自己的问题：几年前，我不得不对照已知正确的参考序列检查短DNA读数的准确性，然后我提出了一种称为“锚定比对”的方法。

这个想法是通过查找参考字符串集并通过查找给定N字符子字符串出现的所有位置来“消化”它。选择N，以使您构建的表不会太大，而且长度N的子字符串也不太常见。对于像DNA碱基这样的小字母，可以对N个字符的字符串进行完美的哈希处理，然后制作表格并将匹配项从每个bin中链接到链表中。列表条目必须标识子字符串的顺序和起始位置，该子字符串映射到它们在其列表中出现的bin。这些是要搜索的字符串列表中的“锚点”，NW对齐很有用处。

处理查询字符串时，您将从查询字符串中的某个偏移量K处开始的N个字符，对其进行哈希处理，查找其bin，如果该bin的列表为非空，则遍历所有列表记录并在记录中引用的查询字符串和搜索字符串。进行这些对齐时，您将查询字符串和搜索字符串

在 锚点 处 对齐，并提取与查询字符串长度相同且包含相同锚点K的锚点的搜索字符串子字符串。

如果选择足够长的锚点长度N和合理的偏移量K值集（它们可以分布在查询字符串中或限制为低偏移量），则应该获得可能的对齐方式的子集，并且通常会获得更清晰的赢家。通常，您将需要使用末端偏斜的，类似align0的NW对准器。

该方法试图通过限制其输入来稍微提高NW，这会提高性能，因为您进行的比对较少，而且它们通常在相似序列之间。与您的NW对准器一起做的另一件好事是允许它在出现一定数量或长度的间隙以降低成本后放弃，特别是如果您知道您不会看到或对中等质量的比赛感兴趣的话。

最终，此方法用于具有小字母的系统，其中K限制在查询字符串的前100个左右位置，并且搜索字符串比查询大得多（DNA读数约为1000个碱基，并且搜索字符串位于数量级为10000，因此我一直在寻找近似子字符串匹配项，具体取决于估算的编辑距离）。要使这种方法适应自然语言，需要仔细考虑：您会损失字母大小，但是如果查询字符串和搜索字符串的长度相似，则会有所收获。

无论哪种方式，允许同时使用来自查询字符串不同端的多个锚可能有助于进一步过滤馈给NW的数据。如果这样做，请准备将可能包含两个锚点之一的重叠字符串发送到对齐器，然后协调对齐…，或者可能进一步修改NW以强调在对齐期间使用惩罚修改在对齐时使锚大部分保持完整。算法的执行。

希望这会有所帮助或至少有趣。

以上是 近似字符串匹配算法 的全部内容， 来源链接： utcz.com/qa/411828.html

回到顶部