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

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

H(i,j):    максимальная оценка глобального выравнивания 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] должны быть выровнены.

HS(i,j):  максимальная оценка глобального выравнивания 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] выровнен с символом пробела.

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