Разработка алгоритма сборки и анализа больших геномов | Статья в журнале «Молодой ученый»

Автор:

Рубрика: Информатика

Опубликовано в Молодой учёный №3 (137) январь 2017 г.

Дата публикации: 23.01.2017

Статья просмотрена: 61 раз

Библиографическое описание:

Бойко В. А. Разработка алгоритма сборки и анализа больших геномов // Молодой ученый. — 2017. — №3. — С. 27-28. — URL https://moluch.ru/archive/137/38530/ (дата обращения: 11.12.2018).



Специфика многих современных задач биологии и медицины требует знания генома живых организмов, состоящего из нуклеотидных последовательностей дезоксирибонуклеиновой кислоты (ДНК).

На сегодняшний день существуют и применяются сборщики ДНК, собравшие уже множество известных геномов. Однако когда речь заходит о геномах большой длинны, осложненных значительным количеством повторяющихся участков, то гарантировать однозначную сборку генома становится невозможно. Также большинство сборщиков запрограммированы на работу с входными данными, полученными из строго определённых типов секвенаторов. Такой подход сокращает возможную область применения сборщиков и не удовлетворяет идеологии свободнораспространяемого ПО.

В данной работе представлено описание сборщика лишенного вышеперечисленных недостатков и показан пример его работы.

Описание алгоритма

Как и большинство современных сборщиков, предлагаемый подход использует парные чтения, получаемые из секвенаторов нового поколения, и в связи с этим работает на основе алгоритма использующего граф де Брёйна.

Разделим работу сборщика на следующие этапы:

  1. Нумерация чтений — каждое чтение получает уникальный идентификационный номер, позволяющий однозначно восстановить нуклеотидную последовательность в пределах одного чтения во время обхода графа.
  2. Построение графа де Брёйна и выбор числа k — любой граф может иметь вершины и рёбра. В нашем случае вершинами являются k — меры. Ребро из вершины 1 в вершину 2 проводится только тогда, когда суффикс длинны k — 1 из k — мера представляющего вершину 1, равняется префиксу k — мера вершины 2, т. е. ребро, по сути, является (k + 1) — мером.
  3. Упрощение графа. Если в графе находится путь, у которого входящие и исходящие степени всех внутренних вершин равны 1, то такой путь заменяется ребром.
  4. Нахождение перспективных вершин. Для нахождения перспективных k — меров будем полагать, что вероятность нахождения вершины в исходном геноме тем выше, чем большее количество исходящих ребер она имеет. Обозначим как количество всех исходящих ребер для вершины Тогда общее число всех исходящих ребер: , где n — общее количество всех вершин. Найдем среднее значение исходящих ребер N для всего графа. . Перспективными будем называть вершины имеющие значение исходящих вершин больше N. Количество перспективных вершин может варьироваться в разных библиотеках чтений от 5 % до 10 %.
  5. Построение контигов. Для построения контигов используются начальные вершины обхода, хранящиеся в массиве перспективных вершин.

Реализация ирезультаты

Предложенный алгоритм был реализован на языке программирования Python и был протестирован на синтетической библиотеке чтений. Для хранения графа де Брёйна использовалась хэш-таблица, где ключом является k — мер (вершина графа), а значением исходящие рёбра и идентификационные номера чтений из которых были получены эти рёбра.

Синтетический геном имеет длину порядка 100000 нуклеотидов, средний размер чтений составляет 50 нуклеотидов, число чтений 13168. В эксперименте был проведен анализ качества контигов в зависимости от значения параметра k. Для этого для всех k множества {16, 20,26} была запущенна сборка.

В каждом случае было определено и записано качество картирования, насколько хорошо контиги картировались на референсный геном: считалась доля числа контигов, в которых доля правильных нуклеотидов была больше заданного порога. Результаты приведены в таблице 1.

Таблица 1

Результаты эксперимента по сборке синтетического генома для разных значений k

Длинна kмера

Качество картирования,%

16

70 %

20

81 %

26

97 %

По итогам проверки качества сборки было выбрано значение k = 26.

