Центральный Дом Знаний - Алгоритм Нидлмана — Вунша

Информационный центр "Центральный Дом Знаний"

Заказать учебную работу! Жми!



ЖМИ: ТУТ ТЫСЯЧИ КУРСОВЫХ РАБОТ ДЛЯ ТЕБЯ

      cendomzn@yandex.ru  

Наш опрос

Как Вы планируете отдохнуть летом?
Всего ответов: 903

Онлайн всего: 1
Гостей: 1
Пользователей: 0


Форма входа

Логин:
Пароль:

Алгоритм Нидлмана — Вунша

Алгоритм Нидлмана — Вунша, алгоритм для выполнения выравнивания двух последовательностей (будем называть их A и B), который используется в биоинформатике при построении выравниваний аминокислотных или нуклеотидных последовательностей. Алгоритм был предложен в 1970 году Солом Нидлманом и Кристианом Вуншем.

А.Н.-В. является примером динамического программирования, и он оказался первым примером приложения динамического программирования к сравнению биологических последовательностей.

Соответствие выровненных символов задается матрицей похожести. Здесь S(a,\;b) — похожесть символов a и b. Также используется линейный штраф за разрыв, называемый здесь d.

Например, если матрица похожести задается таблицей

-

A

G

C

T

A

10

-1

-3

-4

G

-1

7

-5

-3

C

-3

-5

9

0

T

-4

-3

0

8

то выравнивание:

AGACTAGTTAC

CGA‒‒‒GACGT

со штрафом за разрыв d = − 5 будет иметь следующую оценку:

S(A,\;C)+S(G,\;G)+S(A,\;A)+3\times d+S(G,\;G)+S(T,\;A)+S(T,\;C)+S(A,\;G)+S(C,\;T)

=-3+7+10-(3\times 5)+7+(-4)+0+(-1)+0=1.

Для нахождения выравнивания с наивысшей оценкой назначается двумерный массив (или матрица) F, содержащая столько же строк, сколько символов в последовательности A, и столько же столбцов, сколько символов в послдеовательности B. Запись в строке i и столбце j обозначается далее как Fij. Таким образом, если мы выравниваем последовательности размеров n и m, то количество требуемой памяти будет O(nm). (Алгоритм Хиршберга позволяет вычислять оптимальное выравнивание, используя O(n + m) количество памяти, но примерно вдвое большее время счета.)

В процессе работы алгоритма величина Fij будет принимать значения оптимальной оценки для выравнивания первых i=0,\;\ldots,\;n символов в A и первых j=0,\;\ldots,\;m символов в B. Тогда принцип оптимальности Беллмана может быть сформулирован следующим образом:

Базис:

F_{0j}=d\cdot j

F_{i0}=d\cdot i

Рекурсия, основанная на принципе оптимальности:

F_{ij}=\max(F_{i-1,\;j-1}+S(A_i,\;B_j),\;F_{i,\;j-1}+d,\;F_{i-1,\;j}+d).

Таким образом, псевдо-код алгоритма для вычисления матрицы F будет выглядеть следующим образом:

for i=0 to length(A)

F(i,0) ← d*i

for j=0 to length(B)

F(0,j) ← d*j

for i=1 to length(A)

for j = 1 to length(B)

{

Match ← F(i-1,j-1) + S(Ai, Bj)

Delete ← F(i-1, j) + d

Insert ← F(i, j-1) + d

F(i,j) ← max(Match, Insert, Delete)

}

Когда матрица F рассчитана, её элемент Fij дает максимальную оценку среди всех возможных выравниваний. Для вычисления самого выравнивания, которое получило такую оценку, нужно начать с правой нижней клетки и сравнивать значения в ней с тремя возможными источниками (соответствие, вставка или делеция), чтобы увидеть, откуда оно появилось. В случае соответствия Ai и Bj выровнены, в случае делеции Ai выровнено с разрывом, а в случае вставки с разрывом выровнено уже Bj. (В общем случае может быть более одного варианта с одинаковым значением, которые приведут к альтернативным оптимальным выравниваниям.)

AlignmentA ← ""

AlignmentB ← ""

i ← length(A)

j ← length(B)

while (i > 0 and j > 0)

{

Score ← F(i,j)

ScoreDiag ← F(i - 1, j - 1)

ScoreUp ← F(i, j - 1)

ScoreLeft ← F(i - 1, j)

if (Score == ScoreDiag + S(Ai, Bj))

{

AlignmentA ← Ai + AlignmentA

AlignmentB ← Bj + AlignmentB

i ← i - 1

j ← j - 1

}

else if (Score == ScoreLeft + d)

{

AlignmentA ← Ai + AlignmentA

AlignmentB ← "-" + AlignmentB

i ← i - 1

}

otherwise (Score == ScoreUp + d)

{

AlignmentA ← "-" + AlignmentA

AlignmentB ← Bj + AlignmentB

j ← j - 1

}

}

while (i > 0)

{

AlignmentA ← Ai + AlignmentA

AlignmentB ← "-" + AlignmentB

i ← i - 1

}

while (j > 0)

{

AlignmentA ← "-" + AlignmentA

AlignmentB ← Bj + AlignmentB

j ← j - 1

}

Нидлман и Вунш описали свой алгоритм в явном виде для случая, когда оценивается только соответствие или несоответствие символов, но не разрыв (d = 0). В оригинальной публикации от 1970 года предлагается рекурсия

F_{ij}=\max_{h<i,\;k<j}\{F_{h,\;j-1}+S(A_i,\;B_j),\;F_{i-i,\;k}+S(A_i,\;B_j)\}.

Соответствующий алгоритм динамического программирования требует кубического времени для расчета. В статье также указывается, что рекурсия может быть адаптирована и на случай любой формулы для штрафа за разрыв:

Штраф за разрыв — число, вычитаемое за каждый разрыв, — может рассматриваться, как помеха появлению разрывов в выравнивании. Величина штрафа за разрыв может быть функцией размера и/или направления разрыва. 

Более быстрый алгоритм динамического программирования с квадратичным временем выполнения для той же задачи (нет штрафа за разрыв) был впервые предложен  Давидом Санкофф в 1972. Аналогичный квадратичный по времени алгоритм был независимо открыт Т. К. Винцюком  в 1968 для обработке речи (динамическое предыскажение шкалы) и Робертом А. Вагнером и Майклом Дж. Фишером в 1974 для сопоставления строк.

Нидлман и Вунш сформулировали свою задачу в терминах максимизации похожести. Другая возможность заключается в минимизации редакционного расстояния между последовательностями, предложенной В. Левенштейном, однако было показано, что две эти задачи эквивалентны.

В современной терминологии «Нидлман — Вунш» относится к алгоритму выравнивания последовательностей квадратичному по времени для линейного или аффинного штрафа за разрыв.

Loading

Календарь

«  Июнь 2019  »
ПнВтСрЧтПтСбВс
     12
3456789
10111213141516
17181920212223
24252627282930

Архив записей

Друзья сайта

  • Заказать курсовую работу!
  • Выполнение любых чертежей
  • Новый фриланс 24