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

Перейти к навигации Перейти к поиску
м
Нет описания правки
Строка 26: Строка 26:
== Основные результаты ==
== Основные результаты ==


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


H(i,j):    максимальная оценка глобального выравнивания U и V над всеми суффиксами U в S[1::i] и всеми суффиксами V в T[1::j].
<math>H(i, j)</math>:    максимальная оценка глобального выравнивания 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] должны быть выровнены.
<math>H_N(i, j)</math>: максимальная оценка глобального выравнивания 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] выровнен с символом пробела.
<math>H_S(i, j)</math>:  максимальная оценка глобального выравнивания 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] выровнен с символом пробела.
<math>H_T(i, j)</math>: максимальная оценка глобального выравнивания U и V над всеми суффиксами U в S[1..i] и всеми суффиксами V в T[1..j], где T[j] выровнен с символом пробела.




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




Строка 48: Строка 48:
Шаг рекурсии:
Шаг рекурсии:


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

правка

Навигация