После получения графа де Брейна встала необходимость произвести сжатие элементарных путей. Был применен алгоритм сжатия, который позволил удалить около 20000 вершин из 111277. В результате получился граф готовый к построению контигов за приемлемое время. Характеристики полученных контигов представлены в таблице 2.

Таблица 2

Характеристики контигов для оптимального значения k— мера

Длина k-мера

Количество контигов

Максимальная длина контига

Минимальная длина контига

Средняя длина контига

26

12809

11454

1602

6398

Время работы сборщика составило 452 минуты, из которых 22 минут заняло построение графа, 2 минут построение сжатого графа, и 428 минут сборка контигов. Необходимо отметить, что предложенный алгоритм является только частью процесса сборки геномной последовательности и полученные фрагменты нуждаются в дальнейшей обработке.

Заключение

В результате работы был разработан прототип сборщика, основанный на графе де Брёйна, который в перспективе позволит справиться с проблемой повторов в больших геномах. В будущем планируется, во-первых — переписать сборщик на более быстрый язык, например C++, во-вторых — использовать в его работе технологию параллельных вычислений CUDA.

Литература:

  1. Illumina [Электронный ресурс]: официальный сайт компании // Режим доступа: http://www.illumina.com/.
  2. Butler, J. Allpaths: de Novo assembly of whole-genome shotgun microreads / J. Butler. — Genome Research, 2008. — 496p.
  3. Daniel, R. Velvet: Algorithms for de Novo short read assembly using de bruijn graphs. Genome Research / R. Daniel. — Lecture Notes Comput., 2008. — 554p.
Основные термины (генерируются автоматически): вершина, ребро, граф, построение графа, качество картирования, CUDA, синтетический геном, предложенный алгоритм, мера, исходящая.


Похожие статьи

Занятие «Раскраски графов» факультативного курса «Элементы...

Вершины пустого графа раскрашиваются независимо — ведь они не связаны между собой ребрами. Они могут быть окрашены в различные цвета или в один и тот же цвет, неважно.

Один способ генерации графа | Статья в журнале...

Данный алгоритм может работать неправильно, если в графе есть ребра равные по весу. Например, полный граф из трех вершин, вес

Предложенная модель графа хороша именно этим: высокие показатели связности кластеров обеспечивают довольно большое количество...

Использование графов для описания модели предприятия при...

Итак, рассмотрим построение моделей предприятия с применением теории графов

Основные термины (генерируются автоматически): UML, модель, баз данных, теория графов, уровень детализации, качество вершин графа, ребро графа, словесное описание...

Графы в Scilab | Статья в сборнике международной научной...

Рассматриваются некоторые аспекты представления графов в системе Scilab.

Задача о раскладке графа на плоскости — в задачу о построении слоев печатных плат в электронике.

Среди этих операций — добавление и удаление ребер (дуг) и вершин (узлов), объединение...

Двухфазный алгоритм решения задачи о клике для разреженных...

В работе показано, что время выполнения предлагаемого алгоритма полиномиально зависит от числа вершин и экспоненциально от древовидной ширины входного

В качестве результата выдать наибольшую клику графа G и ее мощность. Время выполнения фазы1 составляет O(n3).

Методические аспекты обучения доказательству студентов...

5) граф G — ациклический граф, обладающий тем свойством, что если какую-либо пару его несмежных вершин соединить ребром, то полученный граф

В качестве дополнительного упражнения можно предложить доказать эквивалентность любой пары данных высказываний.

Описание порядка выполнения определённого набора инструкций...

вершина, полюс графа, этап построения, очередная вершина, предыдущий цикл, цикл Гамильтона, максимальный цикл Гамильтона, ближайшее ребро, максимальное расстояние, минимальный цикл Гамильтона.

Модели многокритериальных задач

Для постановки задачи составления расписания как задачи раскраски графа строится граф, в котором каждая вершина представляет собой

В качестве такой силы выступает требование минимизации целевой функции или, в терминах генетических алгоритмов, фитнес функции.

Поиск гамильтоновых циклов и цепей в кубических графах

