Сборка генома

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

Сборка генома является очень сложной вычислительной задачей, в частности, осложнённой тем, что геномы часто содержат большое количество одинаковых повторяющихся последовательностей (так называемые геномные повторы). Эти повторы могут быть длиной в несколько тысяч нуклеотидов, а также встречаться в тысяче различных мест в геноме. Особенно богаты повторами большие геномы растений и животных, в том числе геном человека.

Алгоритмические подходы

Существует два подхода для сборки геномов — основанный на перекрытии overlap-layout-consensus (применяется для длинных фрагментов), а также основанный на графах де Брёйна (применяется для коротких фрагментов) .

Overlap-Layout-Consensus

При секвенировании методом дробовика все ДНК организма сначала разрезают на миллионы маленьких фрагментов до 1000 нуклеотидов в длину. Затем алгоритмы сборки генома рассматривают полученные фрагменты одновременно, находя их перекрытия (overlap), объединяя их по перекрытиям (layout) и исправляя ошибки в объединённой строке (consensus). Данные шаги могут повторяться несколько раз в процессе сборки.

Данный подход был наиболее распространён для сборки геномов до появления секвенирования следующего поколения.

Графы де Брёйна

С развитием технологий секвенирования следующего поколения получение фрагментов стало на порядок дешевле, но размер фрагментов стал меньше (до 150 нуклеотидов), а количество ошибок при чтении фрагментов увеличилось (до 3 %). При сборке таких данных получили распространение методы, основанные на графах де Брёйна.

Доступные сборщики

Список популярных геномных сборщиков: