Множественное выравнивание: обзор

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

Множественное выравнивание (MSA, Multiple Sequence Alignment) — одновременное выравнивание трёх и более последовательностей так, чтобы соответствующие позиции стояли в одной колонке.

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

Как выглядит MSA

Результат — таблица, где каждая строка-последовательность дополнена пропусками так, чтобы гомологичные позиции оказались в одном столбце.

seq1  M K V L - A T
seq2  M K V L L A T
seq3  M - V L L A S
       *   * *   *      <- '*' = колонка полностью консервативна

Столбцы со звёздочкой одинаковы у всех — это консервативные позиции, обычно функционально важные. Пропуски (-) показывают, где у одной последовательности есть вставка или удаление относительно других.

Почему это трудно

Парное выравнивание двух строк — O(n·m). Точное выравнивание k последовательностей динамическим программированием требует k-мерной матрицы, и сложность растёт как O(n^k) — экспоненциально по числу последовательностей. Для трёх коротких ещё реально, для десятков — невозможно. Поэтому точного MSA на практике не делают; применяют эвристики.

# Грубая оценка размера k-мерной матрицы точного MSA
n = 100  # длина каждой последовательности
for k in [2, 3, 5, 10]:
    cells = n ** k
    print(f'{k} последовательностей: ~{cells:.0e} ячеек')

Вывод:

2 последовательностей: ~1e+04 ячеек
3 последовательностей: ~1e+06 ячеек
5 последовательностей: ~1e+10 ячеек
10 последовательностей: ~1e+20 ячеек

Десять коротких последовательностей дали бы 10²⁰ ячеек — неподъёмно. Отсюда необходимость приближённых методов.

Как работает под капотом: прогрессивное выравнивание

Главная эвристика (её используют ClustalW, MUSCLE, MAFFT) — прогрессивное выравнивание:

1. Посчитать все попарные сходства между последовательностями.
2. Построить по ним грубое направляющее дерево (guide tree) — кто на кого больше похож.
3. Выравнивать по дереву от самых похожих к далёким, постепенно добавляя последовательности к растущему выравниванию.

Шаг 1: выровнять две самые похожие  -> профиль AB
Шаг 2: добавить следующую к профилю -> профиль ABC
Шаг 3: ... и так по направляющему дереву до конца

Принцип «жадно, от близких к далёким» избегает экспоненциального взрыва: вместо k-мерной задачи делаем серию парных выравниваний (последовательность против профиля). Цена — приближённость: ранняя ошибка («once a gap, always a gap») тащится дальше. Поэтому современные инструменты добавляют итеративное уточнение.

Важно понять, что выравнивается на поздних шагах: не одна последовательность с другой, а последовательность с профилем — обобщённым представлением уже выровненной группы. Профиль для каждой колонки хранит частоты букв (например, «здесь 80% лейцина, 20% изолейцина»). Выравнивая новую последовательность против профиля, мы используем те же алгоритмы динамического программирования, что в разделе про парное выравнивание, только счёт за колонку считается как усреднение по частотам. Эта идея «последовательность против профиля» — мостик от парного выравнивания к множественному и объясняет, почему MSA удаётся свести к серии знакомых парных задач вместо неподъёмной многомерной.

Стоит и оценить, зачем вообще терпеть эти сложности. MSA — фундамент сразу нескольких ветвей анализа. На нём строят филогенетические деревья (следующие уроки), потому что для корректного дерева нужно знать, какие позиции соответствуют друг другу у всех видов. Из MSA выводят профили и скрытые марковские модели (HMM) семейств белков, которыми затем ищут далёких родственников чувствительнее, чем BLAST. По консервативным колонкам MSA находят функционально важные остатки — мишени для лекарств. То есть MSA — это не самоцель, а вход во многие самые содержательные анализы биоинформатики, и потому усилия на качественное выравнивание окупаются сторицей.

Частые ошибки

• Пытаться сделать точный MSA для многих последовательностей. Экспоненциальная сложность не позволит — нужны эвристики.
• Слепо верить пропускам. Прогрессивный метод фиксирует ранние пропуски навсегда; результат стоит проверять.
• Игнорировать качество входа. Мусорная или неродственная последовательность портит всё выравнивание и дерево.

Итог

• MSA выравнивает много последовательностей, выявляя консервативные колонки и indel.
• Точное MSA экспоненциально по числу последовательностей — практически нереально.
• Прогрессивное выравнивание строит направляющее дерево и выравнивает от близких к далёким.
• Это эвристика: быстро, но ранние ошибки накапливаются; нужны итеративные уточнения.