.
#3 (137)
.
January 2017
27
Computer Science
И Н Ф О Р М А Т И К А
Разработка алгоритма сборки и анализа больших геномов
Бойко Владимир Андреевич, аспирант
Научный руководитель: Кузьмин Д. А., кандидат технических наук
Сибирский федеральный университет (г. Красноярск)
С
пецифика многих современных задач биологии и ме-
дицины требует знания генома живых организмов,
состоящего из нуклеотидных последовательностей дезок-
сирибонуклеиновой кислоты (ДНК).
На сегодняшний день существуют и применяются
сборщики ДНК, собравшие уже множество известных
геномов. Однако когда речь заходит о геномах большой
длинны, осложненных значительным количеством по-
вторяющихся участков, то гарантировать однозначную
сборку генома становится невозможно. Также большин-
ство сборщиков запрограммированы на работу с вход-
ными данными, полученными из строго определённых
типов секвенаторов. Такой подход сокращает возможную
область применения сборщиков и не удовлетворяет идео-
логии свободнораспространяемого ПО.
В данной работе представлено описание сборщика
лишенного вышеперечисленных недостатков и показан
пример его работы.
Описание алгоритма
Как и большинство современных сборщиков, предла-
гаемый подход использует парные чтения, получаемые из
секвенаторов нового поколения, и в связи с этим рабо-
тает на основе алгоритма использующего граф де Брёйна.
Разделим работу сборщика на следующие этапы:
1. Нумерация чтений — каждое чтение получает уни-
кальный идентификационный номер, позволяющий одно-
значно восстановить нуклеотидную последовательность
в пределах одного чтения во время обхода графа.
2. Построение графа де Брёйна и выбор числа
k — любой граф может иметь вершины и рёбра. В нашем
случае вершинами являются k — меры. Ребро из вер-
шины 1 в вершину 2 проводится только тогда, когда суф-
фикс длинны k — 1 из k — мера представляющего вер-
шину 1, равняется префиксу k — мера вершины 2, т. е.
ребро, по сути, является (k + 1) — мером.
3. Упрощение графа. Если в графе находится путь,
у которого входящие и исходящие степени всех вну-
тренних вершин равны 1, то такой путь заменяется ре-
бром.
4. Нахождение перспективных вершин. Для нахож-
дения перспективных k — меров будем полагать, что ве-
роятность нахождения вершины в исходном геноме тем
выше, чем большее количество исходящих ребер она
имеет. Обозначим
p
i
как количество всех исходящих ребер
для вершины
v
i
Тогда общее число всех исходящих ребер:
, где n — общее количество всех вершин. Найдем
среднее значение исходящих ребер N для всего графа.
. Перспективными будем называть вершины име-
ющие значение исходящих вершин больше N. Количество
перспективных вершин может варьироваться в разных
библиотеках чтений от 5% до 10%.
5. Построение контигов. Для построения контигов
используются начальные вершины обхода, хранящиеся
в массиве перспективных вершин.
Достарыңызбен бөлісу: |