Расстояние Хэмминга и мутации

Чтобы сравнить две последовательности равной длины буква в букву, считают расстояние Хэмминга — число несовпадений.

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

Когда два гена почти одинаковы, но один накопил мутации, расстояние Хэмминга прямо считает число точечных замен между ними. Это простейшая мера «непохожести» и основа приближённого поиска. Условие — строки одной длины (только замены, без вставок и удалений; для них нужно выравнивание).

Считаем расстояние Хэмминга

def hamming(a, b):
    if len(a) != len(b):
        raise ValueError('Строки должны быть равной длины')
    return sum(1 for x, y in zip(a, b) if x != y)

s1 = 'GAGCCTACTAACGGGAT'
s2 = 'CATCGTAATGACGGCCT'
print('Расстояние Хэмминга:', hamming(s1, s2))

Вывод:

Расстояние Хэмминга: 7

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

Биологический смысл

Расстояние Хэмминга = число точечных замен (substitutions). Если разделить его на длину, получим долю различий — грубую оценку эволюционного расстояния: чем больше мутаций накопилось, тем дальше разошлись последовательности. Это используется при построении деревьев (раздел про филогенетику). Но Хэмминг не видит вставок/удалений — для них нужно выравнивание.

GAGCCTACTAACGGGAT
несовпадения помечены столбцами ниже
CATCGTAATGACGGCCT
(несовпадений: 7)

Приближённый поиск мотива

В реальной ДНК сайт связывания не идеален — он встречается с парой ошибок. Поэтому ищут мотив с допуском: все позиции, где расстояние Хэмминга до мотива не больше d.

def hamming(a, b):
    return sum(1 for x, y in zip(a, b) if x != y)

def find_approx(seq, motif, max_d):
    k = len(motif)
    hits = []
    for i in range(len(seq) - k + 1):
        if hamming(seq[i:i+k], motif) <= max_d:
            hits.append(i)
    return hits

seq = 'ATGACGATGTTG'
print('ATG с d=0:', find_approx(seq, 'ATG', 0))
print('ATG с d=1:', find_approx(seq, 'ATG', 1))

Вывод:

ATG с d=0: [0, 6]
ATG с d=1: [0, 3, 6, 9]

При d=0 находим точные ATG (позиции 0 и 6). При d=1 добавляются позиции, отличающиеся одной буквой (3 и 9). Так ищут вырожденные сайты и моделируют мутации.

Как работает под капотом: Хэмминг против Левенштейна

Хэмминг прост, но жёсток: требует равной длины и считает только замены. Если одна последовательность получила вставку, все буквы после неё «съезжают», и Хэмминг покажет огромное расстояние, хотя биологически отличие — одна вставка. Расстояние Левенштейна (редактирования) учитывает вставки и удаления, а его обобщение — выравнивание — главная тема следующего раздела. Правило: одинаковая длина и только замены — Хэмминг; возможны сдвиги — выравнивание.

У приближённого поиска есть и оборотная сторона, о которой стоит помнить, — сложность. Наш вариант проверяет каждое окно за O(k) и проходит всю строку, давая O(n·k). Для одного мотива в гене это пустяк. Но в задачах вроде поиска всех вариантов сайта связывания транскрипционного фактора по всему геному человека с допуском в 2–3 ошибки наивный перебор уже ощутимо тяжёл, и применяют умные приёмы: бьют мотив на куски (если ошибок не больше d, хотя бы один из d+1 кусков совпадёт точно — это «принцип ящиков») и сначала ищут точные куски быстрым индексом, а уже вокруг них проверяют полный мотив. Эта идея «фильтр плюс проверка» — та же, что лежит в основе BLAST, к которому мы придём в разделе про выравнивание. Так простое расстояние Хэмминга оказывается отправной точкой для серьёзных эвристик поиска.

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

• Применять Хэмминг к строкам разной длины. zip молча обрежет по короткой — добавьте проверку длины.
• Считать Хэмминг при наличии вставок. Он завысит различие; нужно выравнивание.
• Забыть границу поиска. В приближённом поиске range(len-k+1), иначе выйдете за конец.

Итог

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