Динамическое искажение времени против Needleman-Wunsch_algorithm

Question

Я ищу различия между Динамическая деформация времени и Алгоритм Нидлмана-Вунша .

По сути, они оба находят счет выравнивания.Мне нужно вычислить оценку выравнивания (подобия) между короткой последовательностью строк (<20 символов), и их несколько тысяч.Я не смог выяснить различия между двумя алгоритмами и решить, какой из них выбрать для моей работы.Может кто-нибудь, пожалуйста, проясните мне различия?Благодарю.</p>

Answer 1

Оба этих алгоритма используют динамическое программирование для определения выравнивания последовательных данных. Основное различие заключается в том, как определяется оценка для i,j.
В Dynamic Time Warping стоимость (определяемая функцией 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) и алгоритмом Нидлмана-Вунша (NW) заключается в способе учета элементов последовательности в выравнивании.

Основное предположение DTW заключается в том, чтопоследовательность представляет собой «другую» версию другого в том смысле, что целевая последовательность либо растягивается (выравнивание один-ко-многим), либо уплотняется (выравнивание много-к-одному), либо не деформируется (однозначноодно выравнивание) относительно исходной последовательности.

Таким образом, DTW несовместимо с понятием промежутков , где один или несколько элементов в одной последовательности не сопоставляются никакими элементами вдругая последовательность (выравнивание один-к-одному или нет-к-одному).В отличие от этого, NW явно учитывает пропуски со штрафом, который не зависит от элементов, которые должны быть вставлены / удалены.

Если вам нужно выровнять последовательности символов, DTW подходит только в маловероятном случае, когда последовательностиявляются строго «искаженными во времени» версиями друг друга, такими как «wow» и «wwooowww».Как только одна последовательность содержит элементы, которые не могут быть истолкованы как результат растяжения другой последовательности, такие как восклицательные знаки в «wow» против «wwooowww !!!», DTW не подходит, так как вынуждает вас определять стоимостьвставки "!"с точки зрения расстояния по отношению к «ш» или «о».

Answer 3

Как насчет использования Jarowinkler для измерения сходства и Левенштейна для измерения расстояния (минимальное количество изданий)