Лого сайта
Иллюстрация работы алгоритмов Нидлмана-Вунша и Смита-Ватермана на примере короткого участка выравнивания

Рассмотрим работу двух алгоритмов выравнивания, но преед этим размерем те упрощения, которые будут сделаны при этом.

Таблица 1. Сравнение характеристик работы алгоритмов выравнивания и их упрощений.

Характеристика алгоритма Нидлмана-Вунша Нидлмана-Вунша при упрощении Смита-Ватермана Смита-Ватермана при упрощении
Модель штрафа за гэп афинная не афинная афинная не афинная
Вид выравнивания глобальное глобальное локальное локальное
Оценка значимости замен по матрице замен топорно: совпадает +1 не совпадает -1 по матрице замен топорно: совпадает +1 не совпадает -1

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

Рассматриваемый участок выравнивания взят из теоретического мутанта белка CLPQ_BACSU, по которому построены выравнивания по алгоритму Нидлмана-Вунша и Смита-Ватермана.

Таблица 2. Указание фрагментов взятых из выранвиваний

Алгоритм Нидлмана-Вунша Алгоритм Смита-Ватермана
иллюстрация положения
участок из белкаLFEKLFEK
участок из мутантаNHFFEPNHFFEP

На основании выбранных участков строятся выранвивания по иллюстративной схеме: штраф за гэп -2, за не совпадение -1, за совпадение +1.

Иллюстрация 1. Построение графа работы алгоритма Нидлмана-Вунша, обратный проход указан желтым.


На основании данной иллюстрации ясно видно, что возможны несколько кооптимальных выравниваний.

Таблица 3. Кооптимальные выравнивания, построенные при проходе алгоритма Нидлмана-Вунша, приведенного на Иллюстрации 1.

выравнивание
1
NHFFEP
-LF-EK
2
NHFFEP
-L-FEK
3
NHFFEP
--LFEK

Иллюстрация 2. Построение графа работы алгоритма Смита-Ватермана, обратный проход указан желтым.


На основании данной иллюстрации ясно видно получаемое выравнивание.

Таблица 4. Оптимальное выравнивание, построенные при проходе алгоритма Смита-Ватермана, приведенного на Иллюстрации 2.

выравнивание
1
FE
FE

Вывод: Полученные выравнивания имеют в целом не большую корреляцию с выравниваниями, полученными програмно (лучше -для needle, ведь тут одно из кооптимальных совпало с програмным участком; хуже-для water, ведь совпадение достаточно мало), т.к. не смотря на то, что и там и там используются одинаковые алгоритмы, условия выполнения этих алгоритмов сильно отличаются (см. Таблица 1.).