Approximate string matching algorithms在这里，我们经常需要从字符串列表中找到与其他输入字符串最接近的字符串。当前，我们正在使用Needleman-Wunsch算法。该算法通常会返回很多假阳性(如果我们将最小得分设置得太低)，有时它在应有的时候(最小得分太高时)找不到匹配项，并且在大多数情况下，我们需要手工检查结果。我们认为我们应该尝试其他选择。
您对算法有经验吗？ 我真的很感谢一些建议。 PS：我们正在用C＃进行编码，但您不必在意-我是在询问一般的算法。 哦，对不起，我忘了提了。 不，我们不使用它来匹配重复数据。我们有一个我们要寻找的字符串列表-我们称之为搜索列表。然后，我们需要处理来自各种来源的文本(例如RSS feed，网站，论坛等)-我们提取这些文本的一部分(有完整的规则集，但这是不相关的)，我们需要匹配那些反对搜索列表。如果字符串与搜索列表中的字符串之一匹配-我们需要对该事物进行一些进一步的处理(这也无关紧要)。 我们无法执行常规比较，因为从外部源中提取的字符串通常都包含一些多余的单词等。 无论如何，它不是用于重复检测。 好的，Needleman-Wunsch(NW)是来自生物信息学文献的经典端到端("全局")比对仪。很早以前在FASTA软件包中就可以将其用作" align"和" align0"。所不同的是，" 0"版本在避免终止间隙方面没有偏见，这通常使更容易支持高质量的内部匹配。我怀疑您知道，史密斯·沃特曼(Smith-Waterman)是本地对准器，并且是BLAST的原始基础。 FASTA也有自己的本地校准器，但略有不同。所有这些本质上都是启发式方法，用于估计与各个字符对的得分度量相关的莱文施泰因距离(在生物信息学中，通常由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以强调在对齐期间使用惩罚修改来使锚点在大多数情况下保持完好无损。算法的执行。 希望这会有所帮助或至少有趣。 好。 与Levenstein距离有关：您可能希望通过将结果除以较长字符串的长度来对其进行归一化，以便始终获得0到1之间的数字，以便可以比较有意义的字符串对的距离方式(例如，表达式L(A，B)> L(A，C)是没有意义的，除非您对距离进行归一化)。
要查看的其他算法是agrep(agrep上的Wikipedia条目)， 我们正在使用Levenshtein距离方法来检查数据库中是否有重复的客户。效果很好。 为了最大程度地减少由于拼写的细微变化或错误而导致的不匹配，我使用了Metaphone算法，然后使用Metaphone编码上的Levenshtein距离(以百分比匹配的比例缩放为0-100)来衡量接近程度。这似乎效果很好。 将FM索引用于回溯，类似于Bowtie模糊对齐器中的FM索引 为了扩展Cd-MaN的答案，听起来您正在面临标准化问题。如何处理长度不同的比对之间的分数并不明显。 给定您感兴趣的内容，您可能希望获得用于对齐的p值。如果您使用Needleman-Wunsch，则可以使用Karlin-Altschul统计信息获得这些p值http://www.ncbi.nlm.nih.gov/BLAST/tutorial/Altschul-1.html BLAST将可以进行局部比对并使用这些统计信息对其进行评估。如果您担心速度，这将是一个很好的工具。 另一种选择是使用HMMER。 HMMER使用Profile Hidden Markov模型来比对序列。我个人认为这是一种更强大的方法，因为它还提供了位置信息。 http://hmmer.janelia.org/ |
