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

Рисунок 1: Парное выравнивание последовательностей Нидлмана-Вунша
Сорт	Выравнивание последовательности
Худшая производительность	$O(mn)$
Наихудшая пространственная сложность	$O(mn)$

Алгоритм Нидлмана-Вунша — это алгоритм, используемый в биоинформатике для выравнивания белковых или нуклеотидных последовательностей. Это было одно из первых применений динамического программирования для сравнения биологических последовательностей. Алгоритм был разработан Солом Б. Нидлманом и Кристианом Д. Вуншем и опубликован в 1970 году. Алгоритм по существу делит большую проблему (например, полную последовательность) на ряд более мелких проблем и использует решения меньших проблем для поиска оптимального решения более крупной проблемы. Его также иногда называют алгоритмом оптимального сопоставления и методом глобального выравнивания . Алгоритм Нидлмана-Вунша до сих пор широко используется для оптимального глобального выравнивания, особенно когда качество глобального выравнивания имеет первостепенное значение. Алгоритм присваивает оценку каждому возможному выравниванию, и цель алгоритма — найти все возможные выравнивания, имеющие наивысший балл.

Введение

Этот алгоритм можно использовать для любых двух строк . В этом руководстве в качестве примеров будут использоваться две небольшие последовательности ДНК , как показано на рисунке 1:

GCATGCG
GATTACA

Построение сетки

Сначала постройте сетку, такую ​​как показана на рисунке 1 выше. Начните первую строку с верха третьего столбца, а вторую строку начните с начала третьей строки. Заполните остальные заголовки столбцов и строк, как показано на рисунке 1. В сетке пока не должно быть чисел.

		Г	С	А	Т	Г	С	Г
Г
А
Т
Т
А
С
А

Выбор системы начисления баллов

Далее решите, как оценить каждую отдельную пару букв. Используя приведенный выше пример, одним из возможных кандидатов на выравнивание может быть:

12345678
GCATG-CG
G-ATTACA

Буквы могут совпадать, не совпадать или совпадать с пробелом (удаление или вставка ( indel )):

• Совпадение: две буквы в текущем индексе одинаковы.
• Несоответствие: две буквы в текущем индексе разные.
• Indel (вставка или удаление): лучшее выравнивание предполагает выравнивание одной буквы по пробелу в другой строке.

Каждому из этих сценариев присваивается балл, а сумма баллов всех пар представляет собой балл всего кандидата на согласование. Существуют разные системы выставления оценок; некоторые из них описаны в разделе «Системы подсчета очков» ниже. На данный момент система, используемая Нидлманом и Вуншем, будет использоваться:

• Матч: +1
• Несоответствие или неточность: −1

В приведенном выше примере оценка выравнивания будет равна 0:

GCATG-CG
G-ATTACA
+−++−−+− −> 1*4 + (−1)*4 = 0

Заполнение таблицы

Начните с нуля в первой строке первого столбца (не считая клеток, содержащих нуклеотиды). Перемещайтесь по ячейкам ряд за рядом, подсчитывая баллы для каждой ячейки. Оценка рассчитывается путем сравнения оценок ячеек, соседних с левой, верхней или верхней левой (диагональю) ячейки, и добавления соответствующего балла за совпадение, несовпадение или удаление. Возьмите максимум баллов кандидата для каждой из трех возможностей:

• Путь от верхней или левой ячейки представляет собой пару indel, поэтому возьмите оценки левой и верхней ячеек и добавьте оценку indel к каждой из них.
• Диагональный путь представляет собой совпадение/несовпадение, поэтому возьмите оценку верхней левой диагональной ячейки и добавьте оценку за совпадение, если соответствующие основания (буквы) в строке и столбце совпадают, или оценку за несовпадение, если они не совпадают.

Итоговая оценка ячейки является самой высокой из трех возможных оценок.

Учитывая, что для первой строки нет «верхних» или «верхних левых» ячеек, для расчета оценки каждой ячейки можно использовать только существующую ячейку слева. Следовательно, -1 добавляется для каждого сдвига вправо, поскольку это представляет собой отступ от предыдущего балла. В результате первая строка будет равна 0, -1, -2, -3, -4, -5, -6, -7. То же самое относится и к первому столбцу, поскольку можно использовать только существующую оценку над каждой ячейкой. Таким образом, результирующая таблица:

		Г	С	А	Т	Г	С	Г
	0	−1	−2	−3	−4	−5	−6	−7
Г	−1
А	−2
Т	−3
Т	−4
А	−5
С	−6
А	−7

Первый случай с существующими оценками по всем 3 направлениям — это пересечение наших первых букв (в данном случае G и G). Окружающие ячейки приведены ниже:

		Г
	0	−1
Г	−1	Х

Эта ячейка имеет три возможных суммы-кандидата:

• Сосед по диагонали сверху слева имеет оценку 0. Пара G и G совпадает, поэтому сложите баллы за совпадение: 0+1 = 1.
• Верхний сосед имеет оценку -1, и перемещение оттуда представляет собой отступ, поэтому добавьте оценку за отступ: (-1) + (-1) = (-2)
• Левый сосед также имеет оценку -1, представляет собой индел и также выдает (-2).

Самый высокий кандидат равен 1 и вводится в ячейку:

		Г
	0	−1
Г	−1	1

Ячейку, которая дала наивысший балл кандидату, также необходимо записать. На завершенной диаграмме на рисунке 1 выше это представлено стрелкой от ячейки в строке и столбце 2 к ячейке в строке и столбце 1.

В следующем примере шаг по диагонали для X и Y представляет собой несоответствие:

		Г	С
	0	−1	−2
Г	−1	1	Х
А	−2	И

Х:

• Вверху: (−2)+(−1) = (−3)
• Слева: (+1)+(−1) = (0)
• Вверху слева: (−1)+(−1) = (−2)

И:

• Вверху: (1)+(−1) = (0)
• Слева: (−2)+(−1) = (−3)
• Вверху слева: (−1)+(−1) = (−2)

И для X, и для Y наивысший балл равен нулю:

		Г	С
	0	−1	−2
Г	−1	1	0
А	−2	0

Наивысший балл-кандидат может быть достигнут двумя соседними ячейками:

	Т	Г
Т	1	1
А	0	Х

• Вверху: (1)+(−1) = (0)
• Вверху слева: (1)+(−1) = (0)
• Слева: (0)+(−1) = (−1)

В этом случае все направления, достигшие наивысшего балла-кандидата, должны быть отмечены как возможные исходные ячейки на готовой диаграмме на рисунке 1, например, в ячейке в строке и столбце 6.

Заполнение таблицы таким образом дает оценки всех возможных кандидатов на выравнивание. Оценка в ячейке в правом нижнем углу представляет собой оценку выравнивания для наилучшего выравнивания.

Отслеживание стрелок обратно в исходное положение

Отметьте путь от ячейки в правом нижнем углу обратно к ячейке в левом верхнем углу, следуя направлению стрелок. Из этого пути последовательность строится по следующим правилам:

• Диагональная стрелка обозначает совпадение или несовпадение, поэтому буква столбца и буква строки исходной ячейки совпадут.
• Горизонтальная или вертикальная стрелка представляет собой интервал. Вертикальные стрелки выравнивают пробел («-») по букве строки («боковая» последовательность), горизонтальные стрелки выравнивают пробел по букве столбца («верхняя» последовательность).
• Если на выбор предлагается несколько стрелок, они представляют собой разветвление трасс. Если две или более ветвей принадлежат путям от нижней правой до верхней левой ячейки, они являются одинаково жизнеспособными выравниваниями. В этом случае обратите внимание на пути как на отдельные кандидаты на выравнивание.

Следуя этим правилам, шаги для одного возможного кандидата на выравнивание, показанного на рисунке 1, следующие:

G → CG → GCG → -GCG → T-GCG → AT-GCG → CAT-GCG → GCAT-GCG
A → CA → ACA → TACA → TTACA → ATTACA → -ATTACA → G-ATTACA
             ↓
    (branch) → TGCG → -TGCG → ...
             → TACA → TTACA → ...

Системы подсчета очков

Основные схемы начисления очков

Простейшие схемы подсчета очков просто дают значение для каждого совпадения, несоответствия и удаления. В приведенном выше пошаговом руководстве используются match = 1, несоответствие = −1, indel = −1. Таким образом, чем ниже показатель выравнивания, тем больше расстояние редактирования . Для этой системы оценки требуется высокий балл. Другая система оценки может быть такой:

• Матч = 0
• Индел = -1
• Несоответствие = -1

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

• Матч = 1
• Индел = -10
• Несоответствие = -1

Матрица сходства

Более сложные системы оценки присваивают значения не только типу изменения, но и участвующим в нем буквам. Например, совпадению между A и A может быть присвоено 1, а совпадению между T и T может быть присвоено 4. Здесь (предполагая первую систему оценки) большее значение придается совпадению Ts, чем совпадению As, т. е. совпадению Ts. считается более значимым для выравнивания. Это взвешивание, основанное на буквах, также применимо к несоответствиям.