Цепь или простая цепь замкнуты, если . Замкнутая простая цепь, содержащая, по крайней мере, одно ребро, называется циклом.

Основные термины (генерируются автоматически): гамильтонов цикл, Теория графов, граф, вершина, ребро, граф Г, вычислительный алгоритм...

Занятие «Раскраски графов» факультативного курса «Элементы...

Вершины пустого графа раскрашиваются независимо — ведь они не связаны между собой ребрами. Они могут быть окрашены в различные цвета или в один и тот же цвет, неважно.

Один способ генерации графа | Статья в журнале...

Данный алгоритм может работать неправильно, если в графе есть ребра равные по весу. Например, полный граф из трех вершин, вес

Предложенная модель графа хороша именно этим: высокие показатели связности кластеров обеспечивают довольно большое количество...

Использование графов для описания модели предприятия при...

Итак, рассмотрим построение моделей предприятия с применением теории графов

Основные термины (генерируются автоматически): UML, модель, баз данных, теория графов, уровень детализации, качество вершин графа, ребро графа, словесное описание...

Графы в Scilab | Статья в сборнике международной научной...

Рассматриваются некоторые аспекты представления графов в системе Scilab.

Задача о раскладке графа на плоскости — в задачу о построении слоев печатных плат в электронике.

Среди этих операций — добавление и удаление ребер (дуг) и вершин (узлов), объединение...

Двухфазный алгоритм решения задачи о клике для разреженных...

В работе показано, что время выполнения предлагаемого алгоритма полиномиально зависит от числа вершин и экспоненциально от древовидной ширины входного

В качестве результата выдать наибольшую клику графа G и ее мощность. Время выполнения фазы1 составляет O(n3).

Методические аспекты обучения доказательству студентов...

5) граф G — ациклический граф, обладающий тем свойством, что если какую-либо пару его несмежных вершин соединить ребром, то полученный граф

В качестве дополнительного упражнения можно предложить доказать эквивалентность любой пары данных высказываний.

Описание порядка выполнения определённого набора инструкций...

вершина, полюс графа, этап построения, очередная вершина, предыдущий цикл, цикл Гамильтона, максимальный цикл Гамильтона, ближайшее ребро, максимальное расстояние, минимальный цикл Гамильтона.

Модели многокритериальных задач

Для постановки задачи составления расписания как задачи раскраски графа строится граф, в котором каждая вершина представляет собой

В качестве такой силы выступает требование минимизации целевой функции или, в терминах генетических алгоритмов, фитнес функции.

Поиск гамильтоновых циклов и цепей в кубических графах

Цепь или простая цепь замкнуты, если . Замкнутая простая цепь, содержащая, по крайней мере, одно ребро, называется циклом.

Основные термины (генерируются автоматически): гамильтонов цикл, Теория графов, граф, вершина, ребро, граф Г, вычислительный алгоритм...

Обсуждение

Социальные комментарии Cackle

Похожие статьи

Занятие «Раскраски графов» факультативного курса «Элементы...

Вершины пустого графа раскрашиваются независимо — ведь они не связаны между собой ребрами. Они могут быть окрашены в различные цвета или в один и тот же цвет, неважно.

Один способ генерации графа | Статья в журнале...

Данный алгоритм может работать неправильно, если в графе есть ребра равные по весу. Например, полный граф из трех вершин, вес

Предложенная модель графа хороша именно этим: высокие показатели связности кластеров обеспечивают довольно большое количество...

Использование графов для описания модели предприятия при...

Итак, рассмотрим построение моделей предприятия с применением теории графов

Основные термины (генерируются автоматически): UML, модель, баз данных, теория графов, уровень детализации, качество вершин графа, ребро графа, словесное описание...

Графы в Scilab | Статья в сборнике международной научной...

Рассматриваются некоторые аспекты представления графов в системе Scilab.

Задача о раскладке графа на плоскости — в задачу о построении слоев печатных плат в электронике.

Среди этих операций — добавление и удаление ребер (дуг) и вершин (узлов), объединение...

