[ЗАСТАВКА] Посмотрим, какой можно разработать алгоритм, чтобы собирать данные секвенирования следующего поколения. Они отличаются тем, что количество видов у нас очень большое. Они, то есть эти риды, поменьше, и в них много ошибок. Но пока забудем про ошибки. И я расскажу о такой структуре данных, как de Bruijn graph, на котором основаны все современные геномные сборщики. [ПИШЕТ] Само понятие de Bruijn graph пришло из математики, и в математике это некоторый граф на перестановках, обычно это полный граф на перестановках, не будем вдаваться в математические подробности. В информатике он чуть‐чуть отличается от формального математического определения, но несёт в себе те же самые идеи, которые де Брёйн сформулировал, применяя такой граф в математике. Допустим, каждый рид у нас длиной 100 букв. 100 нуклеотидов. Для нас, информатиков, нуклеотиды — это просто буквы. И таких видов у нас очень много, но все они одинаковой длины. И, допустим, во всех у них нет ошибок. То есть мы точно знаем, что эти 100 нуклеотидов, они встречаются в нашем геноме в какой‐то позиции. Но мы не знаем в какой позиции, все риды перемешаны, и наша задача — восстановить исходный геном, который мы пытаемся просеквенировать. Что можно сделать? Можно построить, опять‐таки, граф по этим данным, но немного другой. Мы каждый рид разбиваем на две 99‐буквенные последовательности. Это первые 99 букв. И вторые, или последние, 99 букв. Каждый рид представляет из себя 2 вершины и ребро. На ребре написана 100‐буквенная последовательность этого рида, в вершине записана 99‐буквенная последовательность префикса этого рида, то есть всё, кроме последней буквы. И во второй вершине записаны тоже 99 букв, но последних. Например, если у нас был рид ACGT, у него длина 4, и он из себя представляет вершину ACG, из которой идёт ребро в вершину CGT. И на ребре написано ACGT. Итого, все наши риды разбиваются на пары вершин и соединяющее ребро. После этого мы берём и объединяем все вершины, на которых одно и то же написано. Соответственно, если у нас был рид CGTA, то он из себя представил вершину CGT и GTA. И вот эти вот 2 вершины имеют один и тот же label, то есть они означают одну и ту же последовательность, и они просто объединяются, они становятся одной вершиной. И наш граф после склеивания вершин представляет из себя ACG, CGT и GTA. Можно заметить, что в данном графе риды — уже рёбра, а не вершины. То есть в overlap layout consensus в подходе в overlap графе каждый рид являлся вершиной, и был соединён с другими вершинами, то есть с другими ридами, по перекрытиям. В de Bruijn графе каждый рид представляет из себя ребро. И 2 ребра сходятся в одной вершине, если этот рид заканчивается на ту же самую последовательность, что и начинается следующий рид. Интересно отметить, что такой граф строится за O(N), благодаря применению такой структуры данных, как хеш-таблица. Не будем вдаваться в подробности, но такой переход позволил применять de Bruijn графы для сборки данных next-generation sequencing, в которых миллионы, а порой и сотни миллионов ридов, которые overlap граф построить просто невозможно, потому что это квадратичный алгоритм, а de Bruijn граф построить можно, потому что это линейный алгоритм. Также интересный момент в этой истории то, что в de Bruijn графе геном является таким путём в графе, который проходит каждое ребро один раз. В overlap графе нужно было проходить вершины, потому что вершины — это риды. В de Bruijn графе нужно проходить рёбра, потому что рёбра — это риды. То есть такая строка, которая проходит через граф по всем рёбрам, нам рассказывает, то есть нам выписывает наш геном, который содержит все эти риды. И нахождение пути в графе, который проходит через все рёбра, является задачей нахождения Эйлерова цикла, которая, удивительно, но решается тоже за линейное время. В overlap графе задача нахождения пути по вершинам решалась за экспоненциальное время, это очень сложная задача. В de Bruijn графе задача нахождения пути по рёбрам решается за линейное время, и это — очень простая задача. В результате, мы можем построить такой граф за линейное время и найти в нём путь, который описывает, который рассказывает нам геном тоже за линейное время. И в результате время работы всего алгоритма сборки в помощью de Bruijn графов линейно. Многие современные сборщики работают как раз с использованием de Bruijn графов. Первым из них был Euler ассемблер. Достаточно популярным ассемблером, который использует de Bruijn графы, и который одним из первых стал широкоприменим, — это Velvet. Наверно, если вы достаточно давно занимаетесь биоинформатикой, то вы слышали про этот ассемблер. А если недавно, то встречаете или будете его встречать в публикациях. Также на основе de Bruijn графа существует ассемблер SPAdes, который разрабатывается в Санкт‐Петербурге, SOAPdenovo, ALLPATH, IDBA и многие другие ассемблеры, которые применимы для современных данных с, в частности, Illumina, Ion Torrent'ом и других технологий next generation sequencing. Хочу отметить, что в последние годы получила ещё распространение технология Pacific Biosciences, у которых риды достаточно длинные, и в них много ошибок. Но из‐за того, что они длинные и их мало, к ним часто пытаются применить, и достаточно успешно, иногда алгоритмы overlap layout consensus сборки, предварительно, правда, исправив ошибки. То есть если взять данные Pacific Biosciences, и например с помощью данных Illumina как-то откорректировать в них ошибки, то дальше можно использовать алгоритм overlap layout consensus для их сборки, и это работает лучше, чем алгоритмы, основанные на de Bruijn графах. Потому что в Pacific Biosciences алгоритмы большие, и лучше искать overlap'ы, и достаточно эффективно получается. {МУЗЫКА}
