Локальное выравнивание (с аффинными штрафами за гэп): различия между версиями

Парное локальное выравнивание с аффинными штрафами за открытие гэпа

== Постановка задачи ==

Пусть даны две последовательности, S и T. Парное выравнивание представляет собой способ вставки символов пробелов '_' в S и T для формирования последовательностей S' и Г, соответственно, с той же длиной. Выравнивание двух последовательностей может производиться различными способами. Оценка выравнивания измеряется метрикой S(x,y). В каждой позиции i, где x и y не являются пробелами, сходство между S'[i] и T'[i] измеряется 8(S'[i], T'[j]). Обычно S(x,y) положительно, когда x и y одинаковы, и отрицательно, когда x и y различны. Для позиций с последовательными символами пробела оценки выравнивания символов пробела не рассматриваются независимо; это связано с тем, что вставка или удаление длинного участка в молекулярных последовательностях более вероятна, чем вставка или удаление нескольких коротких участков. Смит и Уотермен используют аффинный штраф за гэп для моделирования сходства в позициях с символами пробелов. Они определяют последовательную подстроку с пробелами в S' или Г как гэп. Для каждого гэпа длиной l они назначают линейный штраф Wk = Ws + l x Wp для некоторых заранее определенных положительных констант Ws и Wp. Оценка выравнивания представляет собой сумму оценок в каждой позиции i минус штрафы за каждый гэп. Например, оценка следующего выравнивания равна S(G, G) + S(C, C) + S(C, C) + S(U, C) + S(G, G) - (Ws + 2 x Wp).

Оптимальное глобальное выравнивание последовательностей S и T – это выравнивание S и T с максимальной выравнивания. Но иногда мы хотим узнать, содержат ли последовательности S и T похожие подстроки, а не то, похожи ли S и T. В этом случае решают задачу парного локального выравнивания, которая заключается в поиске подстроки U в S и другой подстроки V в T, такой, что глобальная оценка выравнивания U и V максимальна.

Дано: две последовательности S[1::n] и T[1::m].

Задача попарного локального выравнивания может быть решена за время O(mn) с использованием O(mn) памяти при помощи динамического программирования. Алгоритм должен заполнить четыре таблицы H, HN, HS и HT размером m x n, где на каждую запись требуется константное время. Эти таблицы содержат следующие значения.

H(i,j):    максимальная оценка глобального выравнивания U и V над всеми суффиксами U в S[1::i] и всеми суффиксами V в T[1::j].

HN(i,j): максимальная оценка глобального выравнивания U и V над всеми суффиксами U в S[1::i] и всеми суффиксами V в T[1::j], с ограничением, согласно которому S[i] и T[j] должны быть выровнены.

HS(i,j):  максимальная оценка глобального выравнивания U и V над всеми суффиксами U в S[1::i] и всеми суффиксами V в T[1::j], где S[j] выровнен с символом пробела.

HT(i,j): максимальная оценка глобального выравнивания U и V над всеми суффиксами U в S[1::i] и всеми суффиксами V в T[1::j], где T[j] выровнен с символом пробела.

Оценка оптимального локального выравнивания S и T будет равна maxfH( i;j)g, а локальное выравнивание S и T может быть найдено путем обратного обхода таблицы H.

Локальное выравнивание с аффинными штрафами за открытие гэпа может использоваться для лассификации белков, филогенетического футпринтинга и идентификации функциональных элементов последовательности.

* [[Эффективные методы множественного выравнивания последовательностей с гарантированными границами погрешности]]

* [[Локальное выравнивание (с вогнутыми штрафами за открытие гэпа)]]