Введение
Глава 1. Дезоксирибонуклеиновая кислота (ДНК), секвенирование ДНК и анализ данных секвенирования 20
1.1.1. Секвенирование ДНК 22
1.1.2. Существующие методы секвенирования
1.1.2.1. Метод обрыва цепи 24
1.1.2.2. Метод дробовика 24
1.1.2.3. Высокопроизводительные методы секвенирования 25
1.1.3. Метагеномное секвенирование 28
1.2.1. Постановка задачи восстановления геномной последовательности 30
1.2.2. Задача о наименьшей общей надстроке
1.2.2.1. Графовое представление задачи о наименьшей общей надстроке 35
1.2.2.2. Точные алгоритмы решения 37
1.2.2.3. Приближенные алгоритмы решения 38
1.2.2.4. Недостатки сборки генома через поиск наименьшей общей надстроки
1.2.3. Сборка генома на основе данных секвенирования с помощью
1.2.4. Графовая постановка задачи о сборке генома 44
1.2.5. Методы учета двухцепочечной структуры ДНК
1.2.7. Методы учета парной информации 49
1.2.8. Подходы к уменьшению используемой памяти при хранении графа
1.2.9. Существующие программы сборки генома 55
1.2.10. Анализ программ по возможности их использования при обучении59
1.2.11. Использование результатов сборки 60
1.3. Анализ данных метагеномного секвенирования 61
1.3.1. Сравнительный анализ в метагеномике 62
1.3.2. Существующие подходы для сравнительного анализа метагеномов.. 63
1 Л О w (Ґ 69
Выводы по главе 1 71
Глава 2. Автоматизированный метод сборки генома de novo на основе совместного применения графа де Брейна и графа перекрытий 72
2.1. Анализ затрат памяти на хранение графов 72
2.2. Метод сборки генома
2.2.1. Исправление ошибок 76
2.2.2. Сборка квазиконтигов
2.2.3.1. Поиск перекрытий между квазиконтигами 87
2.2.3.2. Поиск и удаление покрываемых квазиконтигов 91
2.2.3.3. Поиск ненайденных перекрытий с помощью найденных 91
2.2.3.4. Удаление транзитивных перекрытий 93
2.2.3.5. Построение графа перекрытий и его упрощение 94
2.2.3.6. Поиски вывод путей в графе 98
2.2.3.7. Нахождение консенсуса для путей
2.3. Реализация предложенных подходов 99
2.4. Экспериментальное исследование
2.4.1. Использованные наборы данных 101
2.4.2. Методология экспериментов 102
2.4.3. Результаты экспериментов 104
2.4.4. Дополнительные эксперименты по анализу требуемых вычислительных ресурсов 107
Выводы по главе 2 111
Глава 3. Автоматизированный метод сравнительного анализа метагеномов, основанный на анализе компонент связности в графе де Брейна 112
3.1. Метод сравнительного анализа метагеномов 112
3.1.3. Выделение компонент связности 116
3.1.4. Построение характеристических векторов 117
3.1.5. Построение матрицы расстояний 118
3.1.6. Выполнение кластеризации и отображение графических результатов
3.2. Реализация предложенного подхода 119
3.3. Экспериментальное исследование
3.3.1. Использованные метагеномные наборы данных 121
3.3.2. Методология экспериментов 123
3.3.3. Эксперименты с симулированными метагеномами: сравнение
3.3.4. Эксперименты с метагеномами микробиоты метро Нью-Йорка: сравнение работы существующих решений 128
3.3.5. Эксперименты с метагеномами микробиоты кишечника человека: оценка работоспособности MetaFast на больших наборах данных 132
3.3.6. Эксперименты с метагеномами виром озер: сравнение возможностей анализа для новых микробиот 134
Выводы по главе 3 141
Глава 4. Внедрение результатов работы 142
4.1. Внедрение результатов работы в учебный процесс в Санкт-Петербургском политехническом университете Петра Великого 142
4.2. Внедрение результатов работы в учебный процесс в Университете ИТМО 144
4.3. Внедрение результатов работы в Казанском (Приволжском) Федеральном Университете 145
Выводы по главе 4 147
Заключение 148
Список источников
