4501
правка
Локальное выравнивание (с аффинными штрафами за гэп): различия между версиями
Перейти к навигации
Перейти к поиску
Локальное выравнивание (с аффинными штрафами за гэп) (посмотреть исходный код)
Версия от 21:58, 8 мая 2021
, 8 мая 2021нет описания правки
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Парное локальное выравнивание с аффинными штрафами за отк…») |
Irina (обсуждение | вклад) Нет описания правки |
||
| Строка 2: | Строка 2: | ||
Парное локальное выравнивание с аффинными штрафами за открытие гэпа | Парное локальное выравнивание с аффинными штрафами за открытие гэпа | ||
== Постановка задачи == | |||
Задача парного локального выравнивания связана с определением пары похожих подстрок в двух молекулярных последовательностях. В компьютерных науках эта задача изучалась более сорока лет. Однако до 1974 года большинство моделей задачи, как правило, не были удовлетворительными с биологической точки зрения либо не поддавались интерпретации. В 1974 году Питер Селлерс разработал метрическую меру сходства между молекулярными последовательностями. Уотермен и др. (1976) обобщили эту метрику, включив в нее вставки (инсерции) и удаления (делеции) произвольной длины, которые представляют собой минимальное количество мутационных событий, необходимых для преобразования одной последовательности в другую. | Задача парного локального выравнивания связана с определением пары похожих подстрок в двух молекулярных последовательностях. В компьютерных науках эта задача изучалась более сорока лет. Однако до 1974 года большинство моделей задачи, как правило, не были удовлетворительными с биологической точки зрения либо не поддавались интерпретации. В 1974 году Питер Селлерс разработал метрическую меру сходства между молекулярными последовательностями. Уотермен и др. (1976) обобщили эту метрику, включив в нее вставки (инсерции) и удаления (делеции) произвольной длины, которые представляют собой минимальное количество мутационных событий, необходимых для преобразования одной последовательности в другую. | ||
Пусть даны две последовательности, S и T. Парное выравнивание представляет собой способ вставки символов пробелов '_' в S и T для формирования последовательностей S' и | Пусть даны две последовательности, 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: GCCAUUG T: GCC__CG | |||
S: GCCAUUG | |||
T: GCC__CG | |||
| Строка 15: | Строка 19: | ||
'''Задача парного локального выравнивания''' | '''Задача парного локального выравнивания''' | ||
Дано: две последовательности S[1 | Дано: две последовательности S[1..n] и T[1..m]. | ||
Требуется: найти подстроку U в S и подстроку V в T, такие, что оптимальное глобальное выравнивание U и V максимально. | Требуется: найти подстроку U в S и подстроку V в T, такие, что оптимальное глобальное выравнивание U и V максимально. | ||