Аноним

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

Материал из WEGA

Локальное выравнивание (с аффинными штрафами за гэп) (посмотреть исходный код)

Версия от 21:58, 8 мая 2021

165 байт добавлено ,  8 мая 2021
нет описания правки
(Новая страница: «== Ключевые слова и синонимы == Парное локальное выравнивание с аффинными штрафами за отк…»)
 
Нет описания правки
Строка 2: Строка 2:
Парное локальное выравнивание с аффинными штрафами за открытие гэпа
Парное локальное выравнивание с аффинными штрафами за открытие гэпа


== Постановка задачи ==
== Постановка задачи ==
Задача парного локального выравнивания связана с определением пары похожих подстрок в двух молекулярных последовательностях. В компьютерных науках эта задача изучалась более сорока лет. Однако до 1974 года большинство моделей задачи, как правило, не были удовлетворительными с биологической точки зрения либо не поддавались интерпретации. В 1974 году Питер Селлерс разработал метрическую меру сходства между молекулярными последовательностями. Уотермен и др. (1976) обобщили эту метрику, включив в нее вставки (инсерции) и удаления (делеции) произвольной длины, которые представляют собой минимальное количество мутационных событий, необходимых для преобразования одной последовательности в другую.
Задача парного локального выравнивания связана с определением пары похожих подстрок в двух молекулярных последовательностях. В компьютерных науках эта задача изучалась более сорока лет. Однако до 1974 года большинство моделей задачи, как правило, не были удовлетворительными с биологической точки зрения либо не поддавались интерпретации. В 1974 году Питер Селлерс разработал метрическую меру сходства между молекулярными последовательностями. Уотермен и др. (1976) обобщили эту метрику, включив в нее вставки (инсерции) и удаления (делеции) произвольной длины, которые представляют собой минимальное количество мутационных событий, необходимых для преобразования одной последовательности в другую.




Пусть даны две последовательности, 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', соответственно, с той же длиной. Выравнивание двух последовательностей может производиться различными способами. Оценка выравнивания измеряется метрикой <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::n] и T[1::m].
Дано: две последовательности S[1..n] и T[1..m].


Требуется: найти подстроку U в S и подстроку V в T, такие, что оптимальное глобальное выравнивание U и V максимально.
Требуется: найти подстроку U в S и подстроку V в T, такие, что оптимальное глобальное выравнивание U и V максимально.
Irina
4551

правка

Источник — http://pco.iis.nsk.su/wega/index.php/Служебная:Сравнение_версий/14553