[ЗАСТАВКА] Теперь
рассмотрим более практически применимую задачу в
биоинформатике — это нахождение многих строк в тексте за 1 раз.
В частности, у вас есть не просто геном (G)
и рид (R) на практике, но у вас этих ридов очень много.
У вас может быть очень много маленьких строк, которые вы ищите в геноме.
И таких ридов могут быть миллионы и больше.
Если мы будем каждый из этих ридов искать
по строке, то, допустим, строка у нас длины M,
рид длины K, каждый из них, и количество ридов — это N.
Если мы будем использовать алгоритмы, которые мы рассмотрели раньше,
то нам нужно сделать O(M + K) умножить на N раз,
потому что нам нужно повторить эту процедуру для каждого рида.
И если геном достаточно большой и N достаточно большое,
то это выражение мажорируется
произведением M * N и получается очень долго.
Как можно ускорить этот процесс?
В биоинформатике, особенно с наступлением эры Next-Generation Sequencing,
стал распространен следующий подход.
Мы строим некоторый индекс по геному,
который позволяет нам быстро искать в нем строки.
После этого нахождение каждой подстроки в этом индексе становится более быстрым,
то есть мы разделяем наши вычисления на препроцессинг,
то есть построение индекса, и сам поиск уже в индексе.
Похожие методы используются во многих областях.
Например, поисковые системы, которые вам всем знакомы, Google, Yandex,
они строят индекс по Интернету, то есть по текстам документов,
которые встречаются в Интернете, по текстам интернет-страниц.
И когда вы вводите запрос в поисковую систему, вы очень быстро получаете ответ,
и Google не должен пробегать через все-все-все терабайты данных,
которые находятся в Интернете.
И на серверах в Google можно более быстро определить
местоположение этого слова в Интернете и выдать вам результат.
Похожий алгоритм используется и в биоинформатике для того,
чтобы найти риды в геноме, когда по геному строится индекс,
а потом этот индекс применяется для поиска.
Рассмотрим, как можно построить такой индекс и какие бывают
алгоритмы в этой области.
Один из простых индексов, который можно построить, — это хеш-таблица.
Помните, что хеш-функция — это некоторая функция,
которая переводит из большего пространства в меньшее.
Например, из всех строк в числа,
которые ограничены, например, 32-битным Integer'ом.
И если у вас есть геном, вы можете разбить его
на некоторые маленькие камеры, например, на десятимеры.
И для каждого десятимера посчитать хеш-функцию,
то есть посчитать хеш-функцию от первых десяти букв в геноме,
потом посчитать хеш-функцию от десяти букв,
начиная со второго, и так далее, и так далее,
и выстроить хеш-таблицу, которая будет представлять из себя массив
от 0 до максимального значения хеша.
И в каждой ячейке будет записан список позиций
подстрок с таким хешом, который встречается в геноме.
Например, если у вас геном и по нему преподсчитана
такая хеш-таблица, то когда вы ищете,
например, AGCT, то в первую очередь вам нужно
посчитать хеш от вашего поискового запроса.
Например, он равен 10.
Мы после этого ищем десятую ячейку в хеш-таблице
по индексу и смотрим индексы, где эта последовательность встречается в геноме.
И тут сказано, например, что она встречается во 2-й позиции, в 100-й,
в 1001-й, и так далее, потому что со
2-й позиции в геноме, с 100-й позиции в геноме и с 1001-й
позиции в геноме хеш четыремера был равен 10.
В данном случае мы можем, предпосчитав такую таблицу,
то есть это наш индекс, по поисковому запросу быстро
адресоваться в нужную ячейку памяти и найти такие вхождения.
Про хеш-таблицу также вы можете почитать в Интернете.
Это достаточно распространенная структура данных,
которая часто применяется в биоинформатике и есть во многих языках программирования.
Например, в Python, если вы программируете на Python, есть структура данных
«Словарь» (dict), которая на самом деле представляет из себя именно хеш-таблицу.
Такой алгоритм достаточно быстрый на практике и часто применяется.
Также для индексирования строк часто применяются суффиксные деревья и
суффиксные массивы.
Что такое суффиксное дерево?
Это некоторая структура данных, построенная по всем суффиксам текста,
в нашем случае — по всем суффиксам генома.
Например, если вам дан геном ACCT, то мы можем по нему построить
такое суффиксное дерево: мы начинаем с корня этого
дерева и выписываем все буквы генома.
После этого мы добавляем все остальные суффиксы.
Помимо ACCT у нас суффиксами этой строки являются CCT, CT и T.
Соответственно, мы добавляем суффикс CCT.
Дальше мы добавляем суффикс CT,
при этом из корня нашего дерева уже есть ребро C,
поэтому мы по нему переходим и добавляем новое ребро T,
то есть у нас остается суффикс CCT и появляется суффикс CT.
Также у нас есть суффикс всего из одной буквы T,
который мы тоже можем добавить в это дерево.
И теперь, если вы хотите найти какую-то подстроку в нашем тексте,
например, подстроку CC, то можно начать с корня
этого дерева, который по-английски называется root,
и пройти по ребрам C и C.
Если вы нашли такой путь по ребрам CC, то, значит,
последовательность CC встречается в геноме.
Если бы вы искали последовательность CG,
то вы бы прошли по C и не встретили ребра G.
Соответственно, такой последовательности нету в нашем геноме.
При этом можно заметить, что, начиная от корня дерева,
нам нужно вглубь этого дерева пройти всего лишь столько раз,
сколько букв в искомой последовательности, независимо от размеров нашего текста.
То есть наш текст, может быть миллиарды символов,
но если у нас уже есть суффиксное дерево по этому тексту,
то вхождение строки мы можем находить намного быстрее за длину этой строки.
То есть нам нужно за некоторое O,
пока неизвестное, построить такое суффиксное дерево,
но потом, если мы ищем строку, подстроку длины K,
то мы можем за O(K) пройти по этому дереву и найти ее местоположение.
При этом можно также и по суффиксному дереву восстановить позицию,
где такая строка входит в геном.
Заметьте, что если мы просто пройдем по CC и на этом закончим наш поиск,
мы будем знать, что этот рид,
эта подстрока входит в геном, но мы не будем знать, где.
В данном случае можно хранить в листьях этого дерева,
то есть в самых низких вершинах этого дерева,
позиции этого суффикса.
Например, вот здесь вот 1, здесь 2, здесь 3,
здесь 4, потому что это 1-й суффикс, это 2-й суффикс, это 3-й,
это 4-й, и, находя, пройдя по CC,
мы можем уйти дальше вниз по дереву и прочитать число 2,
которое будет означать, что мы CC нашли во 2-м суффиксе,
то есть начиная со 2-й позиции нашей строки.
Суффиксное дерево было достаточно непопулярной структурой данных,
но потом его научились строить за линейное время.
То есть если у нас геном длины M, то суффиксное дерево можно построить за O(M),
но при этом оно немного сжатое, то есть оно хранится в сжатом виде,
который позволяет и строить его за O(M),
и потом использовать память линейную от длины генома.
Мы не будем вдаваться в подробности этого алгоритма.
Он достаточно сложный, но вы можете прочитать про него также в Интернете,
если вам интересна эта тема.
Главное, что после того, как мы за O(M) построили один раз индекс для генома,
мы можем много-много-много последовательностей в нем искать.
На практике в биоинформатике в таких программах, как Bowtie и BWA,
используется структура данных под названием FM-index.
В начале 2000-х появился FM-index и недавно появился FM-index 2,
вторая версия, более улучшенная структура данных и алгоритмов,
использующих этот индекс для поиска подстрок.
Он из себя представляет суффиксное дерево, вернее, производную от
суффиксного дерева, называемую «суффиксный массив», в некотором сжатом виде.
И благодаря этому он занимает не очень много места.
Например, для человеческого генома он занимает меньше, чем 3 гигабайта,
то есть даже меньше, чем размер человеческого генома.
При этом этот сжатый индекс позволяет быстро искать в нем подстроки.
Также из-за того, что он очень маленького размера,
он позволяет загружать весь индекс в память, в оперативную память компьютера,
и искать более быстро, чем если бы индекс лежал на жестком диске.
Например, размер суффиксного дерева по человеческому геному порядка 36 гигабайт.
И даже если у вас предподсчитан этот индекс и лежит на жестком диске,
то для его использования нужно делать обращение к жесткому диску много-много раз
— столько, сколько вы ищите.
Но FM-index, который занимает всего несколько гигабайт, можно положить в
оперативную память и уже не работать с диском, а работать с оперативной памятью,
которая в сотни раз быстрее, чем обращения к жесткому диску.
Таким образом, когда вы вызываете Bowtie build,
вы строите индекс по вашему геному.
А когда вы используете его при вызове Bowtie на ваших данных,
например, ридах в виде FASTQ, то вы по этому индексу
ищите риды достаточно быстро, за время,
которое сопоставимо с размером ридов, но не с размером исходного генома.
При этом для популярных геномов, например, для человека,
мыши и других модельных организмов, препосчитанные индексы можно
скачать из Интернета, а не считать у себя на компьютере,
что также может ускорить процесс поиска выравнивания ридов на геном.
Сегодня мы рассмотрели алгоритмы поиска подсроки в строке,
а также индексирование строк для более быстрого поиска многих подстрок сразу.
Важно отметить, что и те, и те алгоритмы применяются в биоинформатике.
Например, если вам нужно один раз найти некоторый ген в большом геноме,
то вам не обязательно его индексировать, потому что вы ищите всего один ген.
Но если вы, например, выравниваете риды от Next-Generation Sequencing на геном,
когда их у вас миллионы, то важно вначале проиндексировать геном,
а потом уже искать риды, точно также, как поисковая система индексирует
Интернет и ищет в нем запросы своих пользователей, и также, как в
конце книги присутствует индекс терминов, которые применяются в этой книге,
и если вы хотите найти определение какого-то термина, вы просто смотрите на
последние страницы, но не перелистываете все-все-все параграфы из вашей книги.
Таким образом, такие эффективные алгоритмы позволяют очень быстро,
за считанные минуты, выравнивать миллионы ридов даже на большой человеческий геном.
[МУЗЫКА]
Alla L LapidusProfessor, Department of Cytology and Histology
Николай Вяххи
Павел ДобрынинМладший научный сотрудник
Михаил РайкоПостдок
Екатерина ЧерняеваПостдок
