Issn 2072-0297 Молодой учёный Международный научный журнал Выходит еженедельно №3 (137) / 2017 р е д а к ц и о н н а я к о л л е г и я : Главный редактор



Pdf көрінісі
бет38/129
Дата23.11.2022
өлшемі9,13 Mb.
#159594
1   ...   34   35   36   37   38   39   40   41   ...   129
Байланысты:
moluch 137 ch1


#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. Построение контигов. Для построения контигов 
используются начальные вершины обхода, хранящиеся 
в массиве перспективных вершин.


Достарыңызбен бөлісу:
1   ...   34   35   36   37   38   39   40   41   ...   129




©engime.org 2024
әкімшілігінің қараңыз

    Басты бет