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

Эта статья находится на начальном уровне проработки, в одной из её версий выборочно используется текст из источника, распространяемого под свободной лицензией
Материал из энциклопедии Руниверсалис

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

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

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

Соответствие выровненных символов задается матрицей похожести. Здесь [math]\displaystyle{ S(a,\;b) }[/math] — похожесть символов [math]\displaystyle{ a }[/math] и [math]\displaystyle{ b }[/math]. Также используется линейный штраф за разрыв, называемый здесь [math]\displaystyle{ 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]\displaystyle{ d=-5 }[/math] будет иметь следующую оценку:

[math]\displaystyle{ S(G,\;G)+2\times d+S(A,\;A)+S(C,\;C)+2\times d }[/math]
[math]\displaystyle{ =7+(2\times -5)+10+9+(2\times -5)=6. }[/math]

Для нахождения выравнивания с наивысшей оценкой назначается двумерный массив (или матрица) [math]\displaystyle{ F }[/math], содержащая столько же строк, сколько символов в последовательности [math]\displaystyle{ A }[/math], и столько же столбцов, сколько символов в последовательности [math]\displaystyle{ B }[/math]. Запись в строке [math]\displaystyle{ i }[/math] и столбце [math]\displaystyle{ j }[/math] обозначается далее как [math]\displaystyle{ F_{ij} }[/math]. Таким образом, если мы выравниваем последовательности размеров [math]\displaystyle{ n }[/math] и [math]\displaystyle{ m }[/math], то количество требуемой памяти будет [math]\displaystyle{ O(nm) }[/math]. (Алгоритм Хиршберга (англ. Hirschberg's algorithm) позволяет вычислять оптимальное выравнивание, используя [math]\displaystyle{ O(n+m) }[/math] количество памяти, но примерно вдвое большее время счета.)

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

  Базис:
  [math]\displaystyle{ F_{0j}=d\cdot j }[/math]
  [math]\displaystyle{ F_{i0}=d\cdot i }[/math]
  Рекурсия, основанная на принципе оптимальности:
  [math]\displaystyle{ 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]\displaystyle{ F }[/math] рассчитана, её элемент [math]\displaystyle{ F_{ij} }[/math] дает максимальную оценку среди всех возможных выравниваний. Для вычисления самого выравнивания, которое получило такую оценку, нужно начать с правой нижней клетки и сравнивать значения в ней с тремя возможными источниками (соответствие, вставка или удаление), чтобы увидеть, откуда оно появилось. В случае соответствия [math]\displaystyle{ A_i }[/math] и [math]\displaystyle{ B_j }[/math] выровнены, в случае удаления[math]\displaystyle{ A_i }[/math] выровнено с разрывом, а в случае вставки с разрывом выровнено уже [math]\displaystyle{ 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]\displaystyle{ d=0 }[/math]). В оригинальной публикации[1] от 1970 года предлагается рекурсия

[math]\displaystyle{ F_{ij}=\max_{h\lt i,\;k\lt 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], что две эти задачи эквивалентны.

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


См. также

Примечания

  1. ↑ 1,0 1,1 Needleman, Saul B.; and Wunsch, Christian D. A general method applicable to the search for similarities in the amino acid sequence of two proteins (англ.) // Journal of Molecular Biology  (англ.) (рус. : journal. — 1970. — Vol. 48, no. 3. — P. 443—453. — doi:10.1016/0022-2836(70)90057-4. — PMID 5420325.
  2. ↑ Sankoff, D. Matching sequences under deletion/insertion constraints (англ.) // Proceedings of the National Academy of Sciences of the United States of America : journal. — 1972. — Vol. 69, no. 1. — P. 4—6.
  3. ↑ Vintsyuk, T. K. Speech discrimination by dynamic programming (неопр.) // Kibernetika. — 1968. — Т. 4. — С. 81—88.
  4. ↑ Wagner, R. A. and Fischer, M. J. The string-to-string correction problem (англ.) // Journal of the ACM : journal. — 1974. — Vol. 21. — P. 168—173. — doi:10.1145/321796.321811.
  5. ↑ Sellers, P. H. On the theory and computation of evolutionary distances (англ.) // SIAM Journal on Applied Mathematics  (англ.) (рус. : journal. — 1974. — Vol. 26, no. 4. — P. 787—793.

Ссылки

Источник — https://xn--h1ajim.xn--p1ai/index.php?title=Алгоритм_Нидлмана_—_Вунша&oldid=5869247