Сборка генома
Сборка генома — процесс объединения большого количества коротких фрагментов ДНК (ридов) в одну или несколько длинных последовательностей (контигов и скаффолдов) в целях восстановления последовательностей ДНК хромосом, из которых возникли эти фрагменты в процессе секвенирования. Сборка генома является очень сложной вычислительной задачей, в частности, осложнённой тем, что геномы часто содержат большое количество одинаковых повторяющихся последовательностей (так называемые геномные повторы). Эти повторы могут быть длиной в несколько тысяч нуклеотидов, а также встречаться в тысяче различных мест в геноме. Особенно богаты повторами большие геномы растений и животных, в том числе геном человека. Алгоритмические подходыСуществует два подхода для сборки геномов — основанный на перекрытии overlap-layout-consensus (применяется для длинных фрагментов), а также основанный на графах де Брёйна (применяется для коротких фрагментов) . Overlap-Layout-ConsensusПри секвенировании методом дробовика все ДНК организма сначала разрезают на миллионы маленьких фрагментов до 1000 нуклеотидов в длину. Затем алгоритмы сборки генома рассматривают полученные фрагменты одновременно, находя их перекрытия (overlap), объединяя их по перекрытиям (layout) и исправляя ошибки в объединённой строке (consensus). Данные шаги могут повторяться несколько раз в процессе сборки. Данный подход был наиболее распространён для сборки геномов до появления секвенирования следующего поколения. Графы де БрёйнаС развитием технологий секвенирования следующего поколения получение фрагментов стало на порядок дешевле, но размер фрагментов стал меньше (до 150 нуклеотидов), а количество ошибок при чтении фрагментов увеличилось (до 3 %). При сборке таких данных получили распространение методы, основанные на графах де Брёйна. Доступные сборщикиСписок популярных геномных сборщиков: |