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

Метод выравнивания биологических последовательностей

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

Введение

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

GCATGCGГАТТАКА

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

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

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

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

12345678GCATG-CGГ-АТТАКА

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

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

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

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

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

GCATG-CGГ-АТТАКА+−++−−+− −> 1*4 + (−1)*4 = 0

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

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

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

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

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

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

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

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

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

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

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

ИКС:

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

Ю:

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

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

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

• Вверху: (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 ↓ (ветвь) → ТГКГ → -ТГКГ → ... → ТАСА → ТТАСА → ...

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

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

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

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

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

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

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

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

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

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

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

• ПАМ
• БЛОСУМ

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

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

ГААААААТГ--ААТ

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

ГААААААТГАА----Т

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

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

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

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

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

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

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

• Основа:

${\displaystyle F_{0j}=d*j}$

${\displaystyle F_{i0}=d*i}$

• Рекурсия, основанная на принципе оптимальности:

${\displaystyle 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 ← Штраф за пропуск для i = 0 к  длине (A) F(i,0) ← d * iдля j = 0 до  длины (B) F(0,j) ← d * jдля i = 1 до  длины (A) для j = 1 до  длины (B) { Соответствие ← F(i-1, j-1) + S(A i , B j ) Удалить ← F(i−1, j) + d Вставить ← F(i, j−1) + d F(i,j) ← max (Сопоставить, Вставить, Удалить) }

После вычисления матрицы F запись дает максимальную оценку среди всех возможных выравниваний. Чтобы вычислить выравнивание, которое фактически дает этот балл, вы начинаете с нижней правой ячейки и сравниваете значение с тремя возможными источниками (Сопоставить, Вставить и Удалить выше), чтобы увидеть, из чего оно получено. Если Match, то и выравниваются, если Удалить, то выравнивается по пробелу, а если Вставить, то выравнивается по пробелу. (Как правило, несколько вариантов могут иметь одно и то же значение, что приводит к альтернативным оптимальным выравниваниям.) ${\displaystyle F_{nm}}$ ${\displaystyle A_{i}}$ ${\displaystyle B_{j}}$ ${\displaystyle A_{i}}$ ${\displaystyle B_{j}}$

ВыравниваниеA ← ""ВыравниваниеB ← ""я ← длина (А)j ← длина (B) , пока (i > 0 или j > 0){ если (i > 0 и j > 0 и F(i, j) == F(i−1, j−1) + S(A i , B j )) { AlignmentA ← A i + AlignmentA AlignmentB ← B j + AlignmentB я ← я - 1 j ← j - 1 } иначе  , если (i > 0 и F(i, j) == F(i−1, j) + d) { AlignmentA ← A i + AlignmentA AlignmentB ← "-" + AlignmentB я ← я - 1 } еще { AlignmentA ← «-» + AlignmentA ВыравниваниеB ← B j + AlignmentB j ← j - 1 }}

Сложность

Вычисление баллов для каждой ячейки таблицы — это операция. Таким образом, временная сложность алгоритма для двух последовательностей длины и равна . ^[3] Было показано, что можно улучшить время бега, используя « Метод четырех русских» . ^{[3] [4]} Поскольку алгоритм заполняет таблицу, пространственная сложность равна ^[3] ${\displaystyle F_{ij}}$ ${\displaystyle O(1)}$ ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle O(mn)}$ ${\displaystyle O(mn/\log n)}$ ${\displaystyle n\times m}$ ${\displaystyle O(mn).}$

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

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

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

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

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

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

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

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

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

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

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

Смотрите также

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

Рекомендации

1. Нидлман, Сол Б. и Вунш, Кристиан Д. (1970). «Общий метод, применимый для поиска сходства в аминокислотной последовательности двух белков». Журнал молекулярной биологии . 48 (3): 443–53. дои : 10.1016/0022-2836(70)90057-4. ПМИД  5420325.
2. «Биоинформатика» . Проверено 10 сентября 2014 г.
3. Wing-Kin., Сун (2010). Алгоритмы в биоинформатике: практическое введение . Бока-Ратон: Chapman & Hall/CRC Press. стр. 34–35. ISBN 9781420070330. ОСЛК  429634761.
4. Масек, Уильям; Патерсон, Майкл (февраль 1980 г.). «Более быстрый алгоритм расчета расстояний редактирования строк». Журнал компьютерных и системных наук . 20 :18–31. дои : 10.1016/0022-0000(80)90002-1 .
5. Санкофф Д (1972). «Сопоставление последовательностей при ограничениях удаления/вставки». Труды Национальной академии наук США . 69 (1): 4–6. Бибкод : 1972PNAS...69....4S. дои : 10.1073/pnas.69.1.4 . ПМЦ 427531 . ПМИД  4500555. 
6. Винцюк Т.К. (1968). «Речевая дискриминация с помощью динамического программирования». Кибернетика . 4 : 81–88. дои : 10.1007/BF01074755. S2CID  123081024.
7. Вагнер Р.А., Фишер М.Дж. (1974). «Проблема построчной коррекции». Журнал АКМ . 21 (1): 168–173. дои : 10.1145/321796.321811 . S2CID  13381535.
8. Селлерс PH (1974). «К теории и расчету эволюционных расстояний». SIAM Journal по прикладной математике . 26 (4): 787–793. дои : 10.1137/0126070.
9. Чакраборти, Ангана; Бандйопадхьяй, Сангамитра (29 апреля 2013 г.). «FOGSAA: алгоритм быстрого оптимального глобального выравнивания последовательностей». Научные отчеты . 3 : 1746. Бибкод : 2013NatSR...3E1746C. дои : 10.1038/srep01746. ПМЦ 3638164 . ПМИД  23624407. 
10. Тевенон, Дж; Мартинес-дель-Ринкон, Дж; Дьени, Р; Небель, Дж. К. (2012). Плотное сопоставление пикселей между неисправленными и искаженными изображениями с использованием динамического программирования. Международная конференция по теории и приложениям компьютерного зрения. Рим.

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

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