Чтобы представить все возможные комбинации букв и их итоговые оценки, используется матрица сходства. Матрица подобия для самой базовой системы представлена ​​как:

	А	Г	С	Т
А	1	−1	−1	−1
Г	−1	1	−1	−1
С	−1	−1	1	−1
Т	−1	−1	−1	1

Каждая оценка представляет собой переход от одной буквы, которой соответствует ячейка, к другой. Следовательно, это представляет все возможные совпадения и несоответствия (для алфавита ACGT). Обратите внимание, что все совпадения идут по диагонали, также не всю таблицу нужно заполнять, только этот треугольник, потому что оценки обратные.= (Оценка за А → С = Оценка за С → А). При реализации правила TT = 4 сверху получается следующая матрица подобия:

	А	Г	С	Т
А	1	−1	−1	−1
Г	−1	1	−1	−1
С	−1	−1	1	−1
Т	−1	−1	−1	4

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

• ПАМ
• ВЗОРВАТЬ

Штраф за разрыв

При выравнивании последовательностей часто возникают пробелы (т.е. вставки), иногда большие. С биологической точки зрения большой разрыв с большей вероятностью возникнет в виде одной большой делеции, а не нескольких одиночных делеций. Следовательно, два маленьких инделя должны иметь худший балл, чем один большой. Простой и распространенный способ сделать это — использовать большую оценку начала пробела для новой вставки и меньшую оценку расширения пробела для каждой буквы, которая расширяет вставку. Например, new-indel может стоить -5, а Extend-indel может стоить -1. Таким образом, происходит такое выравнивание, как:

GAAAAAAT
G--A-A-T

который имеет несколько одинаковых выравниваний, некоторые из них с несколькими небольшими выравниваниями теперь будут выравниваться как:

GAAAAAAT
GAA----T

или любое выравнивание с длинным промежутком 4, предпочтительнее нескольких маленьких промежутков.

Расширенное представление алгоритма

Оценки для выровненных символов определяются матрицей сходства . Здесь S ( a , b ) — сходство символов a и b . линейный Он использует штраф за зазор , здесь называемый d .

Например, если матрица сходства была

	А	Г	С	Т
А	10	−1	−3	−4
Г	−1	7	−5	−3
С	−3	−5	9	0
Т	−4	−3	0	8

тогда расклад:

AGACTAGTTAC
CGA---GACGT

со штрафом за пробел -5, будет иметь следующий счет:

S (A,C) + S (G,G) + S (A,A) + (3 × d ) + S (G,G) + S (T,A) + S (T,C) + S ( А,Г) + С (С,Т)

= −3 + 7 + 10 − (3 × 5) + 7 + (−4) + 0 + (−1) + 0 = 1

двумерный массив (или матрица ) F. Для нахождения выравнивания с наивысшим баллом выделяется Запись в строке i и столбце j обозначается здесь как $F_{ij}$. имеется одна строка Для каждого символа в последовательности A , а для каждого символа в последовательности B — один столбец . Таким образом, при выравнивании последовательностей размеров n и m объём используемой памяти составляет $O(nm)$. Алгоритм Хиршберга хранит в памяти только часть массива и использует $\Theta (\min\{n,m\})$ пространство, но в остальном похож на метод Нидлмана-Вунша (и все еще требует $O(nm)$ время).

По мере развития алгоритма $F_{ij}$ будет присвоен оптимальный балл за выравнивание первого $i=0,\dotsc ,n$ символы в A и первом $j=0,\dotsc ,m$ персонажи В. ​ Тогда принцип оптимальности применяется следующим образом:

• Основа:

$F_{0j}=d*j$

$F_{i0}=d*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 выглядит следующим образом:

d ← Gap penalty score
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_{nm}$ дает максимальный балл среди всех возможных раскладов. Чтобы вычислить выравнивание, которое действительно дает этот балл, вы начинаете с нижней правой ячейки и сравниваете значение с тремя возможными источниками (Сопоставить, Вставить и Удалить выше), чтобы увидеть, из чего оно получено. Если совпадение, то $A_{i}$ и $B_{j}$ выровнены, если Удалить, то $A_{i}$ выравнивается по пробелу, а если Вставить, то $B_{j}$ совпадает с зазором. (Как правило, несколько вариантов могут иметь одно и то же значение, что приводит к альтернативным оптимальным выравниваниям.)

