Русская Википедия:Алгоритм Нидлмана — Вунша
Алгоритм Нидлмана — Вунша — это алгоритм для выполнения выравнивания двух последовательностей (будем называть их <math>A</math> и <math>B</math>), который используется в биоинформатике при построении выравниваний аминокислотных или нуклеотидных последовательностей. Алгоритм был предложен в 1970 году Солом Нидлманом и Кристианом Вуншем[1].
Алгоритм Нидлмана — Вунша является примером динамического программирования, и он оказался первым примером приложения динамического программирования к сравнению биологических последовательностей.
Современное представление
Соответствие выровненных символов задается матрицей похожести. Здесь <math>S(a,\;b)</math> — похожесть символов <math>a</math> и <math>b</math>. Также используется линейный штраф за разрыв, называемый здесь <math>d</math>.
Например, если матрица похожести задается таблицей
| - | A | G | C | T |
|---|---|---|---|---|
| A | 10 | -1 | -3 | -4 |
| G | -1 | 7 | -5 | -3 |
| C | -3 | -5 | 9 | 0 |
| T | -4 | -3 | 0 | 8 |
то выравнивание:
GTTAC‒‒ G‒‒ACGT
со штрафом за разрыв <math>d=-5</math> будет иметь следующую оценку:
- <math>S(G,\;G)+2\times d+S(A,\;A)+S(C,\;C)+2\times d</math>
- <math>=7+(2\times -5)+10+9+(2\times -5)=6.</math>
Для нахождения выравнивания с наивысшей оценкой назначается двумерный массив (или матрица) <math>F</math>, содержащая столько же строк, сколько символов в последовательности <math>A</math>, и столько же столбцов, сколько символов в последовательности <math>B</math>. Запись в строке <math>i</math> и столбце <math>j</math> обозначается далее как <math>F_{ij}</math>. Таким образом, если мы выравниваем последовательности размеров <math>n</math> и <math>m</math>, то количество требуемой памяти будет <math>O(nm)</math>. (Шаблон:Нп4 позволяет вычислять оптимальное выравнивание, используя <math>O(n+m)</math> количество памяти, но примерно вдвое большее время счета.)
В процессе работы алгоритма величина <math>F_{ij}</math> будет принимать значения оптимальной оценки для выравнивания первых <math>i=0,\;\ldots,\;n</math> символов в <math>A</math> и первых <math>j=0,\;\ldots,\;m</math> символов в <math>B</math>. Тогда принцип оптимальности Беллмана может быть сформулирован следующим образом:
Базис:
<math>F_{0j}=d\cdot j</math>
<math>F_{i0}=d\cdot i</math>
Рекурсия, основанная на принципе оптимальности:
<math>F_{ij}=\max(F_{i-1,\;j-1}+S(A_i,\;B_j),\;F_{i,\;j-1}+d,\;F_{i-1,\;j}+d).</math>
Псевдо-код алгоритма для вычисления матрицы 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)
}
Когда матрица <math>F</math> рассчитана, её элемент <math>F_{ij}</math> дает максимальную оценку среди всех возможных выравниваний. Для вычисления самого выравнивания, которое получило такую оценку, нужно начать с правой нижней клетки и сравнивать значения в ней с тремя возможными источниками (соответствие, вставка или удаление), чтобы увидеть, откуда оно появилось. В случае соответствия <math>A_i</math> и <math>B_j</math> выровнены, в случае удаления<math>A_i</math> выровнено с разрывом, а в случае вставки с разрывом выровнено уже <math>B_j</math>. (В общем случае может быть более одного варианта с одинаковым значением, которые приведут к альтернативным оптимальным выравниваниям.)
AlignmentA ← ""
AlignmentB ← ""
i ← length(A)
j ← length(B)
while (i > 0 or 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
}
Исторические замечания
Нидлман и Вунш описали свой алгоритм в явном виде для случая, когда оценивается только соответствие или несоответствие символов, но не разрыв (<math>d=0</math>). В оригинальной публикации[1] от 1970 года предлагается рекурсия
- <math>F_{ij}=\max_{h<i,\;k<j}\{F_{h,\;j-1}+S(A_i,\;B_j),\;F_{i-1,\;k}+S(A_i,\;B_j)\}.</math>
Соответствующий алгоритм динамического программирования требует кубического времени для расчета. В статье также указывается, что рекурсия может быть адаптирована и на случай любой формулы для штрафа за разрыв:
Штраф за разрыв — число, вычитаемое за каждый разрыв, — может рассматриваться, как помеха появлению разрывов в выравнивании. Величина штрафа за разрыв может быть функцией размера и/или направления разрыва. [стр. 444]
Более быстрый алгоритм динамического программирования с квадратичным временем выполнения для той же задачи (нет штрафа за разрыв) был впервые предложен[2] Давидом Санкофф в 1972. Аналогичный квадратичный по времени алгоритм был независимо открыт Т. К. Винцюком[3] в 1968 для обработке речи (динамическое предыскажение шкалы) и Робертом А. Вагнером и Майклом Дж. Фишером[4] в 1974 для сопоставления строк.
Нидлман и Вунш сформулировали свою задачу в терминах максимизации похожести. Другая возможность заключается в минимизации редакционного расстояния между последовательностями, предложенной В. Левенштейном, однако было показано[5], что две эти задачи эквивалентны.
В современной терминологии «Нидлман — Вунш» относится к алгоритму выравнивания последовательностей квадратичному по времени для линейного или аффинного штрафа за разрыв.
См. также
Примечания
Ссылки
- Needleman-Wunsch Algorithm as Ruby Code
- Java Implementation of the Needleman-Wunsch Algorithm
- B.A.B.A. — an applet (with source) which visually explains the algorithm.
- A clear explanation of NW and its applications to sequence alignment
- Sequence Alignment Techniques at Technology Blog
