Алгоритм Нидлмана — Вунша, алгоритм для выполнения выравнивания двух последовательностей (будем называть их 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 для сопоставления строк.
Нидлман и Вунш сформулировали свою задачу в терминах максимизации похожести. Другая возможность заключается в минимизации редакционного расстояния между последовательностями, предложенной В. Левенштейном, однако было показано, что две эти задачи эквивалентны.
В современной терминологии «Нидлман — Вунш» относится к алгоритму выравнивания последовательностей квадратичному по времени для линейного или аффинного штрафа за разрыв.