AlignmentA ← ""
AlignmentB ← ""
i ← length(A)
j ← length(B)
while (i > 0 or j > 0)
{
    if (i > 0 and j > 0 and F(i, j) == F(i−1, j−1) + S(Ai, Bj))
    {
        AlignmentA ← Ai + AlignmentA
        AlignmentB ← Bj + AlignmentB
        i ← i − 1
        j ← j − 1
    }
    else if (i > 0 and F(i, j) == F(i−1, j) + d)
    {
        AlignmentA ← Ai + AlignmentA
        AlignmentB ← "−" + AlignmentB
        i ← i − 1
    }
    else
    {
        AlignmentA ← "−" + AlignmentA
        AlignmentB ← Bj + AlignmentB
        j ← j − 1
    }
}

Сложность

Подсчет очков $F_{ij}$ для каждой ячейки таблицы есть $O(1)$ операция. Таким образом, временная сложность алгоритма для двух последовательностей длины $n$ и $m$ является $O(mn)$. Было показано, что можно улучшить время работы, чтобы $O(mn/\log n)$ используя метод четырёх русских . Поскольку алгоритм заполняет $n\times m$ таблица, сложность пространства $O(mn).$

Исторические заметки и разработка алгоритма

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

Нидлман и Вунш описывают свой алгоритм явно для случая, когда за выравнивание наказываются только совпадения и несовпадения, а за пробелы штрафа нет ( d =0). Оригинальная публикация 1970 года предполагает рекурсию. $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})\}$.

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

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

Позже был представлен лучший алгоритм динамического программирования с квадратичным временем выполнения для той же задачи (без штрафа за пропуск). Дэвид Санкофф в 1972 году. Подобные алгоритмы квадратичного времени были открыты независимо. Т.К. Винцюк в 1968 году для обработки речи ( «искажение времени» ), Роберт А. Вагнер и Майкл Дж. Фишер. в 1974 году для сопоставления строк.

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

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

Недавние разработки были сосредоточены на сокращении временных и пространственных затрат алгоритма при сохранении качества. Например, в 2013 году был разработан алгоритм быстрого оптимального глобального выравнивания последовательностей (FOGSAA), предложили выравнивание нуклеотидных/белковых последовательностей быстрее, чем другие методы оптимального глобального выравнивания, включая алгоритм Нидлмана-Вунша. В документе утверждается, что по сравнению с алгоритмом Нидлмана-Вунша FOGSAA обеспечивает выигрыш во времени 70–90% для очень похожих нуклеотидных последовательностей (со сходством> 80%) и 54–70% для последовательностей, имеющих сходство 30–80%.

Приложения вне биоинформатики

Компьютерное стереозрение

Основная статья: Компьютерное стереозрение

Стереосопоставление — важный шаг в процессе 3D-реконструкции пары стереоизображений. После исправления изображений можно провести аналогию между выравниванием нуклеотидных и белковых последовательностей и сопоставлением пикселей, принадлежащих линиям сканирования , поскольку обе задачи направлены на установление оптимального соответствия между двумя строками символов.

Хотя во многих приложениях исправление изображения может быть выполнено, например, путем обратной засечки или калибровки камеры , иногда это невозможно или непрактично, поскольку вычислительные затраты на точные модели исправления не позволяют их использовать в приложениях реального времени . Более того, ни одна из этих моделей не подходит, когда объектив камеры демонстрирует неожиданные искажения , например, вызванные каплями дождя, погодозащитными чехлами или пылью. Расширяя алгоритм Нидлмана-Вунша, линия на «левом» изображении может быть связана с кривой на «правом» изображении путем нахождения выравнивания с наивысшим баллом в трехмерном массиве (или матрице). Эксперименты показали, что такое расширение обеспечивает плотное сопоставление пикселей между неисправленными или искаженными изображениями.

См. также

• Алгоритм Вагнера-Фишера
• Алгоритм Смита – Уотермана
• Последовательный майнинг
• Расстояние Левенштейна
• Динамическое искажение времени
• Выравнивание последовательности

Внешние ссылки

• NW-align: программа выравнивания белковых последовательностей с помощью алгоритма Нидлмана-Вунша (онлайн-сервер и исходный код)
• Живая демо-версия Нидлмана – Вунша на основе Javascript.
• Интерактивное визуальное объяснение алгоритма Нидлмана-Вунша на основе Javascript.
• Методы выравнивания последовательностей в технологическом блоге
• Пакет Biostrings R, реализующий, среди прочего, алгоритм Нидлмана-Вунша