Issn 2072-0297 Молодой учёный Международный научный журнал Выходит еженедельно №3 (137) / 2017 р е д а к ц и о н н а я к о л л е г и я : Главный редактор
жүктеу/скачать 9,13 Mb. Pdf көрінісі
|
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. Построение контигов. Для построения контигов используются начальные вершины обхода, хранящиеся в массиве перспективных вершин. жүктеу/скачать 9,13 Mb. Достарыңызбен бөлісу:
|