Алгоритм глобального выравнивания последовательностей

Рассмотрим алгоритм нахождения оптимального глобального выравнивания последовательностей при использовании локальной оценочной функции. Обычно при подобных условиях поиск оптимального выравнивания последовательностей производят на ориентированном графе (рис. 2.6).

Рис. 2.6. Пример выравнивания двух последовательностей

а — конкретный вариант выравнивания можно представить как путь на матрице выравнивания. Множество всех путей составляют ориентированный граф, отражающий множество всех вариантов выравнивания последовательностей; б — трансформация пути на графе в стандартное представление выравнивания Продвижение по вертикальному или горизонтальному ребру графа означает пропуск аминокислотного остатка в одной из последовательностей, т. е. выравнивание символа из другой последовательности со специальным «пустым» символом. Перемещение же по диагональному ребру указывает на выравнивание символов в обеих последовательностях друг над другом. Множество всех путей на графе отражает множество возможных выравниваний двух последовательностей.

Рассмотрим работу алгоритма (рис. 2.7). Возьмем вершину Л₀В₀ как стартовую для всех возможных выравниваний. Мы можем это сделать, так как выравнивание глобальное, т. е. должно включать обе последовательности.

Рис. 2.7. Последовательность шагов при поиске глобального выравнивания последовательностей (комментарии — в тексте).

Есть три возможных пути из этой точки:

• 1) в вершину с координатами А_ХВ₀ — выравнивание первого символа в последовательности А с пустым символом в последовательности В;
• 2) в вершину с координатами А_ХВ_Х — выравнивание символов А_х и В_х;
• 3) в вершину с координатами А₀В_Х — выравнивание первого символа в последовательности В с пустым символом в последовательности А.

Для каждого продвижения по одному из ребер мы можем определить стоимость согласно оценочной функции:

где a (X, Y) — стоимость выравнивания символов X и Y;g— величина штрафа за пропуск; k — тип ребра, по которому производится продвижение (рис. 2.8). Запишем эти значения в соответствующие вершины.

Рис. 2.8. Возможные продвижения по ребрам графа при поиске пути, соответствующего глобальному выравниванию последовательностей.

Типы продвижений:

k = 2 — выравнивание символов с изменением предыдущего значения оценочной функции на стоимость выравнивания двух символов (a (/l, Bj)) k = 1; 3 — пропуск символов в одной из последовательностей с уменьшением предыдущего значения оценочной функции на величину штрафа за пропуск (g — в приведенном варианте штраф линейно зависит от длины пропуска) Рассмотрим вершину А₀В_] (см. рис. 2.7), в которой у нас содержится значение оценочной функции от выравнивания символа А_х с пустым символом. Из этой точки также возможны три пути (к А₍₎В₂, А_ХВ₂ и А_ХВ_Х). При этом отметим, что в вершине А_ХВ_Х уже записан результат предыдущего этапа работы алгоритма. Поскольку мы ищем путь с наибольшей стоимостью и наша оценочная функция локальна, достаточно хранить в данной вершине лишь максимальное значение из возможных. Отметим, что для каждой вершины «внутренней» части графа принципиально возможны три варианта (см. рис. 2.8). Также для каждой вершины следует сохранить указатель на вершину, из которой пришло максимальное значение. В данном случае это вершина А₀В₀.

Указатель нам потребуется на этапе восстановления выравнивания по пути на графе (см. далее). Поскольку в тот момент, когда мы обрабатываем вершину, в ней содержится значение оценочной функции для наиболее выгодного пути до данной вершины, то после последовательного прохода всех вершин графа в одной строке (слева направо) и всех строк (сверху вниз) в вершине А_МВ_v будет находиться значение стоимости наиболее выгодного пути по графу. Поскольку для каждой вершины мы сохраняли указатель на предыдущую «наиболее выгодную» вершину, то, пройдя обратный путь по этим указателям, мы можем восстановить «оптимальное выравнивание» (см. рис. 2.7). Это выравнивание и будет оптимальным глобальным выравниванием последовательностей Л и В.

Описанный выше алгоритм требует конечного числа вычислений для каждого узла, и с увеличением длин последовательностей время, необходимое для поиска оптимального пути, растет пропорционально произведению длин последовательностей (0(т • п) или 0(п²))К