Граф де Брёйна и идея сборки

k-меры умеют не только искать — на них строят граф, по которому собирают геном из миллионов обрывков. Это идея графа де Брёйна.

Граф де Брёйна — граф, где узлы — это (k−1)-меры, а каждый k-мер задаёт ребро, соединяющее его префикс и суффикс. Сборка генома сводится к поиску пути, проходящего по всем рёбрам.

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

Из k-мера — ребро графа

Каждый k-мер расщепляется на префикс (первые k−1 букв) и суффикс (последние k−1 букв). Префикс и суффикс — это узлы, а сам k-мер — ребро между ними. Соседние k-меры в последовательности перекрываются на k−1 букв, поэтому их рёбра стыкуются.

def de_bruijn_edges(seq, k):
    edges = []
    for i in range(len(seq) - k + 1):
        kmer = seq[i:i+k]
        edges.append((kmer[:-1], kmer[1:]))  # префикс -> суффикс
    return edges

for a, b in de_bruijn_edges('ATGGCG', 3):
    print(f'{a} -> {b}')

Вывод:

AT -> TG
TG -> GG
GG -> GC
GC -> CG

Получилась цепочка узлов AT → TG → GG → GC → CG. Пройдя по ней и склеивая по одной новой букве, мы восстанавливаем исходную строку ATGGCG. В этом и есть суть сборки.

Сборка как путь по графу

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

edges = [('AT','TG'), ('TG','GG'), ('GG','GC'), ('GC','CG')]

# простая реконструкция: идём по цепочке и добавляем по букве
path = [edges[0][0]]  # стартовый узел
for a, b in edges:
    path.append(b)

genome = path[0] + ''.join(node[-1] for node in path[1:])
print('Узлы пути:', ' -> '.join(path))
print('Собранный геном:', genome)

Вывод:

Узлы пути: AT -> TG -> GG -> GC -> CG
Собранный геном: ATGGCG

Из четырёх рёбер мы склеили исходную строку ATGGCG, добавляя по одной последней букве каждого следующего узла. На этом принципе работают реальные сборщики (SPAdes, Velvet) — только узлов там миллиарды.

Почему эйлеров, а не гамильтонов путь

Раньше сборку формулировали как поиск пути через все узлы (гамильтонов путь) — NP-трудная задача, практически неподъёмная. Прорыв де Брёйна: сделать k-меры рёбрами, тогда сборка — это эйлеров путь (через все рёбра), а он находится за линейное время. Один и тот же набор данных, но другая формулировка превращает невозможное в быстрое — красивый урок алгоритмики.

Гамильтонов путь: через все УЗЛЫ ровно раз  -> NP-трудно
Эйлеров путь:     через все РЁБРА ровно раз -> линейно (легко)
де Брёйн делает k-меры рёбрами => получаем эйлеров случай

Как работает под капотом: почему сборка трудна на практике

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

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

• Путать узлы и рёбра. В графе де Брёйна k-меры — рёбра, а (k−1)-меры — узлы; наоборот будет NP-трудно.
• Игнорировать повторы. На реальных данных они главный источник неоднозначности сборки.
• Слишком маленький k. Тогда граф схлопывается: разные участки дают одинаковые k-меры, и сборка рассыпается.

Итог

• Граф де Брёйна: узлы — (k−1)-меры, рёбра — k-меры (префикс → суффикс).
• Сборка генома = поиск эйлерова пути (через все рёбра) — это быстро.
• Формулировка через рёбра превращает NP-трудный гамильтонов путь в линейный эйлеров.
• На практике сборку усложняют ошибки и повторы; реальные сборщики чистят граф.