Алгоритм Needleman-Wunsch представляет собой алгоритм , используемый в биоинформатики к ALIGN белка или нуклеотидных последовательностей. Это было одно из первых приложений динамического программирования для сравнения биологических последовательностей. Алгоритм был разработан Солом Б. Нидлманом и Кристианом Д. Вуншем и опубликован в 1970 году. [1] Алгоритм по существу делит большую проблему (например, полную последовательность) на серию более мелких задач и использует решения более мелких проблемы, чтобы найти оптимальное решение более крупной проблемы. [2] Его также иногда называют оптимальным алгоритмом сопоставления иметод глобального выравнивания . Алгоритм Нидлмана – Вунша до сих пор широко используется для оптимального глобального выравнивания, особенно когда качество глобального выравнивания имеет первостепенное значение. Алгоритм присваивает оценку каждому возможному выравниванию, и цель алгоритма - найти все возможные выравнивания, имеющие наивысший балл.
Класс | Выравнивание последовательности |
---|---|
Наихудшая производительность | |
Сложность пространства в наихудшем случае |
Вступление
Этот алгоритм можно использовать для любых двух строк . В этом руководстве в качестве примеров будут использоваться две небольшие последовательности ДНК, как показано на диаграмме:
GCATGCUГАТТАКА
Построение сетки
Сначала постройте сетку, подобную показанной на рисунке 1 выше. Начните первую строку в верхней части третьего столбца и начните вторую строку в начале третьей строки. Заполните остальные заголовки столбцов и строк, как показано на рисунке 1. В сетке еще не должно быть чисел.
грамм | C | А | Т | грамм | C | U | ||
---|---|---|---|---|---|---|---|---|
грамм | ||||||||
А | ||||||||
Т | ||||||||
Т | ||||||||
А | ||||||||
C | ||||||||
А |
Выбор системы подсчета очков
Затем решите, как оценивать каждую отдельную пару букв. Используя приведенный выше пример, одним из возможных кандидатов на выравнивание может быть:
12345678
GCATG-CU
G-ATTACA
Буквы могут совпадать, не совпадать или совпадать с пробелом (удаление или вставка ( отступ )):
- Совпадение: две буквы в текущем индексе совпадают.
- Несоответствие: две буквы в текущем индексе разные.
- Indel (INsertion или DELetion): лучшее выравнивание предполагает выравнивание одной буквы по пробелу в другой строке.
Каждому из этих сценариев присваивается балл, и сумма баллов всех пар является баллом всего кандидата на выравнивание. Существуют разные системы для выставления оценок; некоторые из них описаны в разделе « Системы подсчета очков » ниже. На данный момент будет использоваться система, используемая Needleman и Wunsch [1] :
- Матч: +1
- Несоответствие или несоответствие: -1
В приведенном выше примере оценка выравнивания будет равна 0:
GCATG-CU
G-ATTACA
+ - ++ −− + - -> 1 * 4 + (−1) * 4 = 0
Заполнение таблицы
Начните с нуля во второй строке второго столбца. Перемещайтесь по ячейкам строка за строкой, вычисляя балл для каждой ячейки. Оценка рассчитывается путем сравнения оценок ячеек, соседних с левой, верхней или верхней левой (диагональю) ячейки, и добавления соответствующей оценки для совпадения, несоответствия или отступа. Подсчитайте баллы кандидатов для каждой из трех возможностей:
- Путь от верхней или левой ячейки представляет собой пару отступов, поэтому возьмите баллы левой и верхней ячеек и добавьте баллы за отступы к каждой из них.
- Диагональный путь представляет совпадение / несоответствие, поэтому возьмите оценку левой верхней диагональной ячейки и добавьте оценку совпадения, если соответствующие основания (буквы) в строке и столбце совпадают, или оценку несоответствия, если они не совпадают.
Итоговая оценка для ячейки является наивысшей из трех оценок кандидата.
Поскольку для второй строки нет «верхних» или «верхних левых» ячеек, только существующая ячейка слева может использоваться для вычисления оценки каждой ячейки. Следовательно, -1 добавляется для каждого сдвига вправо, поскольку это представляет собой отступ от предыдущей оценки. Это приводит к тому, что первая строка равна 0, −1, −2, −3, −4, −5, −6, −7. То же самое относится к первому столбцу, поскольку можно использовать только существующий счет над каждой ячейкой. Таким образом, итоговая таблица выглядит так:
грамм | C | А | Т | грамм | C | U | ||
---|---|---|---|---|---|---|---|---|
0 | −1 | −2 | −3 | −4 | −5 | −6 | −7 | |
грамм | −1 | |||||||
А | −2 | |||||||
Т | −3 | |||||||
Т | −4 | |||||||
А | −5 | |||||||
C | −6 | |||||||
А | −7 |
Первый случай с существующими оценками во всех 3 направлениях - это пересечение наших первых букв (в данном случае G и G). Окружающие клетки ниже:
грамм | ||
---|---|---|
0 | −1 | |
грамм | −1 | Икс |
В этой ячейке есть три возможных суммы кандидатов:
- Сосед по диагонали в верхнем левом углу имеет счет 0. Соединение G и G является совпадением, поэтому добавьте счет для совпадения: 0 + 1 = 1.
- У верхнего соседа оценка −1, и перемещение оттуда представляет собой отступ, поэтому добавьте оценку для indel: (−1) + (−1) = (−2)
- Левый сосед также имеет оценку -1, представляет собой отступ и также дает (-2).
Самый высокий кандидат равен 1 и вводится в ячейку:
грамм | ||
---|---|---|
0 | −1 | |
грамм | −1 | 1 |
Также должна быть записана ячейка, которая дала кандидату наибольшее количество баллов. На завершенной диаграмме на рисунке 1 выше это представлено как стрелка от ячейки в строке и столбце 3 к ячейке в строке и столбце 2.
В следующем примере шаг по диагонали для X и Y представляет несоответствие:
грамм | C | ||
---|---|---|---|
0 | −1 | −2 | |
грамм | −1 | 1 | Икс |
А | −2 | Y |
ИКС:
- Вверху: (−2) + (- 1) = (−3)
- Слева: (+1) + (- 1) = (0)
- Вверху слева: (−1) + (- 1) = (−2)
Y:
- Сверху: (1) + (- 1) = (0)
- Слева: (−2) + (- 1) = (−3)
- Вверху слева: (−1) + (- 1) = (−2)
Для X и Y наивысший балл равен нулю:
грамм | C | ||
---|---|---|---|
0 | −1 | −2 | |
грамм | −1 | 1 | 0 |
А | −2 | 0 |
Наивысший балл кандидата может быть получен двумя или всеми соседними ячейками:
Т | грамм | |
---|---|---|
Т | 1 | 1 |
А | 0 | Икс |
- Сверху: (1) + (- 1) = (0)
- Вверху слева: (1) + (- 1) = (0)
- Слева: (0) + (- 1) = (−1)
В этом случае все направления, достигающие наивысшего балла кандидата, должны быть отмечены как возможные исходные ячейки на готовой диаграмме на рисунке 1, например, в ячейке в строке и столбце 7.
Заполнение таблицы таким образом дает оценки или всех возможных кандидатов на выравнивание, оценка в ячейке в правом нижнем углу представляет оценку выравнивания для наилучшего выравнивания.
Отслеживание стрелок назад к исходной точке
Отметьте путь от ячейки в правом нижнем углу до ячейки в левом верхнем углу, следуя направлению стрелок. На этом пути последовательность строится по следующим правилам:
- Диагональная стрелка представляет совпадение или несоответствие, поэтому буква столбца и буква строки исходной ячейки будут выровнены.
- Горизонтальная или вертикальная стрелка обозначает отступ. Горизонтальные стрелки выравнивают пробел ("-") с буквой строки ("боковая" последовательность), вертикальные стрелки выравнивают пробел с буквой столбца ("верхняя" последовательность).
- Если есть несколько стрелок для выбора, они представляют собой разветвление трасс. Если две или более ветки принадлежат путям от нижнего правого к верхнему левому углу ячейки, они одинаково жизнеспособны. В этом случае отметьте пути как отдельные кандидаты на выравнивание.
Следуя этим правилам, шаги для одного возможного кандидата на выравнивание на рисунке 1 следующие:
U → CU → GCU → -GCU → T-GCU → AT-GCU → CAT-GCU → GCAT-GCU A → CA → ACA → TACA → TTACA → ATTACA → -ATTACA → G-ATTACA ↓ (филиал) → ТГКУ → ... → TACA → ...
Системы подсчета очков
Базовые схемы подсчета очков
В простейших схемах подсчета очков просто указывается значение для каждого совпадения, несоответствия и отступа. В приведенном выше пошаговом руководстве используется match = 1, mismatch = −1, indel = −1. Таким образом, чем ниже балл совмещения, тем больше расстояние редактирования , для этой системы баллов требуется высокий балл. Другая система подсчета очков может быть:
- Матч = 0
- Indel = 1
- Несоответствие = 1
Для этой системы оценка выравнивания будет представлять собой расстояние редактирования между двумя строками. Для разных ситуаций могут быть разработаны разные системы подсчета очков, например, если пробелы считаются очень плохими для вашего выравнивания, вы можете использовать систему подсчета очков, которая сильно наказывает пробелы, например:
- Матч = 0
- Несоответствие = 1
- Indel = 10
Матрица подобия
Более сложные системы подсчета присваивают значения не только типу изменения, но также и буквам, которые участвуют. Например, совпадению между A и A может быть присвоено 1, а совпадению между T и T может быть присвоено 4. Здесь (при условии первой системы подсчета очков) большее значение придается совпадению Ts, чем As, то есть совпадению Ts. считается более важным для выравнивания. Это взвешивание, основанное на буквах, также применяется к несоответствиям.
Чтобы представить все возможные комбинации букв и их результирующие оценки, используется матрица подобия. Матрица подобия для самой базовой системы представлена как:
А | грамм | C | Т | |
---|---|---|---|---|
А | 1 | -1 | -1 | -1 |
грамм | -1 | 1 | -1 | -1 |
C | -1 | -1 | 1 | -1 |
Т | -1 | -1 | -1 | 1 |
Каждая оценка представляет собой переход от одной буквы, соответствующей ячейке, к другой. Следовательно, здесь представлены все возможные совпадения и удаления (для алфавита ACGT). Обратите внимание, что все совпадения идут по диагонали, также не нужно заполнять всю таблицу, только этот треугольник, потому что оценки взаимны. = (Оценка для A → C = Оценка для C → A). При реализации правила TT = 4 сверху получается следующая матрица подобия:
А | грамм | C | Т | |
---|---|---|---|---|
А | 1 | −1 | −1 | −1 |
грамм | −1 | 1 | −1 | −1 |
C | −1 | −1 | 1 | −1 |
Т | −1 | −1 | −1 | 4 |
Статистически построены разные скоринговые матрицы, которые придают вес различным действиям, подходящим для конкретного сценария. Наличие взвешенных оценочных матриц особенно важно при выравнивании последовательностей белков из-за различной частоты встречаемости различных аминокислот. Существует два широких семейства скоринговых матриц, каждая из которых имеет дополнительные изменения для конкретных сценариев:
Штраф за разрыв
При выравнивании последовательностей часто встречаются пробелы (т.е. инделки), иногда большие. С биологической точки зрения большой разрыв чаще возникает как одна большая делеция, чем как несколько отдельных делеций. Следовательно, две маленькие индели должны иметь худшую оценку, чем одна большая. Простой и распространенный способ сделать это - использовать большой начальный балл для новой отступы и меньший балл за разрыв для каждой буквы, которая расширяет отступ. Например, new-indel может стоить -5, а extension-indel может стоить -1. Таким образом происходит выравнивание, такое как:
GAAAAAATG - AAT
который имеет несколько одинаковых выравниваний, некоторые с несколькими небольшими выравниваниями теперь будут выравниваться как:
GAAAAAATGAA ---- T
или любое выравнивание с 4 длинными промежутками предпочтительнее, чем несколько небольших промежутков.
Расширенное представление алгоритма
Баллы для выровненных символов указываются с помощью матрицы сходства . Здесь S ( a , b ) - подобие символов a и b . Он использует линейный штраф за разрыв , здесь называемый d .
Например, если матрица подобия была
А | грамм | C | Т | |
---|---|---|---|---|
А | 10 | −1 | −3 | −4 |
грамм | −1 | 7 | −5 | −3 |
C | −3 | −5 | 9 | 0 |
Т | −4 | −3 | 0 | 8 |
затем выравнивание:
AGACTAGTTACCGA --- GACGT
со штрафом за пропуск -5, будет иметь следующий счет:
- S (A, C) + S (G, G) + S (A, A) + (3 × d ) + S (G, G) + S (T, A) + S (T, C) + S ( А, G) + S (С, Т)
- = −3 + 7 + 10 - (3 × 5) + 7 + (−4) + 0 + (−1) + 0 = 1
Чтобы найти выравнивание с наибольшим количеством очков, двумерный массив (или матрица ) F выделяются. Запись в строке i и столбце j обозначена здесь как. Существует одна строка для каждого символа в последовательности А , и один столбец для каждого символа в последовательности B . Таким образом, при выравнивании последовательностей размеров n и m объем используемой памяти равен. Алгоритм Хиршберга хранит в памяти только подмножество массива и использует пробел, но в остальном похож на Needleman-Wunsch (и по-прежнему требует время).
По мере продвижения алгоритма будет назначена оптимальная оценка для выравнивания первого символы в A и первомсимволы в B . Затем принцип оптимальности применяется следующим образом:
- Основа:
- Рекурсия, основанная на принципе оптимальности:
Таким образом, псевдокод алгоритма вычисления матрицы F выглядит так:
d ← Штраф за разрыв для i = 0 до длины (A) F (i, 0) ← d * iдля j = 0 до длины (B) F (0, j) ← d * jдля i = 1 до длины (A) для j = 1 до длины (B) { Match ← 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, Insert и Delete выше), чтобы увидеть, откуда оно взято. Если Match, то а также выровнены, если Delete, то выравнивается по пробелу, а если Insert, то выравнивается с зазором. (Как правило, несколько вариантов могут иметь одно и то же значение, что приводит к альтернативным оптимальным согласованиям.)
ВыравниваниеA ← ""ВыравниваниеB ← ""i ← длина (A)j ← length (B) while (i> 0 или j> 0){ если (i> 0 и j> 0 и F (i, j) == F (i − 1, j − 1) + S (A i , B j )) { ВыравниваниеA ← A i + ВыравниваниеA ВыравниваниеB ← B j + ВыравниваниеB я ← я - 1 j ← j - 1 } иначе, если (i> 0 и F (i, j) == F (i − 1, j) + d) { ВыравниваниеA ← A i + ВыравниваниеA ВыравниваниеB ← «-» + ВыравниваниеB я ← я - 1 } еще { ВыравниваниеA ← «-» + ВыравниваниеA ВыравниваниеB ← B j + ВыравниваниеB j ← j - 1 }}
Сложность
Расчет счета для каждой ячейки в таблице есть операция. Таким образом, временная сложность алгоритма для двух последовательностей длины а также является . [3] Было показано, что можно сократить время работы допо методу четырех русских . [3] [4] Поскольку алгоритм заполняет таблица сложность пространства . [3]
Исторические заметки и разработка алгоритмов
Первоначальная цель алгоритма, описанного Нидлманом и Вуншем, состояла в том, чтобы найти сходство в аминокислотных последовательностях двух белков. [1]
Нидлман и Вунш подробно описывают свой алгоритм для случая, когда выравнивание наказывается только совпадениями и несоответствиями, а за пропуски штраф не взимается ( d = 0). Исходная публикация 1970 года предполагает рекурсию .
Соответствующий алгоритм динамического программирования занимает кубическое время. В документе также указывается, что рекурсия может учитывать произвольные формулы штрафов за пробелы:
Фактор штрафа, число, вычитаемое для каждого пробела, может быть оценено как препятствие для разрешения пробела. Штрафной коэффициент может зависеть от размера и / или направления зазора. [стр. 444]
Более совершенный алгоритм динамического программирования с квадратичным временем выполнения для той же задачи (без штрафа за пропуски ) был впервые представлен [5] Дэвидом Санкоффом в 1972 году. Подобные квадратичные алгоритмы были открыты независимо Т.К. Винцюком [6] в 1968 году для обработки речи ( «деформация времени» ), а также Роберт А. Вагнер и Майкл Дж. Фишер [7] в 1974 году для сопоставления строк.
Нидлман и Вунш сформулировали свою проблему в терминах максимального сходства. Другая возможность - минимизировать расстояние редактирования между последовательностями, введенное Владимиром Левенштейном . Питер Х. Селлерс в 1974 г. показал [8], что эти две задачи эквивалентны.
Алгоритм Нидлмана – Вунша до сих пор широко используется для оптимального глобального выравнивания , особенно когда качество глобального выравнивания имеет первостепенное значение. Однако алгоритм является дорогостоящим по времени и пространству, он пропорционален произведению длины двух последовательностей и, следовательно, не подходит для длинных последовательностей.
Недавние разработки были сосредоточены на улучшении временных и пространственных затрат алгоритма при сохранении качества. Например, в 2013 году алгоритм быстрого оптимального глобального выравнивания последовательностей (FOGSAA) [9] предложил выравнивание нуклеотидных / белковых последовательностей быстрее, чем другие оптимальные методы глобального выравнивания, включая алгоритм Нидлмана – Вунша. В документе утверждается, что по сравнению с алгоритмом Нидлмана – Вунша, FOGSAA обеспечивает выигрыш во времени на 70–90% для очень сходных нуклеотидных последовательностей (с подобием> 80%) и 54–70% для последовательностей, имеющих 30–80% сходства.
Приложения за пределами биоинформатики
Компьютерное стереозрение
Стереосогласование - важный шаг в процессе 3D-реконструкции из пары стереоизображений. Когда изображения были исправлены, можно провести аналогию между выравниванием последовательностей нуклеотидов и белков и сопоставлением пикселей, принадлежащих строкам сканирования , поскольку обе задачи направлены на установление оптимального соответствия между двумя строками символов. «Правое» изображение стереопары можно рассматривать как видоизмененную версию «левого» изображения: шум и индивидуальная чувствительность камеры изменяют значения пикселей (т. Е. Замены символов); а другой угол обзора показывает ранее закрытые данные и вводит новые окклюзии (например, вставку и удаление символов). Как следствие, незначительные модификации алгоритма Нидлмана – Вунша делают его пригодным для стерео сопоставления. [10] Хотя характеристики с точки зрения точности не соответствуют современным требованиям, относительная простота алгоритма позволяет реализовать его во встроенных системах . [11]
Хотя во многих приложениях исправление изображения может выполняться, например, с помощью обратной засечки или калибровки камеры , иногда это невозможно или непрактично, поскольку вычислительные затраты на точные модели выпрямления запрещают их использование в приложениях реального времени . Более того, ни одна из этих моделей не подходит, когда объектив камеры показывает неожиданные искажения , например, вызванные каплями дождя, защитными кожухами или пылью. Расширяя алгоритм Нидлмана – Вунша, линия на «левом» изображении может быть связана с кривой на «правом» изображении путем нахождения совмещения с наивысшим баллом в трехмерном массиве (или матрице). Эксперименты показали, что такое расширение позволяет плотное совпадение пикселей между неректированными или искаженными изображениями. [12]
Смотрите также
- Алгоритм Вагнера – Фишера
- Алгоритм Смита – Уотермана
- Последовательный майнинг
- Расстояние Левенштейна
- Динамическое искажение времени
- Выравнивание последовательности
Рекомендации
- ^ a b c Нидлман, Сол Б. и Вунш, Кристиан Д. (1970). «Общий метод, применимый к поиску сходства в аминокислотной последовательности двух белков». Журнал молекулярной биологии . 48 (3): 443–53. DOI : 10.1016 / 0022-2836 (70) 90057-4 . PMID 5420325 .
- ^ «биоинформатика» . Проверено 10 сентября 2014 года .
- ^ а б в Винг-кин., Сун (2010). Алгоритмы в биоинформатике: практическое введение . Бока-Ратон: Chapman & Hall / CRC Press. С. 34–35. ISBN 9781420070330. OCLC 429634761 .
- ^ Масек, Уильям; Патерсон, Майкл (февраль 1980). «Более быстрый алгоритм вычисления расстояний редактирования строк». Журнал компьютерных и системных наук . 20 : 18–31. DOI : 10.1016 / 0022-0000 (80) 90002-1 .
- ^ Санкофф Д (1972). «Соответствующие последовательности при ограничениях на удаление / вставку» . Труды Национальной академии наук США . 69 (1): 4–6. Bibcode : 1972PNAS ... 69 .... 4S . DOI : 10.1073 / pnas.69.1.4 . PMC 427531 . PMID 4500555 .
- ^ Винцюк Т.К. (1968). «Распознавание речи с помощью динамического программирования». Кибернетика . 4 : 81–88. DOI : 10.1007 / BF01074755 . S2CID 123081024 .
- ^ Вагнер Р.А., Фишер М.Дж. (1974). «Проблема исправления строки в строку». Журнал ACM . 21 (1): 168–173. DOI : 10.1145 / 321796.321811 . S2CID 13381535 .
- ^ Продавцы PH (1974). «К теории и вычислению эволюционных расстояний». Журнал SIAM по прикладной математике . 26 (4): 787–793. DOI : 10.1137 / 0126070 .
- ^ Чакраборти, Ангана; Bandyopadhyay, Sanghamitra (29 апреля 2013 г.). «FOGSAA: алгоритм быстрого оптимального глобального выравнивания последовательности» . Научные отчеты . 3 : 1746. Bibcode : 2013NatSR ... 3E1746C . DOI : 10.1038 / srep01746 . PMC 3638164 . PMID 23624407 .
- ^ Dieny Р., Thevenon J., Мартинес-дель-Ринкон J., Nebel Ж.-К. (2011) « Алгоритм, вдохновленный биоинформатикой для стерео соответствия ». Международная конференция по теории и приложениям компьютерного зрения, 5–7 марта, Виламура, Алгарве, Португалия.
- ^ Мадео С., Пелличча Р., Сальвадори К., Мартинес-дель-Ринкон Дж., Небель Х.-К. (2014) «Оптимизированная реализация стереозрения для встраиваемых систем: приложение к изображениям RGB и инфракрасным» . Журнал обработки изображений в реальном времени ».
- ^ Тевенон, Дж; Мартинес-дель-Ринкон, Дж; Dieny, R; Небель, JC (2012). Плотное сопоставление пикселей между не исправленными и искаженными изображениями с помощью динамического программирования . Международная конференция по теории и приложениям компьютерного зрения. Рим.
Внешние ссылки
- NW-align: программа выравнивания последовательности белка с последовательностью по алгоритму Нидлмана-Вунша (онлайн-сервер и исходный код)
- Параллельный алгоритм Нидлмана-Вунша для сетки - реализация Тахиром Навидом, Имитазом Саидом Сиддики и Шафтабом Ахмедом - Университет Бахрии
- Алгоритм Нидлмана-Вунша как код Haskell
- Живая демонстрация Needleman – Wunsch на основе Javascript
- Интерактивное визуальное объяснение алгоритма Нидлмана-Вунша на основе Javascript
- BABA - апплет (с исходником), наглядно объясняющий алгоритм.
- Четкое объяснение NW и его применения для выравнивания последовательностей
- Методы выравнивания последовательностей в блоге о технологиях
- Пакет Biostrings R, реализующий, среди прочего, алгоритм Нидлмана – Вунша
- Алгоритм Нидлмана-Вунша как код Haxe