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

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

 

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