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

редактировать
КлассВыравнивание последовательности
Худший случай производительность O (мин.) {\ displaystyle O (mn)}O (mn)
наихудший случай сложность пространства O (mn) {\ displaystyle O (mn)}O (mn)

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

Рисунок 1: Попарное выравнивание последовательностей Нидлмана-Вунша
Результаты: Последовательности Наилучшее выравнивание --------- --------------------- - GCATGCU GCATG-CU GCA-TGCU GCAT-GCU GATTACA G-ATTACA G-ATTACA G-ATTACA Интерпретация шага инициализации: крайний левый столбец на приведенном выше рисунке можно интерпретировать следующим образом (помещая «дескриптор» перед каждой последовательностью с аннотацией как + здесь): Выравнивание: + GCATGCU + GATTACA Score: 0 // Обработка совпадений, не выигрывает Выравнивание: + GCATGCU + GATTACA Score: 0 // 1 пробел, оценка −1 Выравнивание: + GCATGCU + GATTACA Score : 0 // 2 пропусков, оценка −2 Выравнивание: + GCATGCU + Оценка по GATTACA: 0 // 3 пропусков, оценка −3 Выравнивание: + GCATGCU + Оценка по GATTACA: 0 // 4 пропусков, оценка −4... То же самое можно сделать для самого верхнего ряда.

Содержание

  • 1 Введение
    • 1.1 Построение сетки
    • 1.2 Выбор системы подсчета очков
    • 1.3 Заполнение таблицы
    • 1.4 Отслеживание стрелки к исходной точке
  • 2 Системы подсчета очков
    • 2.1 Базовые схемы оценки
    • 2.2 Матрица сходства
    • 2.3 Штраф за пропуск
  • 3 Расширенное представление алгоритма
  • 4 Сложность
  • 5 Исторические заметки и разработка алгоритмов
  • 6 Инструменты глобального выравнивания с использованием Needleman – Wunsch алгоритм
  • 7 Приложения вне биоинформатики
    • 7.1 Компьютерное стереозрение
  • 8 См. также
  • 9 Ссылки
  • 10 Внешние ссылки

Введение

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

GCATGCU GATTACA

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

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

GCATGCU
G
A
T
T
A
C
A

Выбор системы подсчета очков

Затем решите, как оценивать каждую отдельную пару букв. Используя приведенный выше пример, одним из возможных кандидатов на выравнивание может быть: . 12345678. GCATG-CU. G-ATTACA.Буквы могут совпадать, не совпадать или совпадать с пробелом (удаление или вставка (indel )):

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

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

  • Соответствие: +1
  • Несоответствие или Indel: -1

Для приведенного выше примера оценка выравнивания будет равна 0: . GCATG-CU. G-ATTACA.

+ - ++ −− + - ->1 * 4 + (−1) * 4 = 0

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

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

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

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

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

GCATGCU
0−1−2−3−4−5−6−7
G−1
A−2
T−3
T−4
A−5
C−6
A−7

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

G
0−1
G−1X

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

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

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

G
0-1
G−11

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

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

GC
0−1−2
G−11X
A−2Y

X:

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

Y:

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

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

GC
0−1−2
G−110
A−20

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

TG
T11
A0X
  • Верх: (1) + (- 1) = (0)
  • Слева вверху: (1) + (- 1) = (0)
  • Слева: (0) + (- 1) = (−1)

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

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

Отслеживание стрелок назад к исходной точке

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

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

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

U → CU → GCU → -GCU → T-GCU → AT-GCU → CAT-GCU → GCAT-GCU A → CA → ACA → TACA → TTACA → ATTACA → -ATTACA → G-ATTACA ↓ (ветвь) → TGCU →... → TACA →...

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

Базовые схемы подсчета очков

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

  • Соответствие = 0
  • Indel = 1
  • Несоответствие = 1

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

  • Match = 0
  • Mismatch = 1
  • Indel = 10

Попробовать.

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

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

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

AGCT
A1-1-1-1
G-11-1-1
C-1-11-1
T-1-1-11

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

AGCT
A1−1−1−1
G−11−1−1
C−1−11−1
T−1−1−14

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

Штраф за пропуски

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

