3

Мне интересно, как вы можете количественно оценить результаты алгоритма 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), но я все еще остаюсь с этим вопросом.

+0

Алгоритм, который может вернуть неоптимальный результат для улучшения производительности, называется * heruistic * (https://en.wikipedia.org/wiki/Heuristic). Needleman-Wunsch возвращает * оптимальный * результат и, следовательно, не является herusitic (https://en.wikipedia.org/wiki/Needleman%E2%80%93Wunsch_algorithm). – RBarryYoung

ответ

5

Needlman-Wunsch всегда дает оптимальный ответ - он намного быстрее, чем грубая сила, и не жертвует точностью в процессе. Ключевое понимание, которое он использует, состоит в том, что на самом деле нет необходимости генерировать все возможные выравнивания, поскольку большинство из них содержат плохие подвыборы и не могут быть оптимальными. Алгоритм Needleman-Wunsch работает, вместо этого медленно создавая оптимальные выравнивания для фрагментов исходных прядей, а затем медленно увеличивая эти меньшие выравнивания в более крупные выравнивания, используя гарантию того, что любое оптимальное выравнивание должно содержать оптимальное выравнивание для немного меньшего размера.

2

Я думаю, что ваш вопрос сводится к тому, что динамическое программирование находит оптимальное решение, то есть гарантирует, что y >= x. Для обсуждения этого я хотел бы сослаться на людей, которые, вероятно, умнее меня:

https://cs.stackexchange.com/questions/23599/how-is-dynamic-programming-different-from-brute-force

В основном, это говорит, что динамическое программирование, вероятно, производить оптимальный результат т.е. такой же, как грубая сила, но только для конкретных задач которые удовлетворяют принципу оптимальности Беллмана .

Согласно Википедии странице для Needleman-Wunsch, проблема действительно удовлетворяет принцип Беллмана оптимальности:

https://en.wikipedia.org/wiki/Needleman%E2%80%93Wunsch_algorithm

В частности:

Алгоритм Needleman-Wunsch все еще широко используется для оптимального глобального выравнивания , особенно если качество глобального выравнивания имеет значение .Однако алгоритм дорог с относительно времени и пространства, пропорциональный произведению длины двух последовательностей и, следовательно, не подходит для длинных последовательностей.

Существует также упоминание оптимальности в другом месте на той же странице в Википедии.

+0

Эй, спасибо за ваш ответ. Хотя он не отвечает на вопрос, который я задал так явно, как принятый ответ, это именно то, что я ищу (и я даже не знал об этом!). –

+0

Ваш прием. Пожалуйста, голосуйте, если вам это нравится :) – Vince

 Смежные вопросы

  • Нет связанных вопросов^_^