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

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

История

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

Публикация алгоритма в журнале Journal of Molecular Biology произвела революцию в области сравнительной геномики. Впервые стало возможным автоматически и с гарантированной точностью находить наилучшее выравнивание двух последовательностей, что позволило исследователям изучать эволюционные взаимосвязи, выявлять функциональные участки в белках и генах, а также предсказывать структуру белков. Впоследствии алгоритм был адаптирован для локального выравнивания (алгоритм Смита — Уотермана, 1981) и для множественного выравнивания (например, ClustalW).

Постановка задачи

Задача глобального выравнивания заключается в том, чтобы найти такую последовательность операций (вставок, делеций и замен), которая преобразует одну строку в другую, максимизируя общую «оценку» (score) выравнивания. Оценка определяется на основе матрицы замен (например, BLOSUM62 для белков или единичная матрица для нуклеотидов) и штрафа за введение гэпа (пробела). Гэп — это символ «-», который вставляется в одну из последовательностей, чтобы компенсировать вставку или делецию в другой.

Формально, для двух последовательностей \( A = a_1 a_2 \ldots a_n \) и \( B = b_1 b_2 \ldots b_m \) алгоритм находит выравнивание, которое включает все символы \( A \) и \( B \) (возможно, с гэпами) и максимизирует сумму:

• \( s(a_i, b_j) \) — вес замены символа \( a_i \) на \( b_j \) (обычно положительный для совпадений, отрицательный для несовпадений);
• \( w \) — штраф за открытие гэпа (часто отрицательный);
• \( w \) — штраф за продолжение гэпа (в простейшем случае — фиксированный штраф за каждый гэп).

Принцип работы

Алгоритм Нидлмана — Вунша состоит из трёх этапов: инициализация, рекуррентное заполнение матрицы и обратный ход для восстановления выравнивания.

Инициализация

Создаётся матрица \( F \) размером \( (n+1) \times (m+1) \), где \( n \) и \( m \) — длины последовательностей \( A \) и \( B \) соответственно. Первая строка и первый столбец заполняются штрафами за гэпы:

• \( F(0,0) = 0 \);
• \( F(i,0) = i \times w \) для \( i = 1 \ldots n \);
• \( F(0,j) = j \times w \) для \( j = 1 \ldots m \).

Рекуррентное заполнение

Для каждой ячейки \( (i,j) \) (где \( i = 1 \ldots n \), \( j = 1 \ldots m \)) вычисляется значение по формуле: \[ F(i,j) = \max \begin{cases} F(i-1,j-1) + s(a_i, b_j) & \text{(совпадение/несовпадение)} \\ F(i-1,j) + w & \text{(вставка гэпа в B)} \\ F(i,j-1) + w & \text{(вставка гэпа в A)} \end{cases} \] Здесь \( s(a_i, b_j) \) — вес замены, а \( w \) — штраф за гэп. Значение \( F(i,j) \) представляет собой максимальную оценку выравнивания для первых \( i \) символов \( A \) и первых \( j \) символов \( B \). При этом также запоминается, из какой ячейки пришёл максимум (диагональ, сверху или слева) — это необходимо для обратного хода.

Обратный ход

После заполнения всей матрицы, начиная с ячейки \( F(n,m) \), производится обратный ход. Двигаясь от \( (n,m) \) к \( (0,0) \), алгоритм выбирает направление, которое привело к максимальному значению в текущей ячейке:

• Если это диагональ \( (i-1,j-1) \), то символы \( a_i \) и \( b_j \) выравниваются.
• Если это сверху \( (i-1,j) \), то в последовательность \( B \) вставляется гэп, а символ \( a_i \) остаётся.
• Если это слева \( (i,j-1) \), то в последовательность \( A \) вставляется гэп, а символ \( b_j \) остаётся.

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

Пример

Рассмотрим две последовательности: \( A = \text{GATTACA} \) и \( B = \text{GCATGCU} \). Пусть штраф за гэп \( w = -1 \), а матрица замен: совпадение \( +1 \), несовпадение \( -1 \). Алгоритм построит матрицу \( 8 \times 8 \), и после обратного хода может быть найдено, например, следующее выравнивание:

`` G-ATTACA GCA-TGCU ``

Оценка выравнивания: совпадения: G, A, T, A, C — 5 совпадений (+5), несовпадения: T vs C и A vs U — 2 несовпадения (-2), гэпы: 2 гэпа (-2). Итого: +1. Это не единственное оптимальное выравнивание; алгоритм гарантирует нахождение одного из них (всех, если требуется).

Сложность и оптимизации

Временная сложность алгоритма Нидлмана — Вунша составляет \( O(nm) \), где \( n \) и \( m \) — длины последовательностей. Пространственная сложность — \( O(nm) \) для хранения матрицы, хотя существуют модификации (например, алгоритм Хиршберга), которые позволяют снизить её до \( O(\min(n,m)) \) за счёт рекурсивного подхода, но с сохранением временной сложности.

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

Применение

Алгоритм Нидлмана — Вунша широко применяется в биоинформатике и смежных областях:

• Сравнение гомологичных последовательностей. Выравнивание позволяет выявить эволюционно консервативные участки, что важно для изучения филогении и функциональной аннотации генов.
• Поиск мутаций. Сравнение последовательности пациента с эталонной позволяет обнаружить однонуклеотидные полиморфизмы (SNP), вставки и делеции.
• Предсказание структуры белков. Выравнивание с известными структурами помогает моделировать трёхмерную укладку белка.
• Обработка текстов. В компьютерной лингвистике алгоритм используется для поиска различий в текстах (например, в системах контроля версий, таких как diff), хотя там чаще применяются более быстрые эвристики.
• Биоинформатика в России. В российских научных центрах (например, Институт молекулярной биологии РАН, МГУ) алгоритм используется для анализа геномов микроорганизмов, вирусов и растений, а также в образовательных программах по биоинформатике.

Критика и ограничения

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

Также алгоритм не учитывает контекстную зависимость замен (например, что некоторые мутации более вероятны в определённых участках генома), что может приводить к биологически нереалистичным выравниваниям.

Интересные факты

• Алгоритм Нидлмана — Вунша является частным случаем более общего метода динамического программирования для выравнивания последовательностей, который был независимо разработан несколькими группами учёных в 1970-х годах.
• В 1981 году Темпл Смит и Майкл Уотерман модифицировали алгоритм для локального выравнивания, что позволило находить только наиболее похожие участки последовательностей, а не выравнивать их целиком.
• Алгоритм используется в популярных биоинформатических пакетах, таких как EMBOSS (European Molecular Biology Open Software Suite) и BioPython, а также в онлайн-сервисах, например, в NCBI BLAST (хотя там применяются эвристики для ускорения).

Источники

• Needleman, S. B., & Wunsch, C. D. (1970). A general method applicable to the search for similarities in the amino acid sequence of two proteins. Journal of Molecular Biology, 48(3), 443–453.
• Durbin, R., Eddy, S. R., Krogh, A., & Mitchison, G. (1998). Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids. Cambridge University Press.
• Gusfield, D. (1997). Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press.
• Учебные материалы курса «Биоинформатика» МГУ им. М. В. Ломоносова.