Введение 5
Глава 1. Постановка задачи и профиль ошибок технологии секвенирования lONTORRENT 7
1.1. Основные обозначения 7
1.2. Задача исправления ошибок 8
1.3. Профиль ошибок 8
1.4. Quality-значения технологии lONTORRENT 9
Глава 2. Метод исправления ошибок 13
2.1. Основная идея алгоритма BAYESHAMMER 13
2.2. IonHammer 15
2.3. Алгоритм оценки множества геномных ЛА-меров 16
2.3.1. Статистики по встретившимся ЛА-мерам 16
2.3.2. Кластеризация EDi-графа 18
2.3.3. Субкластеризация 21
2.3.4. Отличия от предыдущей версии IonHammer 23
2.3.5. Качество алгоритма кластеризации 24
2.4. Алгоритм коррекции ошибок 25
2.4.1. Алгоритм коррекции 25
2.4.2. Функция штрафа 29
Глава 3. Оценка качества алгоритма 32
3.1. Сравнение новой версии IonHammer со старой 32
3.2. Сравнение IonHammer с другими алгоритмами коррекции 34
Заключение 38
Список литературы 39
Приложение А. Псевдокод алгоритмов 41
Приложение Б. Наборы данных 44
Приложение В. Сравнение времени работы алгоритмов 45
Приложение Г. Таблицы с качеством коррекции чтений 47
Приложение Д. Результаты сборки генома 53
Совокупность наследственного материала, заключенного в клетке организма, называется геномом. В геноме содержится биологическая информация, определяющая развитие организма. Обычно геномы живых организмов построены на основе макромолекул дезоксирибонуклеиновой кислоты (ДНК). Изучение ДНК позволяет решать широкий спектр задач, среди которых:
• История развития жизни на планете.
• Выявление причин и лечение передающихся по наследству заболеваний.
• Поиск новых антибиотиков и других лекарств.
• Различные задачи генной инженерии (например, разработка генно-модифицированных продуктов).
Для изучения ДНК ее требуется преобразовать из макромолекулы в удобный для анализа формат — строчку над алфавитом {Л, С, G, Т}. Процесс преобразования макромолекулы в строчку называется секвенированием ДНК. Это сложная задача и на сегодняшний день не существует метода, позволяющего получить полную цепочку ДНК. Вместо этого, существующие технологии читают много небольших участков ДНК, на основе которых с помощью специальных алгоритмов затем восстанавливается полная цепочка. К сожалению, секвенированные участки содержат ошибки, что усложняет, а иногда и делает невозможным восстановление полной цепочки и возникает необходимость эти ошибки исправлять. Как и в большинстве задач, универсального «инструмента», позволяющего исправлять ошибки для разных технологий секвенирования не существует — в разных технологиях совершаются разные ошибки и требуются различные подходы к их исправлению.
Одной из самых распространенных технологий секвенирования является технология ILLUMINA. Для данной технологии основой тип ошибок — замена одного нуклеотида на другой. Для коррекции ошибок такого рода существует алгоритм алгоритм BAYESHAMMER [1], являющийся частью геномного ассемблера SPADES [2]. Кроме того, в SPADES реализован алгоритм коррекции ошибок вида «вставка» или «удаление» IONHAMMER, предназначенный для исправления ошибок, возникающий при секвенировании с помощью технологии IONTORRENT. Данная версия алгоритма коррекции обладает несколькими недостатками, из-за которых алгоритм может работать достаточно долго, а также исправляет небольшое число ошибок.
В данной работе предложена и реализована модификация алгоритма IonHammer, а также исследовано качество и время работы новой версии алгоритма.
В данной работе представлена новая версия алгоритма IonHammer, предназначенного для исправления ошибок в чтениях, полученных с помощью технологии IonTorrent.
В рамках данной работы в предыдущую версию IonHammer внесены существенные изменения:
1. Существенно ускорено время работы шаг по поиску компонент связности EDi-графа.
2. Предложен и реализован метод автоматической оценки параметров, необходимый для шага субкластеризации, а также для фильтрации ошибочных кластеров ЛА-меров.
3. Реализован новый метод исправления ошибок в чтениях на основе оценки множества геномных ^fe-меров.
Проведен анализ качества и скорости работы новой версии алгоритма. Предложенная в данной работе модификация IonHammer показывает высокое качество коррекции. Кроме того, новая версия алгоритма является наиболее быстрым и эффективным методом коррекции ошибок в данных IonTorrent.
Проведенные исследования показывают, что высокое качество работы IonHammer позволяет применять в различных задачах анализа и обработки чтений различных бактерий. Одним из таких приложений является задача сборки генома. За счет высокой скорости работы новая версия IonHammer позволяет уменьшить время, необходимое для сборки генома бактерий с помощью геномного ассемблера SPAdes, не теряя при этом в качестве.
В заключение отметим, что современные технологии не стоят на месте. Появляются новые методы секвенирования. Идеи, на которых основан IonHammer, достаточно универсальны и алгоритм коррекции можно будет адаптировать и под будущие технологии, если им будут свойственны ошибки вида «вставки и удаления».
