k-меры: подсчёт и частоты

k-мер — это подстрока длины k. Разбив геном на k-меры и посчитав их, мы получаем мощный язык для анализа последовательностей.

k-мер — любая подстрока длины k в последовательности. Множество всех k-меров и их частот называют k-мерным составом.

k-меры — рабочая лошадка современной биоинформатики. На них держатся сборка геномов, быстрый поиск, сравнение последовательностей без выравнивания, обнаружение загрязнений. Идея проста: вместо того чтобы сравнивать строки целиком, разбиваем их на короткие куски и работаем с кусками. Начнём с подсчёта.

Разбиение на k-меры

Из строки длины n получается n − k + 1 k-меров (скользящим окном с шагом 1). Считаем частоты через Counter.

from collections import Counter

def count_kmers(seq, k):
    return Counter(seq[i:i+k] for i in range(len(seq) - k + 1))

seq = 'GGACCGGTGGACC'
counts = count_kmers(seq, 3)
print('Всего 3-меров:', sum(counts.values()))
for kmer, n in counts.most_common(4):
    print(f'{kmer}: {n}')

Вывод:

Всего 3-меров: 11
GGA: 2
GAC: 2
ACC: 2
CCG: 1

Из строки длины 13 вышло 11 трёхмеров (13 − 3 + 1). Самые частые встречаются дважды — это уже сигнал о структуре последовательности.

Сколько вообще бывает k-меров

Над алфавитом ДНК (4 буквы) существует 4^k различных k-меров. Это растёт стремительно и определяет, какой k разумен.

k	Число возможных k-меров (4^k)	Типичное применение
3	64	кодоны, грубый состав
8	65 536	сигнатуры, фильтры
21	~4,4·10¹²	сборка генома, уникальные «якоря»

for k in [3, 8, 21]:
    print(f'k={k}: возможных k-меров = {4 ** k}')

Вывод:

k=3: возможных k-меров = 64
k=8: возможных k-меров = 65536
k=21: возможных k-меров = 4398046511104

Зачем считать k-меры

Сравнение без выравнивания. Две последовательности с похожим k-мерным составом, вероятно, родственны — и это быстро.
Сборка. Перекрытия ридов выражают через общие k-меры (граф де Брёйна, отдельный урок).
Контроль качества. Аномально частые k-меры выдают адаптеры или загрязнение.
Идентификация. k-мерный «отпечаток» помогает определить организм по фрагменту.

Как работает под капотом: выбор k

Маленький k (3–5) даёт грубый, но устойчивый к ошибкам состав — почти все k-меры встречаются. Большой k (21+) делает k-меры почти уникальными в геноме (удобно как «якоря»), но чувствительнее к ошибкам прибора: одна ошибочная буква портит k k-меров. Поэтому k подбирают под задачу: для сборки берут такой k, чтобы k-меры были достаточно уникальны, но покрытие каждого оставалось высоким. Это компромисс между специфичностью и устойчивостью.

Отдельно стоит понятие каноничного k-мера, которое всплывает почти везде на практике. ДНК двунитевая, и один и тот же физический участок на разных нитях читается как k-мер и как его обратный комплемент. Чтобы не считать их дважды, из пары «k-мер и его обратный комплемент» выбирают один представитель — обычно лексикографически меньший — и называют его каноничным. Тогда подсчёт ведут по каноничным формам, и состав не зависит от того, с какой нити пришёл рид. Это маленькая, но важная деталь: забыв про неё, можно вдвое исказить статистику или решить, что два одинаковых участка разные. Почти все серьёзные k-мерные инструменты (для сборки, для оценки размера генома, для сравнения образцов) работают именно с каноничными k-мерами.

Любопытное применение, объединяющее всё вышесказанное, — оценка размера и сложности генома ещё до сборки, по одним только ридам. Строят гистограмму: сколько k-меров встретилось 1 раз, сколько 2 раза, и так далее. У этой гистограммы появляется характерный пик на уровне покрытия: k-меры из уникальной части генома группируются вокруг значения, равного глубине секвенирования. По положению пика оценивают покрытие, по площади — размер генома, а лишний пик слева выдаёт ошибки (они дают редкие, встречающиеся один раз k-меры). Так из простого подсчёта k-меров, без всякой сборки, извлекают фундаментальные параметры эксперимента — наглядный пример мощи k-мерного подхода.

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

Неверная граница. Диапазон range(len-k+1); иначе последний k-мер либо потеряется, либо выйдет за конец.
Слишком большой k на коротких/шумных данных. Почти все k-меры станут уникальными и бесполезными.
Игнорировать обратную нить. Для многих задач k-мер и его обратный комплемент считают одним (каноничный k-мер).

Итог

k-мер — подстрока длины k; из строки длины n их n − k + 1.
Частоты удобно считать через Counter за один проход.
Возможных k-меров 4^k — растёт экспоненциально, отсюда выбор k под задачу.
k-меры лежат в основе сравнения без выравнивания, сборки и контроля качества.