Матрицы замен и идея BLAST

Для белков «совпало/не совпало» слишком грубо — нужны матрицы замен. А чтобы искать в базе из миллионов записей, точное выравнивание заменяют эвристикой BLAST.

Матрица замен (BLOSUM, PAM) задаёт счёт за выравнивание каждой пары аминокислот, отражая, насколько биологически правдоподобна такая замена. BLAST — эвристический алгоритм быстрого поиска похожих последовательностей в больших базах.

Два финальных кирпичика выравнивания. Сначала поймём, почему белки нельзя выравнивать как «match=1, mismatch=−1», а потом — как искать сходство не среди двух последовательностей, а среди миллионов за секунды.

Почему белкам нужны матрицы замен

Аминокислоты различаются по химии. Замена лейцина на изолейцин (обе гидрофобные, похожие) почти безвредна, а лейцина на заряженный аспартат — разрушительна. Простая схема «совпало/не совпало» этого не видит. Матрица замен даёт каждой паре свой счёт: похожим заменам — положительный или мягкий, разрушительным — сильно отрицательный.

# Крошечный фрагмент матрицы замен (идея BLOSUM): счёт за пару аминокислот
SUBST = {
    ('L', 'L'): 4, ('L', 'I'): 2, ('L', 'V'): 1,  # похожие гидрофобные
    ('L', 'D'): -4, ('D', 'D'): 6, ('D', 'E'): 2,  # заряженные
}
def score_pair(a, b):
    return SUBST.get((a, b), SUBST.get((b, a), -3))

for pair in [('L', 'L'), ('L', 'I'), ('L', 'D'), ('D', 'E')]:
    print(f'{pair[0]} vs {pair[1]}: счёт {score_pair(*pair)}')

Вывод:

L vs L: счёт 4
L vs I: счёт 2
L vs D: счёт -4
D vs E: счёт 2

L против I получает +2 (родственные), L против D — −4 (разные классы). Подставив такую матрицу вместо match/mismatch в Нидлмана-Вунша или Смита-Ватермана, мы получаем биологически осмысленное выравнивание белков.

BLOSUM против PAM

Запомнить легко: у BLOSUM меньшее число (BLOSUM45) — для дальних родственников, у PAM наоборот большее число — для дальних. BLOSUM62 — отраслевой стандарт по умолчанию.

Проблема масштаба: зачем BLAST

Смит-Ватерман точен, но его O(n·m) на каждую пару — это смерть, если в базе миллионы белков. Сравнить запрос с каждым точным алгоритмом нереально. BLAST (Basic Local Alignment Search Tool) жертвует гарантией оптимальности ради скорости — и это окупается.

Как работает под капотом: три шага BLAST

1. Seeds (слова). Запрос бьётся на короткие слова (для белков обычно длины 3). Ищут в базе точные (или почти точные по матрице) совпадения этих слов — быстро, через индекс.
2. Extension (расширение). Вокруг найденных seed-совпадений выравнивание продлевают в обе стороны, пока счёт растёт. Дорогой Смит-Ватерман запускают лишь в перспективных местах.
3. Оценка значимости. Для каждого попадания считают E-value — ожидаемое число таких совпадений случайно. Маленький E-value (например, 10⁻⁵⁰) значит «вряд ли случайность, вероятно, родство».

Запрос ----> разбить на слова длины 3
  слова --> искать точные совпадения в базе (индекс, быстро)
    хиты --> расширять выравнивание вокруг (Смит-Ватерман локально)
      --> E-value: насколько находка значима (а не случайна)

Это та же идея «фильтр + проверка», что в k-мерном индексе: дешёвый шаг отсеивает почти всё, дорогой запускается лишь на кандидатах. Поэтому BLAST за секунды ищет в базах из сотен миллионов последовательностей, тогда как полный Смит-Ватерман работал бы сутками.

E-value: язык значимости

BLAST сообщает не «процент похожести», а E-value — сколько таких же хороших совпадений ожидалось бы найти в базе чисто случайно. Чем меньше, тем надёжнее. E-value = 10 — мусор (десять случайных совпадений ожидаемо); E-value = 10⁻⁴⁰ — почти наверняка настоящая гомология. Это статистическая поправка на размер базы: чем больше база, тем легче случайно найти «похожее», и E-value это учитывает.

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

• Выравнивать белки как ДНК (match/mismatch). Теряется биохимия замен — используйте BLOSUM/PAM.
• Считать BLAST точным. Это эвристика: быстрый, но может пропустить слабое сходство, которое нашёл бы Смит-Ватерман.
• Смотреть только на процент идентичности. E-value учитывает размер базы и длину — он надёжнее как мера значимости.

Итог

• Матрицы замен (BLOSUM, PAM) дают паре аминокислот счёт по биохимическому сходству; BLOSUM62 — стандарт.
• Их подставляют вместо match/mismatch в выравнивание белков.
• BLAST — эвристика поиска по базам: seeds → расширение → E-value, по принципу «фильтр + проверка».
• E-value оценивает значимость находки с учётом размера базы; маленький E-value — вероятная гомология.