Тема: Скрытые марковские модели на графах сборки

В современной биоинформатике одной из ключевых задач является восстановле­ние первичной последовательности генома и определение его функций, то есть сборка и аннотация генома. Аннотация — это выявление биологической информации из гено­ма, а именно функций генов и свойств их взаимодействий. Наиболее важным этапом аннотации является поиск (предсказание) генов, определение кодирующих последова­тельностей в геноме. Именно этой задаче и будет посвящено основное внимание в дан­ной работе. На данный момент для решения задачи предсказания генов разработано множество программ, например: Glimmer [1], MetaGene [2], FragGeneScan [3], Prodigal [4], GeneMark [5]. Однако большинство из них принимают на вход полные геномные последовательности, что является значительным препятствием, так как зачастую сам геном неизвестен, дано лишь множество его коротких фрагментов — ридов. Для того, чтобы получить полную геномную последовательность из множества ридов, необходимо решить сложную вычислительную задачу сборки генома. Возникает необходимость в методе решения задачи предсказания генов для случая, когда дано множество ридов, не выполняя предварительной сборки генома. Такую задачу можно эффективно решить, используя представление множества ридов в виде графа.
В данной работе будет изучен метод FragGeneScan, основанный на скрытых мар­ковских моделях, а также реализована его модификация, позволяющая решать задачу предсказания генов на графах.
Купить

В ходе исследования была изучена задача предсказания генов и методы её форма­лизации. Введено понятие скрытой марковской модели, рассмотрен алгоритм Витерби как способ нахождения наиболее оптимального пути скрытых состояний. Также опи­сан способ решения задачи предсказания генов при помощи алгоритма Витерби. Была изучена скрытая марковская модель FragGeneScan и основанный на ней алгоритм ре­шения задачи для целой нуклеотидной последовательности (генома). Описана задача предсказания генов на графах, разработан алгоритм для её решения на ориентирован­ных ацикличных графах, основанный на модификации алгоритма Витерби.
Удалось выполнить реализацию описанного алгоритма на языке программирова­ния C++ и показать, что, как на простых графах, так и на графах с развилками и соеди­нениями алгоритм даёт разумные результаты. Такой алгоритм позволяет наследовать свойства FragGeneScan и корректно обрабатывать сдвиги рамки счтения, вызванные ошибками при секвенировании. Было проведено несколько экспериментов на графах, на которых были расположены как сами геномы Escherichia coli, Staphylococcus aureus, Rhodobacter sphaeroides, так и их случайные участки, либо случайно сгенерированные последовательности. Таким образом, основным результатом данной работы является то, что удалось показать перспективность решения задачи предсказания генов на графах в обход сборки генома.
В дальнейшем планируется расширить класс графов, к которому может быть при­менён алгоритм (в первую очередь на графы с циклами), а также применить алгоритм на практике при решении задачи предсказания генов на реальных графах сборки.
Купить