GAAAAAAT G - AAT

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

GAAAAAAT GAA- --- T

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

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

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

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

AGCT
A10−1−3−4
G−17−5−3
C−3−590
T−4−308

, тогда выравнивание:

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 (A, G) + S (C, T)
= −3 + 7 + 10 - (3 × 5) + 7 + ( −4) + 0 + (−1) + 0 = 1

Чтобы найти выравнивание с наивысшим баллом, выделяется двумерный массив (или матрица ) F.. Запись в строке i и столбце j обозначена здесь как F i j {\ displaystyle F_ {ij}}F_{ij}. Есть одна строка для каждого символа в последовательности A и один столбец для каждого символа в последовательности B. Таким образом, при выравнивании последовательностей размеров n и m объем используемой памяти находится в O (nm) {\ displaystyle O (nm)}O (нм) . Алгоритм Хиршберга хранит в памяти только подмножество массива и использует Θ (min {n, m}) {\ displaystyle \ Theta (\ min \ {n, m \})}\ Theta (\ min \ {n, m \}) пробел, но в остальном похож на Needleman-Wunsch (и по-прежнему требует O (нм) {\ displaystyle O (nm)}O (нм) time).

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

  • Основа:
F 0 j = d ∗ j {\ displaystyle F_ {0j} = d * j}F_ {0j} = d * j
F i 0 = d ∗ i {\ displaystyle F_ {i0} = d * i}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) {\ 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_ {ij} = \ max (F_ {i-1, j-1} + S (A_ {i}, B_ {j}), \; F_ {i, j-1} + d, \; F_ {i-1, j} + d)

Псевдо- поэтому код алгоритма вычисления матрицы F выглядит следующим образом:

d ← MismatchScore для i = 0 tolength (A) F (i, 0) ← d * i для j = 0 toдлина (B) F (0, j) ← d * j для i = 1 toдлина (A) для j = 1 tole ngth (B) {Match ← F (i − 1, j − 1) + S (A i, B j) Удалить ← F (i − 1, j) + d Insert ← F (i, j − 1) + d F (i, j) ← max (Match, Insert, Delete)}

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

AlignmentA ← "" AlignmentB ← "" i ← length (A) j ← длина (B) while (i>0 или j>0) {if (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 i ← i - 1 j ← j - 1} else if(i>0 и F (i, j) == F (i − 1, j) + d) {AlignmentA ← A i + AlignmentA AlignmentB ← «-» + AlignmentB i ← i - 1} else {AlignmentA ← "-" + AlignmentA AlignmentB ← B j + AlignmentB j ← j - 1}}

Сложность

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

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

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

Нидлман и Вунш подробно описывают свой алгоритм для случая, когда выравнивание наказывается только совпадениями и несовпадениями, а пропуски не имеют штрафа (d = 0). Исходная публикация 1970 года предлагает рекурсию F i j = max h < i, k < j { F h, j − 1 + S ( A i, B j), F i − 1, k + S ( A i, B j) } {\displaystyle F_{ij}=\max _{hF_ {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% сходства.

Инструменты глобального выравнивания с использованием алгоритма Needleman – Wunsch

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

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

Стереосогласование - важный шаг в процессе 3D-реконструкции из пары стереоизображений. Когда изображения были исправлены, можно провести аналогию между выравниванием последовательностей нуклеотидов и белков и сопоставлением пикселей, принадлежащих строкам сканирования, поскольку обе задачи направлены на установление оптимального соответствия между двумя строками символов.. «Правое» изображение стереопары можно рассматривать как видоизмененную версию «левого» изображения: шум и индивидуальная чувствительность камеры изменяют значения пикселей (т. Е. Замены символов); а другой угол обзора показывает ранее закрытые данные и вводит новые окклюзии (то есть вставку и удаление символов). Как следствие, незначительные модификации алгоритма Нидлмана – Вунша делают его пригодным для стерео сопоставления. Хотя характеристики с точки зрения точности не соответствуют современным требованиям, относительная простота алгоритма позволяет его реализовать на встроенных системах.

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

См. Также

Ссылки

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

Последняя правка сделана 2021-05-31 13:40:33
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте