Сборка генома: пазл из миллионов кусочков

Секвенатор даёт миллионы коротких обрывков. Собрать из них целый геном — одна из труднейших задач биоинформатики.

Сборка генома (genome assembly) — восстановление исходной длинной последовательности из множества коротких перекрывающихся ридов без знания эталона.

В разделе про секвенирование мы видели: прибор рвёт геном на миллионы ридов. Здесь соберём картину целиком: почему это пазл, как перекрытия и граф де Брёйна (из раздела про k-меры) решают задачу и почему результат — обычно не одна строка, а множество фрагментов.

Почему это пазл, и трудный

Представьте: тысячу одинаковых книг пропустили через шредер, перемешали обрывки и просят восстановить одну книгу. Сложности: обрывки короткие, многие фразы повторяются (повторы!), часть с опечатками (ошибки прибора), и нет образца для сверки. Ровно это — сборка de novo (с нуля, без эталона).

Перекрытия — ключ к сборке

Идея: если конец одного рида совпадает с началом другого, вероятно, они соседние в геноме. Склеивая по перекрытиям, восстанавливаем последовательность. Покажем склейку двух ридов по перекрытию.

def overlap(a, b, min_len=3):
    # длина максимального суффикса a, равного префиксу b
    start = 0
    best = 0
    for i in range(min_len, min(len(a), len(b)) + 1):
        if a[-i:] == b[:i]:
            best = i
    return best

r1 = 'ATGCGTACG'
r2 = 'TACGGGTTA'
ov = overlap(r1, r2)
merged = r1 + r2[ov:]
print('Перекрытие:', ov, 'букв')
print('Склейка:', merged)

Вывод:

Перекрытие: 4 букв
Склейка: ATGCGTACGGGTTA

Риды ATGCGTACG и TACGGGTTA перекрываются на TACG (4 буквы), и склейка даёт ATGCGTACGGGTTA. Реальные сборщики делают это для миллионов ридов сразу — и тут на помощь приходит граф.

Граф де Брёйна на практике

Перебирать все пары ридов на перекрытие — O(числа ридов в квадрате), слишком дорого. Поэтому современные сборщики (из раздела про k-меры) разбивают риды на k-меры и строят граф де Брёйна: узлы — (k−1)-меры, рёбра — k-меры. Сборка = поиск пути через рёбра. Граф автоматически «складывает» одинаковые куски разных ридов, экономя работу.

риды -> бьём на k-меры -> граф де Брёйна (узлы и рёбра)
      -> чистим граф от ошибок и пузырей
      -> находим пути -> контиги (длинные собранные куски)

Контиги и скэффолды

Из-за повторов граф редко даёт одну непрерывную строку. Результат сборки — контиги (contigs): непрерывные собранные участки. Затем с помощью парных ридов (когда известно расстояние между двумя концами фрагмента) контиги связывают в скэффолды (scaffolds) — цепочки контигов с пропусками-«N» там, где последовательность ещё неизвестна. Качество сборки оценивают метрикой N50 (грубо: длина, такая что половина генома лежит в контигах не короче неё).

Как работает под капотом: почему повторы — главный враг

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

Стоит развести две принципиально разные ситуации, потому что от них зависит вся стратегия. Сборка de novo — с нуля, без эталона, нужна для новых организмов, у которых референса ещё нет; это самый трудный случай, описанный выше. Картирование на референс — когда эталонный геном уже известен (например, человеческий), и риды нового образца просто прикладывают к нему по местам; это куда проще и быстрее, и именно так работает большинство медицинских анализов: не собирают геном пациента заново, а сравнивают его риды с эталоном, отмечая отличия. Понимание, какая из двух задач перед вами, определяет выбор инструментов: для de novo нужен сборщик вроде SPAdes, для картирования — выравниватель вроде BWA из раздела про k-меры. Путаница между этими режимами — частая концептуальная ошибка новичков.

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

Ожидать одну строку на выходе. Сборка даёт множество контигов; единый геном — редкость.
Игнорировать повторы. Они главный источник фрагментации и ошибок сборки.
Сравнивать сборки только по числу контигов. Смотрите и на N50, и на полноту, и на корректность.

Итог

Сборка de novo восстанавливает геном из коротких ридов без эталона — это трудный пазл.
Соседние риды находят по перекрытиям; на масштабе это делает граф де Брёйна из k-меров.
Результат — контиги, связываемые парными ридами в скэффолды; качество мерят N50.
Повторы длиннее рида — главная причина фрагментации; их разрешают длинные и парные риды.