Рассмотрим работу двух алгоритмов выравнивания, но преед этим размерем те упрощения, которые будут сделаны при этом.
Таблица 1. Сравнение характеристик работы алгоритмов выравнивания и их упрощений.
Характеристика алгоритма | Нидлмана-Вунша | Нидлмана-Вунша при упрощении | Смита-Ватермана | Смита-Ватермана при упрощении
|
Модель штрафа за гэп | афинная | не афинная | афинная | не афинная
|
Вид выравнивания | глобальное | глобальное | локальное | локальное
|
Оценка значимости замен | по матрице замен | топорно: совпадает +1 не совпадает -1 | по матрице замен | топорно: совпадает +1 не совпадает -1
|
| | | |
|
На основании указанных упрощений реальные выравнивания, создаваемые по указанным выше алгоритмам могут отличаться от полученных при упрощенном иллюстрировании их работы.
Рассматриваемый участок выравнивания взят из теоретического мутанта белка CLPQ_BACSU, по которому построены выравнивания по алгоритму Нидлмана-Вунша и Смита-Ватермана.
Таблица 2. Указание фрагментов взятых из выранвиваний
| Алгоритм Нидлмана-Вунша | Алгоритм Смита-Ватермана
|
иллюстрация положения | |
|
участок из белка | LFEK | LFEK
|
участок из мутанта | NHFFEP | NHFFEP
|
На основании выбранных участков строятся выранвивания по иллюстративной схеме: штраф за гэп -2, за не совпадение -1, за совпадение +1.
Иллюстрация 1. Построение графа работы алгоритма Нидлмана-Вунша, обратный проход указан желтым.
На основании данной иллюстрации ясно видно, что возможны несколько кооптимальных выравниваний.
Таблица 3. Кооптимальные выравнивания, построенные при проходе алгоритма Нидлмана-Вунша, приведенного на Иллюстрации 1.
Иллюстрация 2. Построение графа работы алгоритма Смита-Ватермана, обратный проход указан желтым.
На основании данной иллюстрации ясно видно получаемое выравнивание.
Таблица 4. Оптимальное выравнивание, построенные при проходе алгоритма Смита-Ватермана, приведенного на Иллюстрации 2.
Вывод: Полученные выравнивания имеют в целом не большую корреляцию с выравниваниями, полученными програмно (лучше -для needle, ведь тут одно из кооптимальных совпало с програмным участком; хуже-для water, ведь совпадение достаточно мало), т.к. не смотря на то, что и там и там используются одинаковые алгоритмы, условия выполнения этих алгоритмов сильно отличаются (см. Таблица 1.).