关于Smith-Waterman算法的问题

我正在使用Smith-Waterman算法运行一些字符串匹配测试。我目前使用SimMetrics（Java开源项目）来运行测试。关于Smith-Waterman算法的问题

任何人都可以解释为什么当我比较'Bloggs J.'到'Bloggs'我得到1.0的相似度值？

显然存在差距（例如'o'和'。'），但似乎没有受到惩罚。

预先感谢您。

来源

2010-07-04 Gia

这是关于算法本身的问题（即，你确信你的实现没有错误，但你不明白为什么算法输出这个特定的结果），或关于你的实现（你怀疑是不稳定的并因此给出错误的结果）？ – stakx 2010-07-04 16:25:51

我不是100％确定实施是正确的，但我认为可能。我想知道是否有人能解释预期结果是什么，为什么。 – Gia 2010-07-04 16:27:28

尝试applet：http：//baba.sourceforge.net/ – tur1ng 2010-07-04 16:49:43

Smith-Waterman Algorithm是本地比对算法。这意味着它的设计旨在对齐件的字符串很好地对齐，而不是对齐整个字符串。你所说的“差距”不应该作为差距来处罚，因为它被认为发生在对齐的区域之外。 'Bloggs'的长度没有字符串可能更好地对齐'Bloggs J.'。比'Bloggs'的确如此。如果您想要全局对齐，则应该使用Needleman-Wunsch Algorithm。

来源

2010-07-05 17:11:38 dsimcha

正确。请参阅此博客文章，以获取Smith-Waterman的概述，以及有关Needleman-Wunsch实现方式的更多详细信息：http：//www.etherealbits.com/2013/04/string-alignment-dynamic-programming-dna/。 – Tyson 2013-04-29 17:31:47

关于Smith-Waterman算法的问题

回答

相关问题