Двухфазный алгоритм решения задачи о клике для разреженных...

В работе показано, что время выполнения предлагаемого алгоритма полиномиально зависит от числа вершин и экспоненциально от древовидной ширины входного

В качестве результата выдать наибольшую клику графа G и ее мощность. Время выполнения фазы1 составляет O(n3).

Методические аспекты обучения доказательству студентов...

5) граф G — ациклический граф, обладающий тем свойством, что если какую-либо пару его несмежных вершин соединить ребром, то полученный граф

В качестве дополнительного упражнения можно предложить доказать эквивалентность любой пары данных высказываний.

Описание порядка выполнения определённого набора инструкций...

вершина, полюс графа, этап построения, очередная вершина, предыдущий цикл, цикл Гамильтона, максимальный цикл Гамильтона, ближайшее ребро, максимальное расстояние, минимальный цикл Гамильтона.

Модели многокритериальных задач

Для постановки задачи составления расписания как задачи раскраски графа строится граф, в котором каждая вершина представляет собой

В качестве такой силы выступает требование минимизации целевой функции или, в терминах генетических алгоритмов, фитнес функции.

Поиск гамильтоновых циклов и цепей в кубических графах

Цепь или простая цепь замкнуты, если . Замкнутая простая цепь, содержащая, по крайней мере, одно ребро, называется циклом.

Основные термины (генерируются автоматически): гамильтонов цикл, Теория графов, граф, вершина, ребро, граф Г, вычислительный алгоритм...

Занятие «Раскраски графов» факультативного курса «Элементы...

Вершины пустого графа раскрашиваются независимо — ведь они не связаны между собой ребрами. Они могут быть окрашены в различные цвета или в один и тот же цвет, неважно.

Один способ генерации графа | Статья в журнале...

Данный алгоритм может работать неправильно, если в графе есть ребра равные по весу. Например, полный граф из трех вершин, вес

Предложенная модель графа хороша именно этим: высокие показатели связности кластеров обеспечивают довольно большое количество...

Использование графов для описания модели предприятия при...

Итак, рассмотрим построение моделей предприятия с применением теории графов

Основные термины (генерируются автоматически): UML, модель, баз данных, теория графов, уровень детализации, качество вершин графа, ребро графа, словесное описание...

Графы в Scilab | Статья в сборнике международной научной...

Рассматриваются некоторые аспекты представления графов в системе Scilab.

Задача о раскладке графа на плоскости — в задачу о построении слоев печатных плат в электронике.

Среди этих операций — добавление и удаление ребер (дуг) и вершин (узлов), объединение...

Двухфазный алгоритм решения задачи о клике для разреженных...

В работе показано, что время выполнения предлагаемого алгоритма полиномиально зависит от числа вершин и экспоненциально от древовидной ширины входного

В качестве результата выдать наибольшую клику графа G и ее мощность. Время выполнения фазы1 составляет O(n3).

Методические аспекты обучения доказательству студентов...

5) граф G — ациклический граф, обладающий тем свойством, что если какую-либо пару его несмежных вершин соединить ребром, то полученный граф

В качестве дополнительного упражнения можно предложить доказать эквивалентность любой пары данных высказываний.

Описание порядка выполнения определённого набора инструкций...

вершина, полюс графа, этап построения, очередная вершина, предыдущий цикл, цикл Гамильтона, максимальный цикл Гамильтона, ближайшее ребро, максимальное расстояние, минимальный цикл Гамильтона.

Модели многокритериальных задач

Для постановки задачи составления расписания как задачи раскраски графа строится граф, в котором каждая вершина представляет собой

В качестве такой силы выступает требование минимизации целевой функции или, в терминах генетических алгоритмов, фитнес функции.

Поиск гамильтоновых циклов и цепей в кубических графах

Цепь или простая цепь замкнуты, если . Замкнутая простая цепь, содержащая, по крайней мере, одно ребро, называется циклом.

Основные термины (генерируются автоматически): гамильтонов цикл, Теория графов, граф, вершина, ребро, граф Г, вычислительный алгоритм...

Задать вопрос