Глобальное выравнивание.
Выравнивание, соответствующее показанному в matrix.xls пути: M A N P -
M I N A K
2 -1+2 -1 -2 =0 - вес этого выравнивания (к такому же результату приводит выделенный путь).
Последовательности - это первые 4 а/к моего белка и та же искусственно измененная последовательность. Алгоритм предназначен для выбора выравнивания с наибольшим весом. Заполнение матрицы происходит следующим способом:
верхнюю строку и первый столбец заполняют, постепенно прибавляя штрафы за гэпы,
стрелки в направлении к левому верхнему углу страницы
все остальные ячейки так ( с номером i,j):
i,j-1 + штраф за гэп
i-1,j + штраф за гэп
i-1,j-1 + вес этой замены (аминокислоты с соотв. номерами из 2-х послед.)
Максимум из этих 3-х чисел - содержание ячейки
стрелки расставляют в том направлении, откуда "пришло" это максимальное значение.
Этот алгоритм хорош тем, что по своей сути является рекурсивным. Это значительно облегчает выбор наибольшего веса, т.к. на каждом шаге делается одно и то же, независимо от длины последовательности ( информация о наилучшем варианте не "накапливается"). Также этот алгоритм позволяет найти то выравнивание, для которого вес максимален.
