4501
правка
Irina (обсуждение | вклад) Нет описания правки |
Irina (обсуждение | вклад) |
||
Строка 26: | Строка 26: | ||
== Основные результаты == | == Основные результаты == | ||
Задача попарного локального выравнивания может быть решена за время O(mn) с использованием O(mn) памяти при помощи динамического программирования. Алгоритм должен заполнить четыре таблицы H, | Задача попарного локального выравнивания может быть решена за время O(mn) с использованием O(mn) памяти при помощи динамического программирования. Алгоритм должен заполнить четыре таблицы <math>H, H_N, H_S, H_T</math> размером m x n, где на каждую запись требуется константное время. Эти таблицы содержат следующие значения. | ||
H(i,j): максимальная оценка глобального выравнивания U и V над всеми суффиксами U в S[1 | <math>H(i, j)</math>: максимальная оценка глобального выравнивания U и V над всеми суффиксами U в S[1..i] и всеми суффиксами V в T[1..j]. | ||
<math>H_N(i, j)</math>: максимальная оценка глобального выравнивания U и V над всеми суффиксами U в S[1..i] и всеми суффиксами V в T[1..j], с ограничением, согласно которому S[i] и T[j] должны быть выровнены. | |||
<math>H_S(i, j)</math>: максимальная оценка глобального выравнивания U и V над всеми суффиксами U в S[1..i] и всеми суффиксами V в T[1..j], где S[j] выровнен с символом пробела. | |||
<math>H_T(i, j)</math>: максимальная оценка глобального выравнивания U и V над всеми суффиксами U в S[1..i] и всеми суффиксами V в T[1..j], где T[j] выровнен с символом пробела. | |||
Оценка оптимального локального выравнивания S и T будет равна | Оценка оптимального локального выравнивания S и T будет равна max {H(i, j)}, а локальное выравнивание S и T может быть найдено путем обратного обхода таблицы H. | ||
Строка 48: | Строка 48: | ||
Шаг рекурсии: | Шаг рекурсии: | ||
== Применение == | == Применение == | ||
Локальное выравнивание с аффинными штрафами за открытие гэпа может использоваться для лассификации белков, филогенетического футпринтинга и идентификации функциональных элементов последовательности. | Локальное выравнивание с аффинными штрафами за открытие гэпа может использоваться для лассификации белков, филогенетического футпринтинга и идентификации функциональных элементов последовательности. |
правка