[ЗАСТАВКА] Но в реальной жизни
применение de Bruijn-графов не настолько простое, насколько я только что рассказал.
Потому что в реальной жизни в ридах бывают ошибки, и покрытия бывают неравномерные,
бывают дырки в покрытиях, и всё не так просто.
Если бы у нас все риды перекрывались бы почти на максимум,
то есть на длину рида минус 1, и в них не было бы ошибок, то использование de
Bruijn-графа было бы оптимальное, было бы самое быстрое и восстанавливало бы геном.
Но к сожалению, в ридах иногда случаются ошибки.
Некоторые риды не перекрываются, то есть, допустим,
если два рида длиной 100, то не существует перекрытия этих двух ридов
длины 99 и какого-то рида на этом месте, то есть покрытия меньше 100, например.
Это такое точно произойдет.
И если случаются ошибки, или покрытие не очень большое,
то построенный de Bruijn-граф разваливается на много разных кусков,
например, вот эти вот 4 рида, они в геноме перекрываются,
но здесь ошибка и здесь ошибка, а эти два перекрываются на две буквы.
Из-за этого они представляют из себя 4 несвязанных части de Bruijn-графа,
которые просто не складываются никак в один общий путь.
Для этого применяют такую технологию, как использование K-меров,
то есть наши риды просто режут на более маленькие кусочки.
И здесь возникает тот параметр K, который вы будете встречать при сборке геномов.
Почти любой ассемблер, основанный на de Bruijn-графах,
принимает на вход параметр K, и его можно варьировать.
Это K — это длина, на которую мы разрезаем каждый рид,
то есть мы, допустим, рид длины 100 разрезаем на кусочки длины, скажем, 31.
И из одного рида длины 100 у нас получается около 70 ридов длины 31.
В результате, если в исходном риде была ошибка,
она где-то встречается, но не во всех кусочках.
То есть таким образом мы из ошибочных данных получаем часть данных,
которую мы можем использовать, часть 31-меров,
например, в данном случае, которые все равно можно использовать.
И в таком случае перекрытие, если мы определяем уже не по 99 буквам,
а по 30 буквам, то такие перекрытия между ридами существуют,
и эти куски графа оказываются связанными.
Проблема в том, что мы, специально добавляя это K,
как будто делаем данные хуже, то есть вроде бы у нас были длинные риды длины
100, а мы, перед тем как применять алгоритм,
их намеренно уменьшили, и теперь у нас как будто риды длины 31.
Да, это создает проблемы, и из-за этого, в частности,
разрешения повторов становятся важной задачей в алгоритмах сборки
как постпроцессинг, а также как некоторая уже обработка контигов,
которые выходят из программы сборки.
В частности, de Bruijn-граф,
в котором есть параметр K, не может разрешить повторы больше, чем K.
То есть если у вас есть в геноме повторяющийся какой-то фрагмент длины
K-нуклеотидов, то в графе он будет представлять из себя такую структуру,
и вы не знаете, как правильно пройти по этому участку графа,
и он будет разбит на 5 контигов: A,
B, C, D и наш повтор R.
Если бы риды были длиннее, то можно было бы,
например, разбить их на контиги такого вида,
но мы не знаем, верна вот такая
сборка или ARD и BRC.
В частности, для разрешения таких
повторов применяются made pairs и pair-end риды,
о чем мы алгоритмически не будем говорить сейчас,
но они помогают разрешить такие неоднозначности тем,
что связывают ребра de Bruijn-графа, подсказывают их последовательность.
Если в геноме есть тандемные повторы,
то они могут выглядеть как некоторые циклы в графе.
То есть, допустим, идет так, так, и мы не знаем,
сколько раз нужно нам пройти по этому циклу,
и при достаточно маленькой длине рида и большом
количестве повторов в тандеме, такое разрешить невозможно.
Также хочется отметить то,
что de Bruijn-граф занимает часто достаточно много места в памяти,
и поэтому многие ассемблеры геномные требуют много оперативной памяти.
В любом случае нам приходится хранить все наши входные данные,
преобразованные в виде графа, в оперативной памяти.
Соответственно, если у вас 10 гигабайт ридов вышло из секвенатора,
и вам нужно их собрать, то вам нужно
как-то их организовать в оперативной памяти, в структуры данных граф.
Многие алгоритмы, например, которые мы будем рассматривать в следующей неделе,
они позволяют распараллеливать себя на разные компьютеры, например,
на вычислительные кластеры, на процессоры, на разные машины, то есть можно, вместо
того чтобы использовать один компьютер, в котором 100 гигабайт оперативной памяти,
использовать 10 компьютеров, в котором в каждом по 10 гигабайт оперативной памяти.
К сожалению, алгоритмы сборки генома не обладают таким свойством.
Из-за того что все данные объединяются в единый граф, который очень тесно связан
друг с другом, его очень непросто распределить на разные машины.
И сложно разделить разные куски графа на отдельные
ноды вычислительные кластера и делать вычисления распределенными,
потому что общение между этими узлами, то есть между этими компьютерами,
будет дороже, то есть будет намного больше давать сложностей,
чем вся польза от того, что мы распределяем эти данные.
И алгоритмы сборки генома обычно требуют большого компьютера с
оперативной памятью и одного.
Алгоритмы, например, выравнивания ридов на референсный геном
могут легко распараллеливаться на сотни и тысячи компьютеров,
на сотни и тысячи процессоров независимых, но сборка генома — это сложная задача,
которая требует одного единого куска оперативной памяти.
Итого, сегодня мы рассмотрели понятие алгоритмов и сложностей алгоритмов,
а также чем отличаются линейные алгоритмы от квадратичных,
и вкратце я рассказал про Overlap/Layout/Consensus-подход к сборке
графов, который применялся в основном раньше для сэнгеровских ридов,
а также про de Bruijn-граф-подход, который применяется сейчас широко
во многих инструментах геномной сборки и хорошо применим для
сборки большого количества маленьких ридов из Next-generation sequencing.
Программ для сборки генома достаточно много, и часто выбор зависит,
выбор программы зависит от того, какой у вас был эксперимент.
В частности, например, для single cell assembly, когда покрытие неравномерное,
хорошо подходит геномный сборщик Space.
Для больших геномов, если вы собираете de novo млекопитающих,
то обычно используют SOAPdenovo, который лучше организует память и
позволяет хоть как-то собрать большой геном млекопитающих.
Собрать геном млекопитающих в Space достаточно тяжело,
потому что память не так сильно сжимается, как в SOAPdenovo.
Соответственно, выбор геномного сборщика — это достаточно сложная задача,
но часто это приходит с опытом.
Также есть статьи в GAGE-B про сборку, про выбор сборщика,
который вы можете найти в разделе дополнительных материалов,
и бактериальные геномы сейчас уже реально собирать на ноутбуках,
то есть для этого не нужно очень больших вычислительных ресурсов.
Геномы млекопитающих обычно собираются на суперкомпьютерах и на больших
вычислительных системах, но часто для сборки геномов млекопитающих
не нужно их собирать de novo, о чем мы поговорим в следующей неделе.
Но важно помнить, что сборка генома de novo — это достаточно сложная задача,
потому что вы имеете большой набор ридов
исходных и не имеете никакой информации про тот геном, который вы собираете.
На самом деле часто, если вы не собираете новый организм, новый вид, например,
если вы собираете человека или собираете кошку, то у вас есть какие-то уже данные,
например, геном человека похожего или геном кошки похожей.
Если вы собираете гепарда, вы можете использовать геном кошки,
для того чтобы находить какие-то похожие регионы,
и вам не нужно будет собирать de novo и использовать такие сложные алгоритмы с
большим количеством оперативной памяти, как сборка de novo.
Но если вы собираете новые организмы, то этого никак не избежать.
Но, главное, выбирать хороший сборщик и понимать, сколько он будет работать,
и уметь оценивать время работы для ваших входных данных.
Спасибо!
До новых встреч!
[ЗАСТАВКА]
Alla L LapidusProfessor, Department of Cytology and Histology
Николай Вяххи
Павел ДобрынинМладший научный сотрудник
Михаил РайкоПостдок
Екатерина ЧерняеваПостдок
