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

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

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

Соответствие выровненных символов задается матрицей похожести. Здесь  — похожесть символов 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 будет иметь следующую оценку:

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

В процессе работы алгоритма величина Fij будет принимать значения оптимальной оценки для выравнивания первых  символов в A и первых  символов в B. Тогда принцип оптимальности Беллмана может быть сформулирован следующим образом:

Базис:

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

Таким образом, псевдо-код алгоритма для вычисления матрицы 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 года предлагается рекурсия

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

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

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

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

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