Зачем выравнивать и точечные матрицы

Выравнивание последовательностей — способ найти сходство между ДНК или белками. С него начинается поиск родства, функции и мутаций.

Выравнивание — сопоставление двух последовательностей с расстановкой пропусков так, чтобы максимально совпали похожие участки.

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

Сходство, гомология, идентичность

Три термина, которые путают:

• Идентичность — доля точно совпадающих позиций (измеримая величина).
• Сходство — похожесть с учётом «близких» замен (для белков — биохимически родственные аминокислоты).
• Гомология — общее эволюционное происхождение (вывод, а не измерение). Гомология есть или нет; «процента гомологии» не бывает.

Высокая идентичность намекает на гомологию, но это разные вещи. Выравнивание даёт идентичность и сходство; гомологию мы заключаем из них.

Точечная матрица (dot plot)

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

def dotplot(a, b):
    lines = ['  ' + ' '.join(b)]
    for ca in a:
        row = ['*' if ca == cb else '.' for cb in b]
        lines.append(ca + ' ' + ' '.join(row))
    return '\n'.join(lines)

print(dotplot('ACGT', 'AGCT'))

Вывод:

  A G C T
A * . . .
C . . * .
G . * . .
T . . . *

Точки на главной диагонали (A…A, T…T) показывают совпадения в одинаковых позициях. Диагональная линия точек = протяжённый похожий участок. Разрыв линии со сдвигом = вставка или удаление; параллельные линии = повтор.

Что видно на dot plot

Как работает под капотом: фильтрация шума

На сырой dot plot из случайных совпадений много «снега» (одиночных точек). Чтобы выделить настоящее сходство, ставят точку не на одиночное совпадение, а только если совпадает целое окно из нескольких букв (порог). Это убирает шум и оставляет реальные диагонали. По сути это первая идея локального сходства — её формализует алгоритм Смита-Ватермана из этого раздела.

Стоит оценить, насколько содержателен dot plot как инструмент, несмотря на простоту. Это единственный способ выравнивания, который показывает всю картину сходства сразу, а не один «лучший» вариант. Алгоритмы Нидлмана-Вунша и Смита-Ватермана выдают одно оптимальное выравнивание и прячут альтернативы; dot plot же честно рисует все совпадения, и опытный глаз мгновенно считывает структуру: тандемные повторы выглядят как лесенка коротких параллельных диагоналей, дупликация целого участка — как вторая длинная диагональ в стороне от главной, инверсия — как диагональ, идущая в противоположную сторону. Именно поэтому, сравнивая два целых генома, биоинформатики до сих пор первым делом строят dot plot: за секунды видно перестройки хромосом, которые в текстовом выравнивании потерялись бы среди тысяч строк. Так наглядность простого метода дополняет точность сложных.

Важно и понимание границ метода. Dot plot отлично работает для визуальной разведки на коротких и средних последовательностях, но как точный инструмент он ограничен: он не даёт численного счёта, не расставляет пропуски и плохо масштабируется на миллионы букв (матрица становится гигантской). Поэтому в реальном анализе dot plot — это разведка, после которой включают численные алгоритмы выравнивания этого раздела. Связка «сначала посмотреть глазами, потом посчитать точно» — здоровый рабочий процесс, который убирает грубые ошибки до того, как вы доверитесь числу из программы.

def windowed_dotplot(a, b, w, threshold):
    rows = []
    for i in range(len(a) - w + 1):
        line = ''
        for j in range(len(b) - w + 1):
            matches = sum(1 for x, y in zip(a[i:i+w], b[j:j+w]) if x == y)
            line += '*' if matches >= threshold else '.'
        rows.append(line)
    return '\n'.join(rows)

print(windowed_dotplot('ACGTACGT', 'ACGTACGT', w=3, threshold=3))

Вывод:

*...*.
.*...*
..*...
...*..
*...*.
.*...*

Звёздочки выстроились в диагонали: главная диагональ (где i = j) показывает полное совпадение строк, а смещённые диагонали — внутренний повтор ACGT (он встречается дважды, поэтому окна совпадают и со сдвигом на 4). Окно с порогом отсекает случайные одиночные совпадения и проявляет осмысленную диагональную структуру.

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

• Путать сходство и гомологию. Сходство измеряют; гомологию выводят. «Процент гомологии» — неверный термин.
• Читать сырой dot plot без фильтра. Случайные совпадения создают шум; нужен оконный порог.
• Забывать про вторую нить. Инверсии видны как «обратные» диагонали — сравнивайте и с обратным комплементом.

Итог

• Выравнивание ищет сходство — основу выводов о функции, родстве и мутациях.
• Идентичность и сходство измеряют; гомологию (общее происхождение) выводят.
• Точечная матрица визуализирует сходство: диагонали — похожие участки, сдвиги — indel, параллели — повторы.
• Оконный порог убирает шум — это шаг к формальному локальному выравниванию.