На главную страницу второго семестра
Здесь можно ознакомиться с матрицей алгоритма.
Из последовательности первых четырех аминокислотных остатков белка FCTA_ECOLI получена искусственная последовательность вставкой 1 остатка и заменой 2 остатков. Для полученных последовательностей построена матрица переходов глобального выравнивания по алгоритму Нидельмана-Вунша при следующих входных данных: вес совпадения = 2, вес замены = -1, штраф за гэп = -2.
Немного об алгоритме. Алгоритм Нидельмана-Вунша подразумевает составление таблицы, строки которой соответствуют элементам одной из выравниваемых последоваельностей, столбцы - элементам другой, последние столбец и строка не соответствуют ничему. В первой клетке таблицы ставится значение 0. Каждая следующая клетка заполняется по такому принципу: переход в нее из клетки, расположенной слева сверху по диагонали означает сопоставление элементов, соответствующих клетке, откуда переход. К значению в клетке прибавляется либо цена совпадения, либо штраф за несовпадение (отрицательное число). Переход из клетки, расположенной выше, означает, что данному элементу первой последовательности соответствует гэп во второй. Переход из клетки, расположенной слева, означает, что данному элементу второй последовательности соответствует гэп в первой. В обоих этих случаях к значению в клетке, откуда переход, прибавляется штраф за гэп (отрицательное число). В клетку записывается наибольшее из 3 возможных значение, стрелкой указывается направление перехода. Таким образом заполняется вся матрица. Оптимальное выравнивание определяет путь из левой верхней клетки в правую нижнюю. Я пользовалась алгоритмом следующим образом: столбцы соответствуют первым 4 остаткам белка FCTA_ECOLI, строки - искусственной последовательности. Цена всех замен одинакова. Концевые гэпы штафуются.
Получено следующее выравнивание.
MS-TP MSHEA
Вес выравнивания равен 0. Естественно, это не единственное такое выравнивание, в некоторых местах можно было пойти другим путем. При этом изменилось бы взаимное положение гэпа и остатков, сопоставленных с несовпадающими. В данном случае считаем все замены равнозначными, поэтому между этими выравниваниями нет принципиальной разницы. Очевидно, что наивысший вес выравнивания в данном случае не может быть больше 0.