Алгоритм Нидлмана

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

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

Современное представление

Соответствие выровненных символов задается матрицей похожести. Здесь $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$ обозначается далее как $F_{ij}$. Таким образом, если мы выравниваем последовательности размеров $n$ и $m$, то количество требуемой памяти будет $O(nm)$. (Алгоритм Хиршберга позволяет вычислять оптимальное выравнивание, используя $O(n+m)$ количество памяти, но примерно вдвое большее время счета.)

В процессе работы алгоритма величина $F_{ij}$ будет принимать значения оптимальной оценки для выравнивания первых $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$ рассчитана, её элемент $F_{ij}$ дает максимальную оценку среди всех возможных выравниваний. Для вычисления самого выравнивания, которое получило такую оценку, нужно начать с правой нижней клетки и сравнивать значения в ней с тремя возможными источниками (соответствие, вставка или делеция), чтобы увидеть, откуда оно появилось. В случае соответствия $A_i$ и $B_j$ выровнены, в случае делеции $A_i$ выровнено с разрывом, а в случае вставки с разрывом выровнено уже $B_j$. (В общем случае может быть более одного варианта с одинаковым значением, которые приведут к альтернативным оптимальным выравниваниям.)

  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$). В оригинальной публикации^[1] от 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)\}.$

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

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

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

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

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

См. также

• Алгоритм Смита — Ватермана
• BLAST
• Расстояние Левенштейна

Примечания

1. ↑ ^{1 2} Needleman, Saul B.; and Wunsch, Christian D. (1970). «A general method applicable to the search for similarities in the amino acid sequence of two proteins». Journal of Molecular Biology 48 (3): 443–53. DOI:10.1016/0022-2836(70)90057-4. PMID 5420325.
2. ↑ Sankoff, D. (1972). «Matching sequences under deletion/insertion constraints». Proceedings of the National Academy of Sciences of the USA 69 (1): 4–6.
3. ↑ Vintsyuk, T. K. (1968). «Speech discrimination by dynamic programming». Kibernetika 4: 81-88.
4. ↑ Wagner, R. A. and Fischer, M. J. (1974). «The string-to-string correction problem». Journal of the ACM 21: 168-173. DOI:10.1145/321796.321811.
5. ↑ Sellers, P. H. (1974). «On the theory and computation of evolutionary distances». SIAM Journal on Applied Mathematics 26 (4): 787-793.

Ссылки

• 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