Мне интересно, как вы можете количественно оценить результаты алгоритма Needleman-Wunsch (обычно используется для выравнивания последовательностей нуклеотидов/белков).Как алгоритм Needleman Wunsch сравнивается с грубой силой?
Рассмотрим некоторую фиксированную схему подсчета и две последовательности различной длины S1
и S2
. Скажем, мы вычисляем все возможные выравнивания S1
и S2
с помощью грубой силы, а наивысшее выравнивание очков имеет оценку x
. И, конечно же, это значительно сложнее, чем подход Needleman-Wunsch.
При использовании алгоритма Needleman-Wunsch, чтобы найти выравнивание последовательности, скажем, что он имеет оценку y
.
Рассмотрите r
как результат, полученный через Needleman-Wunsch для двух случайных последовательностей R1
и R2
.
Как x
по сравнению с y
? y
всегда больше r
для двух последовательностей известных гомологий?
В общем, я понимаю, что мы используем алгоритм Needleman-Wunsch для значительного ускорения выравнивания последовательностей (по сравнению с подходом с грубой силой), но не понимаем стоимости в точности (если есть), которая поставляется с ней , Я прочитал оригинальную бумагу (Needleman & Wunsch, 1970), но я все еще остаюсь с этим вопросом.
Алгоритм, который может вернуть неоптимальный результат для улучшения производительности, называется * heruistic * (https://en.wikipedia.org/wiki/Heuristic). Needleman-Wunsch возвращает * оптимальный * результат и, следовательно, не является herusitic (https://en.wikipedia.org/wiki/Needleman%E2%80%93Wunsch_algorithm). – RBarryYoung