Алгоритм Нидлмана — Вунша — это алгоритм для выполнения выравнивания двух последовательностей (будем называть их и ), который используется в биоинформатике при построении выравниваний аминокислотных или нуклеотидных последовательностей. Алгоритм был предложен в 1970 году Солом Нидлманом и Кристианом Вуншем[1].
Алгоритм Нидлмана — Вунша является примером динамического программирования, и он оказался первым примером приложения динамического программирования к сравнению биологических последовательностей.
Соответствие выровненных символов задается матрицей похожести. Здесь — похожесть символов и . Также используется линейный штраф за разрыв, называемый здесь .
Например, если матрица похожести задается таблицей
- | 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
со штрафом за разрыв будет иметь следующую оценку:
Для нахождения выравнивания с наивысшей оценкой назначается двумерный массив (или матрица) , содержащая столько же строк, сколько символов в последовательности , и столько же столбцов, сколько символов в последовательности . Запись в строке и столбце обозначается далее как . Таким образом, если мы выравниваем последовательности размеров и , то количество требуемой памяти будет . (Алгоритм Хиршберга (англ. Hirschberg's algorithm) позволяет вычислять оптимальное выравнивание, используя количество памяти, но примерно вдвое большее время счета.)
В процессе работы алгоритма величина будет принимать значения оптимальной оценки для выравнивания первых символов в и первых символов в . Тогда принцип оптимальности Беллмана может быть сформулирован следующим образом:
Базис: Рекурсия, основанная на принципе оптимальности:
Таким образом, псевдо-код алгоритма для вычисления матрицы 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) }
Когда матрица рассчитана, её элемент дает максимальную оценку среди всех возможных выравниваний. Для вычисления самого выравнивания, которое получило такую оценку, нужно начать с правой нижней клетки и сравнивать значения в ней с тремя возможными источниками (соответствие, вставка или удаление), чтобы увидеть, откуда оно появилось. В случае соответствия и выровнены, в случае удаления выровнено с разрывом, а в случае вставки с разрывом выровнено уже . (В общем случае может быть более одного варианта с одинаковым значением, которые приведут к альтернативным оптимальным выравниваниям.)
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 }
Нидлман и Вунш описали свой алгоритм в явном виде для случая, когда оценивается только соответствие или несоответствие символов, но не разрыв ( ). В оригинальной публикации[1] от 1970 года предлагается рекурсия
Соответствующий алгоритм динамического программирования требует кубического времени для расчета. В статье также указывается, что рекурсия может быть адаптирована и на случай любой формулы для штрафа за разрыв:
Штраф за разрыв — число, вычитаемое за каждый разрыв, — может рассматриваться, как помеха появлению разрывов в выравнивании. Величина штрафа за разрыв может быть функцией размера и/или направления разрыва. [стр. 444]
Более быстрый алгоритм динамического программирования с квадратичным временем выполнения для той же задачи (нет штрафа за разрыв) был впервые предложен[2] Давидом Санкофф в 1972. Аналогичный квадратичный по времени алгоритм был независимо открыт Т. К. Винцюком[3] в 1968 для обработке речи (динамическое предыскажение шкалы) и Робертом А. Вагнером и Майклом Дж. Фишером[4] в 1974 для сопоставления строк.
Нидлман и Вунш сформулировали свою задачу в терминах максимизации похожести. Другая возможность заключается в минимизации редакционного расстояния между последовательностями, предложенной В. Левенштейном, однако было показано[5], что две эти задачи эквивалентны.
В современной терминологии «Нидлман — Вунш» относится к алгоритму выравнивания последовательностей квадратичному по времени для линейного или аффинного штрафа за разрыв.
Для улучшения этой статьи желательно: |
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .