Введение 2
Глава 1. Основные определения 3
Глава 2. Скрытые марковские модели 4
2.1. Определение СММ 4
2.2. Алгоритм Витерби 5
Глава 3. Метод FragGeneScan 6
3.1. Свойства и особенности алгоритма 6
3.2. Скрытая марковская модель FragGeneScan 7
3.3. Решение задачи предсказания генов при помощи модели FragGeneScan 9
Глава 4. Задача предсказания генов на графах 11
4.1. Задача предсказания генов на ориентированных ацикличных графах 11
4.2. Алгоритм Витерби на графах (прямой ход) 12
4.3. Алгоритм Витерби на графах (обратный ход) 14
4.4. Алгоритм решения задачи предсказания генов на графе 15
Глава 5. Валидация 17
5.1. Тривиальный граф 17
5.1.1. Геном на графе 17
5.1.2. Удаления, вставки 19
5.2. Граф с развилками и соединениями 20
Заключение 24
Список литературы 25
В современной биоинформатике одной из ключевых задач является восстановление первичной последовательности генома и определение его функций, то есть сборка и аннотация генома. Аннотация — это выявление биологической информации из генома, а именно функций генов и свойств их взаимодействий. Наиболее важным этапом аннотации является поиск (предсказание) генов, определение кодирующих последовательностей в геноме. Именно этой задаче и будет посвящено основное внимание в данной работе. На данный момент для решения задачи предсказания генов разработано множество программ, например: Glimmer [1], MetaGene [2], FragGeneScan [3], Prodigal [4], GeneMark [5]. Однако большинство из них принимают на вход полные геномные последовательности, что является значительным препятствием, так как зачастую сам геном неизвестен, дано лишь множество его коротких фрагментов — ридов. Для того, чтобы получить полную геномную последовательность из множества ридов, необходимо решить сложную вычислительную задачу сборки генома. Возникает необходимость в методе решения задачи предсказания генов для случая, когда дано множество ридов, не выполняя предварительной сборки генома. Такую задачу можно эффективно решить, используя представление множества ридов в виде графа.
В данной работе будет изучен метод FragGeneScan, основанный на скрытых марковских моделях, а также реализована его модификация, позволяющая решать задачу предсказания генов на графах.
В ходе исследования была изучена задача предсказания генов и методы её формализации. Введено понятие скрытой марковской модели, рассмотрен алгоритм Витерби как способ нахождения наиболее оптимального пути скрытых состояний. Также описан способ решения задачи предсказания генов при помощи алгоритма Витерби. Была изучена скрытая марковская модель FragGeneScan и основанный на ней алгоритм решения задачи для целой нуклеотидной последовательности (генома). Описана задача предсказания генов на графах, разработан алгоритм для её решения на ориентированных ацикличных графах, основанный на модификации алгоритма Витерби.
Удалось выполнить реализацию описанного алгоритма на языке программирования C++ и показать, что, как на простых графах, так и на графах с развилками и соединениями алгоритм даёт разумные результаты. Такой алгоритм позволяет наследовать свойства FragGeneScan и корректно обрабатывать сдвиги рамки счтения, вызванные ошибками при секвенировании. Было проведено несколько экспериментов на графах, на которых были расположены как сами геномы Escherichia coli, Staphylococcus aureus, Rhodobacter sphaeroides, так и их случайные участки, либо случайно сгенерированные последовательности. Таким образом, основным результатом данной работы является то, что удалось показать перспективность решения задачи предсказания генов на графах в обход сборки генома.
В дальнейшем планируется расширить класс графов, к которому может быть применён алгоритм (в первую очередь на графы с циклами), а также применить алгоритм на практике при решении задачи предсказания генов на реальных графах сборки.
