动态时间扭曲与Needleman-Wunsch_algorithm

Question

我正在寻找动态时间扭曲和Needleman-Wunsch算法之间的差异.

基本上,他们都找到了对齐分数.我需要计算短序列(<20个字符)之间的对齐(相似性)得分,并且有几千个.我无法弄清楚两种算法之间的差异,并决定选择哪一种算法.有人可以清楚我的差异吗？谢谢.

Answer 1

这两种算法都使用动态编程来确定顺序数据的对齐.这里的主要区别在于如何i,j确定得分.
在动态时间规整,成本(由函数确定的i, j)加入到该组的最小值(i-1, j),(i-1, j-1),(j, i-1).

在NW,最大的组(i-1, j) + weight,(i-1, j-1) + S(Ai, Bi),(j, i-1) + weight取,使得S(A, B)由一个查找表,该相似性矩阵来确定.

如果您想通过可枚举空间进行对齐并且可以创建相似性矩阵(例如蛋白质序列或单词),请使用NW,但是,如果您要对齐数据而不能建立相似性矩阵(如时间序列),需要使用一个功能,配合DTW.

对齐可能是一件棘手的事情,您可能需要调整参数才能使事情正确.

祝好运.

Answer 2

动态时间规整 (DTW) 和 Needleman-Wunsch 算法 (NW) 之间的根本区别在于比对中考虑序列元素的方式。

DTW 的基本假设是一个序列是另一个序列的“时间扭曲”版本，从某种意义上说，目标序列要么被拉伸（一对多对齐），要么被压缩（多对一对齐），或相对于源序列非扭曲（一对一对齐）。

因此，DTW 与间隙的概念不兼容，其中一个序列中的一个或多个元素不与另一序列中的任何元素匹配（一对一或非一对一比对）。相比之下，NW 明确地用惩罚来解释间隙，该惩罚不是要插入/删除的元素的函数。

如果您需要对齐字符序列，DTW 仅适用于序列彼此严格“时间扭曲”版本的不太可能的情况，例如“wow”和“wwooowww”。一旦一个序列包含不能被解释为拉伸另一个序列的结果的元素，例如“wow”与“wwooowww！！！”中的感叹号，DTW 就不合适，因为它迫使您定义成本插入一个“！” 就相对于“w”或“o”的距离而言。