Вычислительные методы для анализа подверженных ошибкам метабологеномных данных тема диссертации и автореферата по ВАК РФ 03.01.09, кандидат наук Гуревич, Алексей Александрович

• Гуревич, Алексей Александрович
• кандидат наук
• 2018

Оглавление диссертации кандидат наук Гуревич, Алексей Александрович

Оглавление

Стр.

Введение

Глава 1. Оценка качества геномных сборок

1.1 Секвенирование генома

1.2 Задача сборки генома

1.2.1 Стратегия Перекрытие-Компоновка-Консенсус

1.2.2 Стратегия графа де Брюйна

1.2.3 Стратегия строкового графа

1.3 Современные способы оценки геномных сборок

1.4 QUAST

1.4.1 Обзор вычислительного конвейера

1.4.2 Метрики качества

1.4.3 Визуализация результатов

1.4.4 Веб-интерфейс

1.5 Результаты

1.5.1 Сравнение сборок данных одноклеточного секвенирования S. aureus

1.5.2 Производительность QUAST

1.5.3 Распространение QUAST в научном сообществе

Глава 2. Оценивание метагеномных сборок

2.1 Метагеномные исследования

2.1.1 Секвенирование некультивируемых бактерий

2.1.2 Особенности метагеномных данных

2.1.3 Алгоритмы сборки метагеномных данных

2.2 MetaQUAST

2.2.1 Обзор вычислительного конвейера

2.2.2 Дополнительные метрики качества

2.2.3 Автоматическое определение видового состава

2.2.4 Определение структурных вариаций и уточнение мисассемблов

Стр.

2.2.5 Визуализация

2.3 Результаты

2.3.1 Чувствительность определения видового состава

2.3.2 Эффективность уточнения мисассемблов

2.3.3 Производительность MetaQUAST

2.3.4 Критическая оценка метагеномного программного обеспечения

Глава 3. Дерепликация пептидных природных соединений

посредством поиска масс-спектров по базе данных

3.1 Особенности PNP

3.1.1 PNP и медицина

3.1.2 Синтез PNP

3.1.3 Новые высокопроизводительные подходы к обнаружению

PNP

3.2 Дерепликация PNP

3.2.1 Существующие стратегии дерепликации PNP

3.3 Алгоритм Dereplicator

3.3.1 Обзор вычислительного конвейера

3.3.2 Создание ложной базы данных

3.3.3 Конструирование теоретических спектров PNP

3.3.4 Оценивание PSM

3.3.5 Вычисление P-значений для PSM

3.3.6 Вычисление FDR

3.4 Тестирование Dereplicator

3.4.1 Тестовые данные

3.4.2 Дерепликация SpectracNPS

3.4.3 Дерепликация Spectra High

Глава 4. Вариативная идентификация пептидных природных

соединений

4.1 Варианты PNP

4.1.1 Задача вариативной идентификации

4.1.2 Семейства PNP

Стр.

4.2 Существующие стратегии вариативной идентификации PNP

4.2.1 Подход на основе спектральных сетей

4.2.2 Подход грубой силы

4.3 Алгоритм \arQuest

4.3.1 Обзор вычислительного конвейера

4.3.2 Оценка соответствия спектр-РКР

4.3.3 Выбор соединений-кандидатов

4.3.4 Предобработка базы РКР

4.3.5 Сопоставление одного спектра всей базе пептидов

4.4 Тестирование \arQuest

4.4.1 Тестовые наборы данных

4.4.2 Результаты

4.4.3 Проверка достоверности идентификаций VarQuest

4.5 Микробиологическая составляющая результатов применения VarQuest

4.5.1 Модификации и мутации, обнаруженные VarQuest

4.5.2 Варианты Р№? найденные VarQuest

4.5.3 Разнообразие РКР, обнаруженное при помощи VarQuest

Заключение

Список сокращений и условных обозначений

Словарь терминов

Список литературы

Список рисунков

Список таблиц

Введение диссертации (часть автореферата) на тему «Вычислительные методы для анализа подверженных ошибкам метабологеномных данных»

Введение

Актуальность темы. Биоинформатика обрабатывает различные виды биологических данных: ДНК, РНК, белки и метаболиты. Эти вещества изучаются соответствующими направлениями исследований в молекулярной биологии — ге-номикой, транскриптомикой, протеомикой и метаболомикой. Новые подотрасли биоинформатики, как правило, объединяют различные типы данных для улучшения возможностей анализа биологических процессов. Успешным примером такого объединения является протеогеномика [1-3], которая использует протеомную информацию для улучшения аннотации генов. Данная работа посвящена другому активно развивающемуся направлению исследований, метабологеномике, отрасли на пересечении геномики и метаболомики [4; 5].

Метабологеномика чрезвычайно важна для современной медицины, поскольку она помогает идентифицировать биологически активные органические соединения, которые могут быть использованы в качестве природного источника новых антибиотиков и других лекарственных средств [6-8]. Ключевыми условиями для возникновения метабологеномики стали появление новых технологий секвенирования в геномике и переход к высокопроизводительному масс-спектрометрическому анализу в метаболомике. Однако для обработки огромного количества подверженных ошибкам геномных и метаболомных данных и для реализации перспектив технологических прорывов в секвенировании и масс-спектрометрии необходима разработка соответствующих вычислительных методов.

Программный конвейер по обработке метабологеномных данных обычно принимает на вход информацию, полученную из генома (данные секвенирова-ния) и метаболома (данные масс-спектрометрии) исследуемого организма, и осуществляет ее анализ вычислительными методами. Обработка геномной информации, как правило, начинается с коррекции и контроля качества данных секвениро-вания. После этого производится сборка этих данных в геномную последовательность, оценка качества этой сборки и идентификация в ней фрагментов, потенциально кодирующих метаболиты. Завершающим шагом является создание базы предполагаемых метаболитов, присутствующих в исследуемом образце. Анализ метаболомной информации обычно включает в себя сверку масс-спектров с базой уже известных метаболитов (так называемая дерепликация от англ. dereplication)

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

Почти каждый из перечисленных этапов метабологеномного конвейера представляет собой сложную вычислительную задачу из-за огромных объемов данных, которые часто также содержат программные и аппаратные ошибки. Некоторые из этих задач уже имеют устоявшиеся решения, так например, в настоящее время доступны десятки программных средств для сборки геномных последовательностей [9-22]. В то же время некоторые другие задачи остаются по-прежнему нерешенными. В данной работе рассмотрены две из таких задач, первая из них относится к геномной, а вторая — к метаболомной составляющим конвейера. В обоих случаях требуется решить схожие по постановке задачи: сравнить экспериментальные данные с эталонным (референсным) образцом. При этом в этих сравнениях требуется учитывать, что референс может отличаться от исследуемого образца из-за мутаций или модификаций. Для обеих рассматриваемых задач разрабатываются алгоритмические решения и их реализация в новых программных инструментах.

Первой задачей, рассматриваемой в данной работе, является оценка качества геномных сборок. Современные технологии секвенирования ДНК не позволяют прочитать полную последовательность генома. Напротив, они считывают большое количество коротких геномных последовательностей, которые впоследствии объединяются друг с другом в более длинные фрагменты при помощи специализированных программ. Ошибки при считывании и длинные геномные повторы превращают процесс геномной сборки в сложную вычислительную задачу. Различные алгоритмы используют многочисленные эвристики для преодоления этих сложностей, что в итоге приводит к большим различиям в получаемых сборках. Таким образом возникает вопрос о том, как оценивать качество геномных сборок и как сравнивать их между собой. Эта задача особенно важна, поскольку последующий геномный анализ очень чувствителен к качеству используемой сборки [23].

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

но не полностью соответствующим просеквенированному организму Этот факт приводит к необходимости различать естественные вариации в геномной последовательности и отклонения, вызванные ошибками алгоритмов сборки. Более того, в некоторых случаях, таких как метагеномные исследования (изучение сложных бактериальных сообществ и образцов из окружающей среды), представленные в образце организмы полностью неизвестны и соответствующие референс-ные геномы должны быть найдены вычислительными методами. В диссертации описывается семейство инструментов QUAST, предназначенное для решения задач оценки качества геномных сборок. Этот программный пакет включает в себя утилиту QUAST [24] для работы с геномами отдельных организмов и ее расширение, MetaQUAST [25], для метагеномных исследований.

Вторая рассматриваемая в работе задача — дерепликация известных метаболитов и их новых вариантов посредством идентификации масс-спектров по базе данных. Данная работа специализируется на идентификации пептидных природных соединений (англ. peptidic natural products, PNP), которые представляют собой важный и широко используемый класс метаболитов (часто называемых просто природными соединениями, англ. natural products). Сложная химическая структура (например, циклическая или ветвь-циклическая) и наличие нестандартных аминокислот значительно усложняют поиск PNP и делают невозможным использование традиционных протеомных методов для решения этой задачи [26]. Еще одна серьезная проблема, связанная с дерепликацией PNP, — природная изменчивость этих соединений. Большинство PNP образуют семейства родственных пептидов, где соединения имеют сходные или идентичные структуры, а аминокислотные последовательности различаются в одной или нескольких позициях. Во многих случаях PNP отсутствует в базе данных, но там содержатся более распространенные представители этого семейства. Нахождение неизвестного соединения по его известным вариантам называется вариативной (или устойчивой к модификациям) идентификацией (дерепликацией) и имеет решающее значение для исследования PNP.

Недавно появившаяся платформа Global Natural Products Social molecular networking infrastructure (GNPS, англ. инфраструктура для международной социальной молекулярной сети природных соединений) [27] объединила вместе более сотни лабораторий, которые уже сгенерировали более миллиарда масс-спектров природных соединений. Однако их интерпретация по-прежнему затруднена, поскольку вычислительные методы для идентификации PNP все еще находятся на

стадии становления. В диссертации описывается метод высокопроизводительной идентификации РКР и его реализация в новом программном инструменте под названием Dereplicator [28]. Поскольку все существующие способы расширения Dereplicator для работы в режиме вариативной идентификации имеют серьезные ограничения и не могут применяться в высокопроизводительных программных конвейерах, был разработан VarQuest [29], новый подход к этой задаче. Тестирование VarQuest показывает, что он позволяет выполнить устойчивый к модификациям поиск по всей GNPS и ведет к важным с микробиологической точки зрения открытиям.

Цели и задачи исследования. Цель данного исследования заключается в разработке новых методов решения двух важных метабологеномных задач и их реализации в программных инструментах. Первой задачей является оценка качества геномных сборок. Второй — идентификация PNP посредством поиска масс-спектров по базе данных. Для достижения этой цели были решены следующие подзадачи. Для задачи оценки геномных сборок:

1. изучение существующих метрик качества сборки, выбор лучших и разработка новых, если это необходимо;

2. реализация механизмов вычисления выбранных метрик;

3. разработка алгоритма для разграничения ошибок сборки от естественных вариаций в просеквенированном организме;

4. изучение и обработка особенностей метагеномных сборок для последующей оценки их качества.

Для задачи идентификации РКР:

1. разработка метода для стандартной идентификации Р№, который совместим с высокопроизводительным анализом данных;

2. изучение существующих методов вариативной идентификации РКР и их ограничений;

3. проектирование и реализация нового алгоритма для вариативной идентификации PNP, устраняющего ограничения существующих методов;

4. реализация веб-интерфейсов для разработанных инструментов;

5. сравнительный анализ разработанных инструментов на крупномасштабных наборах данных.

Общая методика работы. Данная работа базируется на использовании следующих методов, теорий и алгоритмов:

- алгоритмы обработки строк (в частности, алгоритмы выравнивания последовательностей);

- теория графов;

- статистическое моделирование;

- модульное и объектно-ориентированное программирование на языках C++ и Python.

Практическая ценность и научная новизна. Результатами выполненной работы стали следующие новые программные продукты для биоинформатики:

- пакет QUAST (включающий QUAST и MetaQUAST): набор инструментов для оценки качества геномных и метагеномных сборок (http:

//cab.spbu.ru/software/quast/ и http://cab.spbu.ru/ software/metaquast/, зарегистрированы Роспатентом, свидетельства о регистрации под номерами 2016661824 и 2016661838 соответственно);

- Dereplicator и VarQuest: программные продукты для стандартной и вариативной идентификации PNP посредством поиска масс-спектров по базе данных (http://cab.spbu.ru/software/dereplicator/и http://cab.spbu.ru/software/varquest/ соответственно).

Пакет QUAST стал широко распространенным инструментом в области геномных сборок. Зафиксировано более чем 35 000 скачиваний программы1 и более 500 ссылок в Web of Science Core Collection2 с момента старта проекта летом 2012 года и первой публикации в 2013 году Насколько известно, Dereplicator и VarQuest являются первыми высокопроизводительными методами для стандартной и вариативной идентификации PNP соответственно. Оба метода были протестированы на более чем ста миллионах общедоступных тандемных масс-спектров на платформе GNPS. Инструменты идентифицировали на порядок больше PNP (и их новых вариантов), чем все предыдущие попытки дерепликации этих данных [28; 29]. VarQuest в настоящий момент является единственным устойчивым к модификациям методом идентификации PNP, способным обработать данные со всей платформы GNPS [29].

1общее количество скачиваний всех версий пакета по данным сайта https://sourceforge.net/ p/quast (по состоянию на 31 марта 2018 г.)

2общее количество ссылок на [24] и [25] по данным сайта https://www.webofknowledge.com (по состоянию на 31 марта 2018 г.)

Апробация работы. Результаты работы докладывались на семинарах лаборатории "Центр олгоритмической биотехнологии" (Санкт-Петербургский государственный университет), а также на следующих конференциях и встречах:

1. Increased diversity of peptidic natural products revealed by modification-tolerant database search of mass spectra. Устный доклад на конференции RECOMB 2018 (освещение статьи о VarQuest). Париж, Франция. Апрель 2018.

2. VarQuest: modification-tolerant identification of novel variants of peptidic antibiotics and other natural products. Постерный доклад на конференции ISMB/ECCB 2017. Прага, Чехия. Июль 2017.

3. Genome assembly evaluation with QUAST. Устный доклад на конференции BiATA 2017. Санкт-Петербург, Россия. Август 2017.

4. Identification of novel peptidic antibiotics via large scale scoring of mass spectra against natural products databases (одновременно о Dereplicator и VarQuest). Постерный доклад на конференции RECOMB 2017. Гонконг, Китай. Май, 2017; Постерный доклад на конференции ISMB/ECCB 2017. Прага, Чехия. Июль 2017.

5. MetaQUAST: evaluating metagenome assemblies. Приглашенный устный доклад на встрече по разработке инструментов оценивания качества для CAMI. Берлин, Германия. Май 2015.

6. QUAST: quality assessment tool for genome assemblies. Постерный доклад на конференции RECOMB 2013. Пекин, Китай. Апрель 2013.

Постерный доклад о VarQuest был также принят на конференцию ASMS 2018 и будет представлен в Сан-Диего, США в июне 2018.

Основные научные результаты, выносимые на защиту:

1. Разработаны и реализованы программы для оценки качества геномных (QUAST) и метагеномных (MetaQUAST) сборок. Программы вычисляют корректность, полноту, протяженность и другие характеристики качества сборок с использованием их выравнивания на соответствующие референсные геномы. В программах реализованы алгоритмы, позволяющие работать при неточных референсах (отделение реальных ошибок сборки от естественных вариаций в геноме просеквенированного организма), а также при полностью неизвестном составе исследуемого образца (автоматическое определение состава и скачивание соответствующих референсных геномов из базы NCBI).

2. Разработаны и реализованы программы для стандартной (Dereplicator) и вариативной (VarQuest) идентификации PNP посредством поиска масс-спектров по базе данных. Программы вычисляют статистическую значимость обнаруженных соединений, что позволяет значительно уменьшить число ложноположительных идентификаций. VarQuest выполняет поиск, устойчивый к любым модификациям в PNP. Более того, VarQuest позволяет идентифицировать модифицированные соединения, даже если их известная форма не представлена во входных масс-спектрометрических данных.

3. Проведена апробация программ для идентификации PNP на более чем ста миллионах масс-спектров на платформе GNPS. Апробация показала применимость разработанных подходов в высокопроизводительных конвейерах для обработки метаболомных данных. Анализ полученных результатов показал большое разнообразие PNP на химическом уровне, что соотносится с недавно открытым разнообразием PNP на уровне геномных последовательностей (разнообразие биосинтетических кластеров генов, кодирующих PNP) [30; 31].

Публикации. Основные результаты данной работы описаны в четырех статьях [24; 25; 28; 29] (все в соавторстве), опубликованных в журналах, индексируемых базами данных Web of Science Core Collection и Scopus (включая две статьи в журналах Nature Publishing Group). Практическое применение разработанного программного обеспечения также описано в семи работах [16; 18; 32-36], соавтором которых является автор диссертации. Эти работы опубликованы в журналах, индексируемых базами данных Web of Science Core Collection и Scopus (включая одну статью в журнале Nature Publishing Group).

Личный вклад. Автор диссертации играл ведущую роль в исследованиях, разработке, программной реализации и написании текста в работах про QUAST [24] и VarQuest [29]. В работе по MetaQUAST [25] автору принадлежит ведущая роль в написании текста, разработке и тестировании соответствующего инструмента, а также участие в программной реализации части алгоритмов. В работе по Dereplicator [28] автор реализовал веб-версию инструмента на платформе GNPS, а также участвовал в программной реализации основного кода инструмента и его масштабном тестировании.

Объем и структура работы. Диссертация состоит из введения, четырех глав и заключения. Полный объем диссертации составляет 118 страниц, включая 24 рисунка и 8 таблиц. Список литературы содержит 169 наименований.

В первой главе описывается задача сборки генома и мотивация для создания инструментария по оценке качества геномной сборки. Обсуждаются аспекты оценивания качества на основе референсного генома. Подробно показаны программный конвейер разработанного инструмента оценки качества QUAST и его основные алгоритмы. Данная глава частично адаптирована из [24].

Вторая глава посвящена адаптации QUAST к анализу метагеномных сборок. Показаны сложности и особенности метагеномных исследований. Представлен MetaQUAST — расширение QUAST для работы с учетом указанных особенностей данных. Данная глава частично адаптирована из [25].

Третья глава посвящена идентификации PNP посредством поиска масс-спектров по базе данных. Описаны важность обнаружения PNP и сложности, возникающие при этом. Показаны представление химических структур в виде графовой модели PNP и генерация на ее основе теоретических спектров. Приводятся функция ранжирования, процедура оценки статистической значимости идентификаций и весь программный конвейер Dereplicator. Показаны результаты обработки всей GNPS с помощью Dereplicator. Данная глава частично адаптирована из [28].

В четвертой главе обсуждаются особенности вариативной идентификации PNP. Описаны существующие методы и их недостатки. Предлагается алгоритм VarQuest для вариативной идентификации PNP. Проводится всестороннее сравнение VarQuest с конкурирующими подходами и стандартной идентификацией PNP с использованием Dereplicator. Демонстрируется валидация соединений, найденных VarQuest. Результаты устойчивого к модификациям анализа всего GNPS обсуждаются с микробиологической точки зрения. Данная глава частично адаптирована из [29].

Глава 1. Оценка качества геномных сборок 1.1 Секвенирование генома

Полногеномное секвенирование — это процесс определения точного порядка нуклеотидов в геноме организма. Знание полной последовательности ДНК имеет широкий спектр применений от эволюционной и молекулярной биологии до персонализированной медицины и криминалистики. Бактериофаг ФХ174 стал первым полностью просеквенированным геномом. Эта работа была выполнена Фредериком Сенгером (англ. Frederick Sanger) и его коллегами в 1977 году [37]. Метод Сенгера использовался и в дальнейшем для выяснения исходной последовательности многих коротких геномов, таких как вирусы, митохондрии и хлоро-пласты в 1970-1980 гг. [38-41]. Однако этот подход был очень дорогим и трудоемким, так как требовал большого объема ручной работы.

Переход к автоматизированным методам секвенирования в 1990-х годах позволил определить последовательность более крупных геномов. Haemophilus influenzae (гемофильная палочка) стала первым свободноживущим организмом, чей геном был полностью отсеквенирован. Эта бактерия была просеквенирована в 1995 году с использованием секвенирования по методу дробовика (англ. shotgun sequencing) [42]. Первый геном эукариотического организма, Saccharomyces cerevisiae (пекарские дрожжи), и первый геном животного, Caenorhabditis elegans (круглый червь), были также просеквенированы в 1990-е годы [43; 44]. Первая черновая версия последовательности генома человека была опубликована в 2001 году [45; 46]. Международный Проект Человеческий Геном (англ. The Human Genome Project, HGP) опубликовал полную версию человеческого генома в 2003 году и представил оценку качества этой последовательности в 2004 [47]. Тем не менее последовательность генома человека все еще находится в процессе уточнения и анализа, например, его самая последняя версия была выпущена в конце 2017 года (GRCh38.p12).

В начале 2000-х годов метод секвенирования по Сенгеру был практически повсеместно заменен так называемыми технологиями высокопроизводительного секвенирования (англ. High-Throughput Sequencing) или секвенирования нового поколения (СНП, англ. Next-Generation Sequencing, NGS). Технологии СНП зна-

чительно сократили стоимость и время секвенирования. Наиболее известные методы СНП включают в себя Illumina/Solexa [48] (секвенирование синтезом), Ion Torrent [49] (ионное полупроводниковое секвенирование) и другие. В настоящее время тысячи геномов были просеквенированы с использованием СНП. Тем не менее рынок технологий секвенирования генома постоянно развивается, и недавнее лидерство технологий СНП сейчас уже стоит под вопросом в связи с быстрым улучшением так называемых технологий секвенирования длинными ридами (СДР, англ. Long-Read Sequencing, LRS). Технологии СДР в данный момент представлены методом одномолекулярного секвенирования в реальном времени от компании Pacific Biosciences [50] и нанопоровым секвенированием от компании Oxford Nanopore Technologies [51]. Эти технологии позволяют считывать фрагменты ДНК на несколько порядков длиннее, чем прочитанные при помощи СНП. В то же время СДР остается достаточно дорогостоящей технологией, и зачастую она производит данные со значительно более высоким уровнем ошибок, чем у ее конкурентов, работающих по принципу СНП.

1.2 Задача сборки генома

Несмотря на прорыв в методах секвенирования, до сих пор нет технологии, способной считывать полные последовательности хромосомы за один проход. Напротив, современные подходы считывают множество относительно коротких фрагментов ДНК, называемых прочтения (англ. reads) (обычно 100-500 пар нуклеотидов (п.н., англ. base pairs, bp) у технологий СНП и до десятков тысяч п.н. у СДР). Компьютерные программы используют перекрывающиеся концы разных прочтений для восстановления их взаимного расположения и последующей сборки в более крупные сегменты, называемые контиги (англ. contigs). Эта процедура является сложной вычислительной задачей из-за огромного количества прочтений, наличия ошибок в них и таких особенностей геномных последовательностей, как четырехбуквенный алфавит и наличие множества повторяющихся фрагментов.

Существует несколько классических подходов к решению задачи геномной сборки (Рисунок 1.1). Все они используют теорию графов, но каждый из подходов определяет вершины и ребра по-разному. Последовательность генома закодиро-

А

А) Последовательность генома и соответствующие ей прочтения. Геном состоит из трех уникальных фрагментов, разделенных повторяющейся последовательностью. Б) граф перекрытия; В) граф де Брюйна; Г) строковый граф. Данный рисунок частично адаптирован из [10].

Рисунок 1.1 — Различные графы геномной сборки.

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

1.2.1 Стратегия Перекрытие-Компоновка-Консенсус

Подход Перекрытие-Компоновка-Консенсус (англ. Overlap-Layout-Consensus, OLC) создает граф перекрытий, где вершины представляют собой прочтения и две вершины соединены, если соответствующие им прочтения перекрываются (Рисунок 1.1Б). Для построения такого графа требуется найти перекрытия между всеми парами прочтений, что является очень трудоемкой задачей даже при использовании дополнительных эвристик [9]. Геномные сборщики, работающие на основе подхода OLC, такие как Celera Assembler [9], ARACHNE [52] и PHRAP [53], успешно применялись для обработки прочтений, полученных по методу Сенгера. Однако подход OLC плохо совместим с данными СНП, поскольку количество прочтений огромно, а сами они достаточно короткие. Тем не менее идея OLC метода по-прежнему используется. Недавно были разработаны сразу несколько геномных сборщиков, основанных на этом подходе, такие как Canu [22] и FALCON [19], которые предназначены для сборки данных СДР.

1.2.2 Стратегия графа де Брюйна

Этот метод сначала разрезает прочтения на более короткие k-меры (строки длины k), а затем использует все полученные k-меры для построения графа де Брюйна (англ. de Bruijn graph, DBG). Вершины DBG являются k-мерами, и две вершины связаны, если они являются префиксом и суффиксом k + 1-мера, присутствующего во входных прочтениях (Рисунок 1.1В). Граф также может быть упрощен в так называемый сжатый DBG путем замены неветвящихся путей на отдельные ребра. EULER — первый геномный сборщик, основанный на DBG, был опубликован в 2001 году Павлом Певзнером и его коллегами [10]. Развитие технологий СНП продемонстрировало перспективность подхода DBG. С тех пор на базе этого метода было разработано множество геномных сборщиков по данным СНП, таких как Velvet [11], ABySS [12], AllPath-LG [15], SOAPdenovo [13], SPAdes [16], IDBA-UD [17] и другие. Более того, DBG был также адаптирован

для обработки данных СДР, причем как в сборщиках для смешанных СНП-СДР данных [20], так и в работающих исключительно с СДР прочтениями [21].

1.2.3 Стратегия строкового графа

Строковые графы (англ. string graph) были введены Юджином Майерсом (англ. Eugene Myers) в 2005 году. Эта концепция является улучшением OLC подхода. Строковый граф создается путем конструирования графа перекрытий и дальнейшего объединения перекрывающихся прочтений и удаления транзитивных ребер и прочтений, которые содержатся в некотором другом прочтении [54] (Рисунок 1.1Г). По сравнению с DBG, строковый граф намного сложнее построить, но он обычно лучше разрешает неоднозначности, вызванные короткими повторениями в геноме (длиннее, чем k, но короче длины прочтения) и более компактен для хранения. Наиболее широко используемой программной реализацией данного метода является SGA [14].

1.3 Современные способы оценки геномных сборок

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

Список литературы диссертационного исследования кандидат наук Гуревич, Алексей Александрович, 2018 год

Список литературы

1. Jaffe J. D., BergH. C., Church G. M. Proteogenomic mapping as a complementary method to perform genome annotation // Proteomics. — 2004. — Jan. — Vol. 4, no. 1. — Pp. 59-77.

2. Whole proteome analysis of post-translational modifications: applications of mass-spectrometry for proteogenomic annotation / N. Gupta, S. Tanner, N. Jaitly et al. // Genome Res. — 2007. — Sep. — Vol. 17, no. 9. — Pp. 1362-1377.

3. Proteogenomics: needs and roles to be filled by proteomics in genome annotation / C. Ansong, S. O. Purvine, J. N. Adkins et al. // Brief Funct Genomic Proteomic.

— 2008. — Jan. — Vol. 7, no. 1. — Pp. 50-62.

4. Kelleher N. L. Metabologenomics: Discovery of new natural products and their biosynthetic gene clusters by genome-informed metabolomics // Planta Med. — 2015. — Vol. 81, no. 11. — P. IL52. — IL52.

5. Metabologenomics: Correlation of Microbial Gene Clusters with Metabolites Drives Discovery of a Nonribosomal Peptide with an Unusual Amino Acid Monomer / A. W. Goering, R. A. McClure, J. R. Doroghazi et al. // ACS Cent Sci. — 2016. — Feb. — Vol. 2, no. 2. — Pp. 99-108.

6. Li J. W, Vederas J. C. Drug discovery and natural products: end of an era or an endless frontier? // Science. — 2009. — Jul. — Vol. 325, no. 5937. — Pp. 161165.

7. Harvey A. L., Edrada-Ebel R., Quinn R. J. The re-emergence of natural products for drug discovery in the genomics era // Nat Rev Drug Discov. — 2015. — Feb.

— Vol. 14, no. 2. — Pp. 111-129.

8. Moloney M. G. Natural Products as a Source for Novel Antibiotics // Trends Pharmacol. Sci. — 2016. — Aug. — Vol. 37, no. 8. — Pp. 689-701.

9. A whole-genome assembly of Drosophila / E. W. Myers, G. G. Sutton, A. L. Delcher et al. // Science. — 2000. — Vol. 287, no. March. — Pp. 2196-205.

10. Pevzner P. A., TangH., Waterman M. S. An Eulerian path approach to DNA fragment assembly // PNAS. — 2001. — Vol. 98, no. 17. — Pp. 9748-53.

11. Zerbino D. R., BirneyE. Velvet: Algorithms for de novo short read assembly using de Bruijn graphs // Genome Research. — 2008. — Vol. 18, no. 5. — Pp. 821-9.

12. ABySS: A parallel assembler for short read sequence data ABySS : A parallel assembler for short read sequence data / J. T. Simpson, K. Wong, S. D. Jackman et al. // Genome Res. — 2009. — Vol. 19. — Pp. 1117-23.

13. Li R. et al. De novo assembly of human genomes with massively parallel short read sequencing // Genome Res. — 2010. — Feb. — Vol. 20, no. 2. — Pp. 265272.

14. Simpson J. T., Durbin R. Efficient construction of an assembly string graph using the FM-index // Bioinformatics. — 2010. — Jun. — Vol. 26, no. 12. — Pp. i367-373.

15. Gnerre S. et al. High-quality draft assemblies of mammalian genomes from massively parallel sequence data // Proc Natl Acad Sci USA. — 2011. — Vol. 108, no. 4.— Pp. 1513-1518.

16. SPAdes: A New Genome Assembly Algorithm and Its Applications to Single-Cell Sequencing / A. Bankevich, S. Nurk, D. Antipov et al. // Journal of Computational Biology. — 2012. — Vol. 19. — Pp. 455-77.

17. Peng Y et al. IDBA-UD: A de novo assembler for single-cell and metagenomic sequencing data with highly uneven depth. // Bioinformatics. — 2012. — Vol. 28, no. 11. — Pp. 1-8. — URL: http://www.ncbi.nlm.nih.gov/pubmed/22495754.

18. Assembling single-cell genomes and mini-metagenomes from chimeric MDA products / S. Nurk, A. Bankevich, D. Antipov et al. // J. Comput. Biol. — 2013.

— Oct. — Vol. 20, no. 10. — Pp. 714-737.

19. Phased diploid genome assembly with single-molecule real-time sequencing / C. S. Chin, P. Peluso, F. J. Sedlazeck et al. // Nat. Methods. — 2016. — Dec.

— Vol. 13, no. 12. — Pp. 1050-1054.

20. hybridSPAdes: an algorithm for hybrid assembly of short and long reads / D. An-tipov, A. Korobeynikov, J. S. McLean, P. A. Pevzner // Bioinformatics. — 2016.

— Apr. — Vol. 32, no. 7. — Pp. 1009-1015.

21. Assembly of long error-prone reads using de Bruijn graphs / Y. Lin, J. Yuan, M. Kolmogorov et al. // Proc. Natl. Acad. Sci. U.S.A. — 2016. — Dec. — Vol. 113, no. 52. — Pp. E8396-E8405.

22. Canu: scalable and accurate long-read assembly via adaptive k-mer weighting and repeat separation / S. Koren, B. P. Walenz, K. Berlin et al. // Genome Res. — 2017.

— May. — Vol. 27, no. 5. — Pp. 722-736.

23. Ekblom R., Wolf J. B. A field guide to whole-genome sequencing, assembly and annotation//EvolAppl. — 2014. — Nov. — Vol. 7, no. 9. — Pp. 1026-1042.

24. Gurevich A. et al. QUAST: quality assessment tool for genome assemblies // Bioinformatics. — 2013. — Vol. 29, no. 8. — Pp. 1072-1075.

25. Mikheenko A., Saveliev V., Gurevich A. MetaQUAST: evaluation of metagenome assemblies // Bioinformatics. — 2016. —Apr. — Vol. 32, no. 7. — Pp. 10881090.

26. Mohimani H., Pevzner P. A. Dereplication, sequencing and identification of pep-tidic natural products: from genome mining to peptidogenomics to spectral networks // Nat Prod Rep. — 2016. — Jan. — Vol. 33, no. 1. — Pp. 73-86.

27. Wang M et al. Sharing and community curation of mass spectrometry data with Global Natural Products Social Molecular Networking // Nat. Biotechnol. — 2016. — Aug. — Vol. 34, no. 8. — Pp. 828-837.

28. Dereplication of peptidic natural products through database search of mass spectra / H. Mohimani, A. Gurevich, A. Mikheenko et al. // Nat. Chem. Biol. — 2017.

— Jan. — Vol. 13, no. 1. — Pp. 30-37.

29. Increased diversity of peptidic natural products revealed by modification-tolerant database search of mass spectra / A. Gurevich, A. Mikheenko, A. Shlemov et al. // Nature Microbiol. — 2018. — Mar. — Vol. 3, no. 3. — Pp. 319-327.

30. Schmidt E. W. The hidden diversity of ribosomal peptide natural products // BMC Biol. — 2010. — Jun. — Vol. 8. — P. 83.

31. IMG-ABC: new features for bacterial secondary metabolism analysis and targeted biosynthetic gene cluster discovery in thousands of microbial genomes / M. Had-

jithomas, I. A. Chen, K. Chu et al. // Nucleic Acids Res. — 2017. — Jan. — Vol. 45, no. D1. — Pp. D560-D565.

32. ExSPAnder: A universal repeat resolver for DNA fragment assembly / An-drey D. Prjibelski, Irina Vasilinetc, Anton Bankevich et al. // Bioinformatics. — 2014. — Vol. 30, no. 12. — Pp. 293-301.

33. Assembling short reads from jumping libraries with large insert sizes /1. Vasilinetc, A. D. Prjibelski, A. Gurevich et al. // Bioinformatics. — 2015. — Oct. — Vol. 31, no. 20. — Pp. 3262-3268.

34. Critical Assessment of Metagenome Interpretation-a benchmark of metagenomics software / A. Sczyrba, P. Hofmann, P. Belmann et al. // Nat. Methods. — 2017. — Nov. — Vol. 14, no. 11. — Pp. 1063-1071.

35. Spatial Molecular Architecture of the Microbial Community of a Peltigera Lichen / N. Garg, Y. Zeng, A. Edlund et al. // mSystems. — 2016. — Vol. 1, no. 6.

36. Metabolic Fingerprints from the Human Oral Microbiome Reveal a Vast Knowledge Gap of Secreted Small Peptidic Molecules / A. Edlund, N. Garg, H. Mohi-mani et al. // mSystems. — 2017. — Vol. 2, no. 4.

37. Nucleotide sequence of bacteriophage phi X174 DNA / F. Sanger, G. M. Air, B. G. Barrell et al. // Nature. — 1977. — Feb. — Vol. 265, no. 5596. — Pp. 687695.

38. Nucleotide sequence of bacteriophage lambda DNA / F. Sanger, A. R. Coulson, G. F. Hong et al. // J. Mol. Biol. — 1982. — Dec. — Vol. 162, no. 4. — Pp. 729773.

39. The complete DNA sequence of vaccinia virus / S. J. Goebel, G. P. Johnson, M. E. Perkus et al. // Virology. — 1990. — Nov. — Vol. 179, no. 1. — Pp. 247266.

40. The DNA sequence of the human cytomegalovirus genome / A. T. Bankier, S. Beck, R. Bohni et al. // DNA Seq. — 1991. — Vol. 2, no. 1. — Pp. 1-12.

41. Chloroplast gene organization deduced from complete sequence of liverwort Marchantia polymorpha chloroplast DNA / Kanji Ohyama, Hideya Fukuzawa, Takayuki Kohchi et al. // Nature. — 1986. — Vol. 322. — Pp. 572 - 574.

42. Whole-genome random sequencing and assembly of Haemophilus influenzae Rd / R. D. Fleischmann, M. D. Adams, O. White et al. // Science. — 1995. — Jul. — Vol. 269, no. 5223. — Pp. 496-512.

43. Life with 6000 genes / A. Goffeau, B. G. Barrell, H. Bussey et al. // Science. — 1996. — Oct. — Vol. 274, no. 5287. — Pp. 563-567.

44. elegans Sequencing Consortium The C. Genome sequence of the nematode C. elegans: a platform for investigating biology // Science. — 1998. — Dec. — Vol. 282, no. 5396. — Pp. 2012-2018.

45. Venter J. C. et al. The sequence of the human genome // Science. — 2001. — Feb.

— Vol. 291, no. 5507. — Pp. 1304-1351.

46. Lander E. S. et al. Initial sequencing and analysis of the human genome // Nature.

— 2001. — Feb. — Vol. 409, no. 6822. — Pp. 860-921.

47. Project The Human Genome. Finishing the euchromatic sequence of the human genome // Nature. — 2004. — Oct. — Vol. 431, no. 7011. — Pp. 931-945.

48. Bennett S. Solexa Ltd // Pharmacogenomics. — 2004. — Jun. — Vol. 5, no. 4.

— Pp. 433-438.

49. Pennisi E. Genomics. Semiconductors inspire new sequencing technologies // Science. — 2010. — Mar. — Vol. 327, no. 5970. — P. 1190.

50. Real-time DNA sequencing from single polymerase molecules / J. Eid, A. Fehr, J. Gray et al. // Science. — 2009. — Jan. — Vol. 323, no. 5910. — Pp. 133-138.

51. Schneider G. F., Dekker C. DNA sequencing with nanopores // Nat. Biotechnol.

— 2012. — Apr. — Vol. 30, no. 4. — Pp. 326-328.

52. ARACHNE: a whole-genome shotgun assembler / S. Batzoglou, D. B. Jaffe, K. Stanley et al. // Genome Res. — 2002. — Jan. — Vol. 12, no. 1. — Pp. 177-189.

53. de la Bastide M., McCombie W. R. Assembling genomic DNA sequences with PHRAP // Curr Protoc Bioinformatics. — 2007. — Mar. — Vol. Chapter 11. — P. Unit11.4.

54. Myers E. W. The fragment assembly string graph // Bioinformatics. — 2005. — Sep. — Vol. 21 Suppl 2. — Pp. 79-85.

55. Earl D. et al. Assemblathon 1: a competitive assessment of de novo short read assembly methods// Genome Res. — 2011. —Dec. — Vol. 21, no. 12. — Pp. 22242241.

56. Bradnam K. et al. Assemblathon 2: evaluating de novo methods of genome assembly in three vertebrate species // Gigascience. — 2013. — Vol. 2, no. 1. — P. 10.

57. Salzberg S. et al. GAGE: A critical evaluation of genome assemblies and assembly algorithms // Genome Res. — 2012. — Mar. — Vol. 22, no. 3. — Pp. 557-567.

58. Magoc T. et al. GAGE-B: an evaluation of genome assemblers for bacterial organisms // Bioinformatics. — 2013. —Jul. — Vol. 29, no. 14. — Pp. 1718-1725.

59. Simao F. et al. BUSCO: assessing genome assembly and annotation completeness with single-copy orthologs // Bioinformatics. — 2015. — Jun.

60. Clark S. et al. ALE: a generic assembly likelihood evaluation framework for assessing the accuracy of genome and metagenome assemblies // Bioinformatics. — 2013. — Vol. 29, no. 4. — Pp. 435-443.

61. Ghodsi M. et al. De novo likelihood-based measures for comparing genome assemblies // BMC research notes. — 2013. — Vol. 6, no. 1. — P. 334.

62. HuntM. et al. REAPR: a universal tool for genome assembly evaluation // Genome Biol. — 2013. — Vol. 14, no. 5. — P. R47.

63. Kurtz Stefan et al. Versatile and open software for comparing large genomes // Genome Biol. — 2004. — Vol. 5, no. 2. — P. R12. — URL: http://genomebiology. com/2004/5/2/R12.

64. Versatile genome assembly evaluation with QUAST-LG / A. Mikheenko, A. Prjibelski, V. Saveliev et al. // Bioinformatics. — 2018. — June.

65. Li H. Minimap2: pairwise alignment for nucleotide sequences // Bioinformatics.

— 2018.—May.

66. Hinnebusch J., Tilly K. Linear plasmids and chromosomes in bacteria // Mol. Microbiol. — 1993. — Dec. — Vol. 10, no. 5. — Pp. 917-922.

67. Besemer J. et al. GeneMarkS: a self-training method for prediction of gene starts in microbial genomes. Implications for finding sequence motifs in regulatory regions // Nucleic Acids Res. — 2001. — Jun.. — Vol. 29, no. 12. — Pp. 2607-2618.

68. Lomsadze A. et al. Gene identification in novel eukaryotic genomes by self-training algorithm // Nucleic Acids Res. — 2005. — Vol. 33, no. 20. — Pp. 64946506.

69. Majoros W. et al. TigrScan and GlimmerHMM: two open source ab initio eukaryotic gene-finders // Bioinformatics. — 2004. —Nov. — Vol. 20, no. 16. — Pp. 2878-2879.

70. Makinen Veli et al. Normalized N50 assembly metric using gap-restricted colinear chaining // BMC Bioinformatics. — 2012. — Vol. 13, no. 1. — P. 255. — URL: http://www.biomedcentral.com/1471-2105/13/255.

71. Narzisi G., Mishra B. Scoring-and-unfolding trimmed tree assembler: concepts, constructs and comparisons // Bioinformatics. — 2011. — Jan. — Vol. 27, no. 2.

— Pp. 153-160.

72. Bohlin Jon et al. Analysis of intra-genomic GC content homogeneity within prokaryotes // BMC Genomics. — 2010. — Vol. 11, no. 1. — P. 464. — URL: http://www.biomedcentral.com/1471-2164/11/464.

73. Krzywinski M. et al. Circos: an information aesthetic for comparative genomics // Genome Res. — 2009. — Sep. — Vol. 19, no. 9. — Pp. 1639-1645.

74. Icarus: visualizer for de novo assembly evaluation / A. Mikheenko, G. Valin, A. Prjibelski et al. // Bioinformatics. — 2016. — Nov. — Vol. 32, no. 21. — Pp. 3321-3323.

75. Chitsaz Hamidreza et al. Efficient de novo assembly of single-cell bacterial genomes from short-read data sets // Nature Biotechnol. — 2011. — Sep.. — Vol. 29, no. 10. — Pp. 915-921. — URL: http://dx.doi.org/10.1038/nbt.1966.

76. Lasken Roger S. Single-cell genomic sequencing using Multiple Displacement Amplification. // Curr Opin Microbiol. — 2007. — Oct.. — Vol. 10, no. 5. — Pp. 510-516. — URL: http://dx.doi.org/10.1016/j.mib.2007.08.005.

77. Boisvert Sebastien, Laviolette Francois, Corbeil Jacques. Ray: Simultaneous Assembly of Reads from a Mix of High-Throughput Sequencing Technologies // Journal ofComputational Biology. — 2010. — Vol. 17, no. 11. — Pp. 1519-1533.

— URL: http://bioinformatics.oxfordjournals.org/content/29/21/2669.abstract.

78. SOAPdenovo2: An empirically improved memory-efficient short-read de novo assembler / R. Luo, B. Liu, Y. Xie et al. // GigaScience. — 2012. — Vol. 1, no. 1.

— P. 18.

79. Complete genome sequence of USA300, an epidemic clone of community-acquired meticillin-resistant Staphylococcus aureus / B. A. Diep, S. R. Gill, R. F. Chang et al. // Lancet. — 2006. — Mar. — Vol. 367, no. 9512. — Pp. 731739.

80. Performance comparison of second- and third-generation sequencers using a bacterial genome with two chromosomes / M. Miyamoto, D. Motooka, K. Gotoh et al. // BMC Genomics. — 2014. — Aug. — Vol. 15. — P. 699.

81. The MaSuRCA genome assembler / Aleksey V. Zimin, Guillaume Marcais, Daniela Puiu et al. // Bioinformatics. — 2013. — Vol. 29, no. 21. — Pp. 2669-2677. — URL: http://bioinformatics.oxfordjournals.org/content/29/21/ 2669.abstract.

82. Li D. et al. MEGAHIT: an ultra-fast single-node solution for large and complex metagenomics assembly via succinct de Bruijn graph // Bioinformatics. — 2015.

— May. — Vol. 31, no. 10. — Pp. 1674-1676.

83. Jackman S. D. et al. ABySS 2.0: resource-efficient assembly of large genomes using a Bloom filter // Genome Res. — 2017. — May. — Vol. 27, no. 5. — Pp. 768-777.

84. Lasken R. S., Egholm M. Whole genome amplification: abundant supplies of DNA from precious samples or clinical specimens // Trends Biotechnol. — 2003. — Dec. — Vol. 21, no. 12. — Pp. 531-535.

85. Are uncultivated bacteria really uncultivable? / I. D. Puspita, Y. Kamagata, M. Tanaka et al. // Microbes Environ. — 2012. — Vol. 27, no. 4. — Pp. 356-366.

86. Rapid amplification of plasmid and phage DNA using Phi 29 DNA polymerase and multiply-primed rolling circle amplification / F. B. Dean, J. R. Nelson, T. L. Giesler, R. S. Lasken // Genome Res. — 2001. — Jun. — Vol. 11, no. 6. — Pp. 1095-1099.

87. Community structure and metabolism through reconstruction of microbial genomes from the environment / G. W. Tyson, J. Chapman, P. Hugenholtz et al. // Nature. — 2004. — Mar. — Vol. 428, no. 6978. — Pp. 37-43.

88. Environmental genome shotgun sequencing of the Sargasso Sea / J. C. Venter, K. Remington, J. F. Heidelberg et al. // Science. — 2004. — Apr. — Vol. 304, no. 5667. — Pp. 66-74.

89. Whole-genome shotgun assembly and analysis of the genome of Fugu rubripes / S. Aparicio, J. Chapman, E. Stupka et al. // Science. — 2002. — Vol. 297, no. 5585.— Pp. 1301-10.

90. Meta-IDBA: a de Novo assembler for metagenomic data / Y. Peng, H. C. Leung, S. M. Yiu, F. Y. Chin // Bioinformatics. — 2011. — Jul. — Vol. 27, no. 13. — Pp. 94-101.

91. Laserson J. et al. Genovo: de novo assembly for metagenomes // Journal of Computational Biology. — 2011. — Vol. 18, no. 3. — Pp. 429-443.

92. Namiki T. et al. MetaVelvet: an extension of Velvet assembler to de novo metagenome assembly from short sequence reads // Nucleic Acids Res. — 2012.

— Vol. 40, no. 20. — P. e155.

93. Boisvert S. et al. Ray Meta: scalable de novo metagenome assembly and profiling // Genome Biol. — 2012. — Vol. 13, no. 12. — P. R122.

94. Haider B. et al. Omega: an overlap-graph de novo assembler for metagenomics // Bioinformatics. — 2014. — Oct. — Vol. 30, no. 19. — Pp. 2717-2722.

95. metaSPAdes: a new versatile metagenomic assembler / S. Nurk, D. Meleshko, A. Korobeynikov, P. A. Pevzner// Genome Res. — 2017. — 05. — Vol. 27, no. 5.

— Pp. 824-834.

96. Parks D. et al. CheckM: assessing the quality of microbial genomes recovered from isolates, single cells, and metagenomes // Genome Res. — 2015. — Jul. — Vol. 25, no. 7. — Pp. 1043-1055.

97. Qin J. et al. A human gut microbial gene catalogue established by metagenomic sequencing // Nature. — 2010. — Vol. 464, no. 7285. — Pp. 59-65.

98. Ondov B. et al. Interactive metagenomic visualization in a Web browser // BMC bioinformatics. — 2011. — Vol. 12, no. 1. — P. 385.

99. Zhu W. et al. Ab initio gene identification in metagenomic sequences // Nucleic Acids Res. — 2010. — Vol. 38, no. 12. — P. e132.

100. Reference sequence (RefSeq) database atNCBI: current status, taxonomic expansion, and functional annotation / N. A. O'Leary, M. W. Wright, J. R. Brister et al. // Nucleic Acids Res. — 2016. — Jan. — Vol. 44, no. D1. — Pp. D733-745.

101. Quast C. et al. The SILVA ribosomal RNA gene database project: improved data processing and web-based tools// Nucleic Acids Res. — 2012. — Vol. 41, no. D1.

— Pp. D590-D596.

102. Camacho C. et al. BLAST+: architecture and applications // BMC bioinformatics.

— 2009. — Vol. 10, no. 1. — P. 421.

103. Palys T., Nakamura L. K., Cohan F. M. Discovery and classification of ecological diversity in the bacterial world: the role of DNA sequence data // Int. J. Syst. Bacteriol. — 1997. — Oct. — Vol. 47, no. 4. — Pp. 1145-1156.

104. Kolbert C. P., PersingD. H. Ribosomal DNA sequencing as a tool for identification of bacterial pathogens // Curr. Opin. Microbiol. — 1999. — Jun. — Vol. 2, no. 3. — Pp. 299-305.

105. Intragenomic heterogeneity of 16S rRNA genes causes overestimation of prokary-otic diversity / D. L. Sun, X. Jiang, Q. L. Wu, N. Y. Zhou // Appl. Environ. Microbiol. — 2013. — Oct. — Vol. 79, no. 19. — Pp. 5962-5969.

106. Williamson S. et al. Metagenomic exploration of viruses throughout the Indian Ocean // PLoS ONE. — 2012. — Vol. 7, no. 10. — P. 18.

107. WoodDerrickE, Salzberg Steven L. Kraken: ultrafast metagenomic sequence classification using exact alignments // Genome Biol. — 2014. — Vol. 15, no. 3. — P. R46.

108. Ounit R. et al. CLARK: fast and accurate classification of metagenomic and genomic sequences using discriminative k-mers // BMC genomics. — 2015. — Vol. 16, no. 1. — P. 236.

109. Altschul S. et al. Basic local alignment search tool // J. Mol. Biol. — 1990. — Oct. — Vol. 215, no. 3. — Pp. 403-410.

110. Li H. Aligning sequence reads, clone sequences and assembly contigs with BWA-MEM // arXiv:1708.01492. — 2013.

111. GRIDSS: sensitive and specific genomic rearrangement detection using positional de Bruijn graph assembly / D. L. Cameron, J. Schroder, J. S. Penington et al. // Genome Res. — 2017. — Dec. — Vol. 27, no. 12. — Pp. 2050-2060.

112. Chen X. et al. Manta: Rapid detection of structural variants and indels for clinical sequencing applications // bioRxiv. — 2015.

113. Layer R. et al. LUMPY: a probabilistic framework for structural variant discovery // Genome Biol. — 2014. — Vol. 15, no. 6. — P. R84.

114. Ye K. et al. Pindel: a pattern growth approach to detect break points of large deletions and medium sized insertions from paired-end short reads // Bioinformatics. — 2009. — Nov. — Vol. 25, no. 21. — Pp. 2865-2871.

115. Blattner F. R. et al. The complete genome sequence of Escherichia coli K-12. // Science. — 1997. — Sep.. — Vol. 277, no. 5331. — Pp. 1453-1462. — URL: http://dx.doi.org/10.1126/science.277.5331.1453.

116. The complete genome sequence of Escherichia coli DH10B: insights into the biology of a laboratory workhorse / T. Durfee, R. Nelson, S. Baldwin et al. // J. Bacteriol. — 2008. — Apr. — Vol. 190, no. 7. — Pp. 2597-2606.

117. Consortium The Human Microbiome Project. Structure, function and diversity of the healthy human microbiome // Nature. — 2012. — Vol. 486, no. 7402. — Pp. 207-214.

118. MegaGTA: a sensitive and accurate metagenomic gene-targeted assembler using iterative de Bruijn graphs / D. Li, Y. Huang, C. M. Leung et al. // BMC Bioinfor-matics. — 2017. — Oct. — Vol. 18, no. Suppl 12. — P. 408.

119. IMP: a pipeline for reproducible reference-independent integrated metagenomic and metatranscriptomic analyses / S. Narayanasamy, Y. Jarosz, E. E. Muller et al. // Genome Biol. — 2016. — 12. — Vol. 17, no. 1. — P. 260.

120. Use of simulated data sets to evaluate the fidelity of metagenomic processing methods / K. Mavromatis, N. Ivanova, K. Barry et al. // Nat. Methods. — 2007. — Jun. — Vol. 4, no. 6. — Pp. 495-500.

121. Lindgreen S., Adair K. L., Gardner P. P. An evaluation of the accuracy and speed of metagenome analysis tools // Sci Rep. — 2016. — Jan. — Vol. 6. — P. 19233.

122. LingL et al. A new antibiotic kills pathogens without detectable resistance // Nature. — 2015. — Jan. — Vol. 517, no. 7535. — Pp. 455-459.

123. Newman D. J., Cragg G. M. Natural products as sources of new drugs over the 30 years from 1981 to 2010 // J.Nat. Prod. — 2012. — Mar. — Vol. 75, no. 3. — Pp. 311-335.

124. Marahiel M. A., Stachelhaus T., Mootz H. D. Modular Peptide Synthetases Involved in Nonribosomal Peptide Synthesis // Chem. Rev. — 1997. — Nov. — Vol. 97, no. 7. — Pp. 2651-2674.

125. Arnison P. G. et al. Ribosomally synthesized and post-translationally modified peptide natural products: overview and recommendations for a universal nomenclature // Nat Prod Rep. — 2013. — Jan. — Vol. 30, no. 1. — Pp. 108-160.

126. Peptide bond formation in nonribosomal peptide biosynthesis. Catalytic role of the condensation domain / T. Stachelhaus, H. D. Mootz, V. Bergendahl, M. A. Marahiel // J. Biol. Chem. — 1998. — Aug. — Vol. 273, no. 35. — Pp. 22773-22781.

127. von Dohren H., Dieckmann R., Pavela-Vrancic M. The nonribosomal code // Chem. Biol. — 1999. — Oct. — Vol. 6, no. 10. — Pp. R273-279.

128. Molecular networking as a dereplication strategy / J. Y. Yang, L. M. Sanchez, C. M. Rath et al. // J. Nat. Prod. — 2013. — Sep. — Vol. 76, no. 9. — Pp. 16861699.

129. Gerwick W. H., Moore B. S. Lessons from the past and charting the future of marine natural products drug discovery and chemical biology // Chem. Biol. — 2012. — Jan. — Vol. 19, no. 1. — Pp. 85-98.

130. Microbial strain prioritization using metabolomics tools for the discovery of natural products / Y. Hou, D. R. Braun, C. R. Michel et al. // Anal. Chem. — 2012.

— May. — Vol. 84, no. 10. — Pp. 4277-4283.

131. Dereplication of microbial natural products by LC-DAD-TOFMS / K. F. Nielsen, M. Mansson, C. Rank et al. // J. Nat. Prod. — 2011. — Nov. — Vol. 74, no. 11.

— Pp. 2338-2348.

132. Blunt J., Munro M., Laatsch H. Dereplication of peptidic natural products through database search of mass spectra // University of Canterbury; Christchurch, New Zealand: University of Gottingen; Gottingen, Germany. — 2007.

133. Gozalbes R., Pineda-Lucena A. Small molecule databases and chemical descriptors useful in chemoinformatics: an overview // Comb. Chem. High Throughput Screen. — 2011. — Jul. — Vol. 14, no. 6. — Pp. 548-458.

134. EngJ.K., McCormack A. L., Yates J. R. An approach to correlate tandem mass spectral data of peptides with amino acid sequences in a protein database // J. Am. Soc. Mass Spectrom. — 1994. — Nov. — Vol. 5, no. 11. — Pp. 976-989.

135. Probability-based protein identification by searching sequence databases using mass spectrometry data / D. N. Perkins, D. J. Pappin, D. M. Creasy, J. S. Cottrell // Electrophoresis. — 1999. — Dec. — Vol. 20, no. 18. — Pp. 3551-3567.

136. Dereplication and de novo sequencing of nonribosomal peptides / J. Ng, N. Ban-deira, W. T. Liu et al. // Nat. Methods. — 2009. — Aug. — Vol. 6, no. 8. — Pp. 596-599.

137. Dereplicating nonribosomal peptides using an informatic search algorithm for natural products (iSNAP) discovery / A. Ibrahim, L. Yang, C. Johnston et al. // Proc. Natl. Acad. Sci. U.S.A. — 2012. —Nov. — Vol. 109, no. 47. — Pp. 19196-19201.

138. Elias J. E., Gygi S. P. Target-decoy search strategy for increased confidence in large-scale protein identifications by mass spectrometry // Nat. Methods. — 2007. — Mar. — Vol. 4, no. 3. — Pp. 207-214.

139. HufskyF., ScheubertK., Bocker S. New kids on the block: novel informatics methods for natural product discovery // Nat Prod Rep. — 2014. — Jun. — Vol. 31, no. 6. — Pp. 807-817.

140. Stein S. Mass spectral reference libraries: an ever-expanding resource for chemical identification//Anal. Chem. — 2012. — Sep. — Vol. 84, no. 17. — Pp. 72747282.

141. Target-decoy approach and false discovery rate: when things may go wrong / N. Gupta, N. Bandeira, U. Keich, P. A. Pevzner // J Am Soc Mass Spectr. — 2011. — Vol. 22, no. 7. — Pp. 1111-20.

142. Mohimani H., Kim S., Pevzner P. A. A new approach to evaluating statistical significance of spectral identifications // J. Proteome Res. — 2013. — Apr. — Vol. 12, no. 4. — Pp. 1560-1568.

143. Abramova Anastasiia, Korobeynikov Anton. Assessing the Significance of Peptide Spectrum Match Scores //17th International Workshop on Algorithms in Bioinfor-matics (WABI2017) / Ed. by Russell Schwartz, Knut Reinert. — Vol. 88 of Leibniz International Proceedings in Informatics (LIPIcs). — Dagstuhl, Germany: Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017. — Pp. 14:1-14:11. — URL: http://drops.dagstuhl.de/opus/volltexte/2017/7641.

144. Massetolides A-H, antimycobacterial cyclic depsipeptides produced by two pseu-domonads isolated from marine habitats / J. Gerard, R. Lloyd, T. Barsby et al. // J. Nat. Prod. — 1997. — Mar. — Vol. 60, no. 3. — Pp. 223-229.

145. Arima K et al. Surfactin, a crystalline peptide lipid surfactant produced by Bacillus subtilis: Isolation, characterization and its inhibition of fibrin clot formation //

Biochem. Biophys. Res. Commun. — 1968. — Vol. 31. — Pp. 488—494.

146. Efficiency of database search for identification of mutated and modified proteins via mass spectrometry / P. A. Pevzner, Z. Mulyukov, V. Dancik, C. L. Tang // Genome Res. — 2001. — Feb. — Vol. 11, no. 2. — Pp. 290-299.

147. Identification of post-translational modifications via blind search of mass-spectra / D. Tsur, S. Tanner, E. Zandi et al. // Proc IEEE Comput Syst Bioinform Conf. — 2005. — Pp. 157-166.

148. InsPecT: identification of posttranslationally modified peptides from tandem mass spectra / S. Tanner, H. Shu, A. Frank et al. // Anal. Chem. — 2005. — Jul. — Vol. 77, no. 14. — Pp. 4626-4639.

149. Discovery and development of first in class antifungal caspofungin (CANCIDAS®)-a case study / J. M. Balkovec, D. L. Hughes, P. S. Masurekar et al. // Nat Prod Rep. — 2014. — Jan. — Vol. 31, no. 1. — Pp. 15-34.

150. Okano A., Isley N. A., Boger D. L. Peripheral modifications of vancomycin with added synergistic mechanisms of action provide durable and potent antibiotics //

Proc. Natl. Acad. Sci. U.S.A. — 2017. — May.

151. Multiplex de novo sequencing of peptide antibiotics / H. Mohimani, W. T. Liu, Y. L. Yang et al. // J. Comput. Biol. — 2011. — Nov. — Vol. 18, no. 11. — Pp. 1371-1381.

152. NingK., Fermin D., Nesvizhskii A. I. Computational analysis of unassigned high-quality MS/MS spectra in proteomic data sets // Proteomics. — 2010. — Jul. — Vol. 10, no. 14. — Pp. 2712-2718.

153. Exploration of Nonribosomal Peptide Families with an Automated Informatic Search Algorithm / L. Yang, A. Ibrahim, C. W. Johnston et al. // Chem. Biol.

— 2015. — Sep. — Vol. 22, no. 9. — Pp. 1259-1269.

154. Bandeira N. Spectral networks: a new approach to de novo discovery of protein sequences and posttranslational modifications // BioTechniques. — 2007. — Jun.

— Vol. 42, no. 6. — Pp. 687, 689, 691 passim.

155. Method to correlate tandem mass spectra of modified peptides to amino acid sequences in the protein database / J. R. Yates, J. K. Eng, A. L. McCormack, D. Schieltz // Anal. Chem. — 1995. — Apr. — Vol. 67, no. 8. — Pp. 1426-1436.

156. Pevzner P. A., Dancik V., Tang C. L. Mutation-tolerant protein identification by mass spectrometry // J. Comput. Biol. — 2000. — Vol. 7, no. 6. — Pp. 777-787.

157. Na S., Bandeira N., PaekE. Fast multi-blind modification search through tandem mass spectrometry // Mol. Cell Proteomics. — 2012. — Apr. — Vol. 11, no. 4.

— P. M111.010199.

158. Indexing the Pseudomonas specialized metabolome enabled the discovery of poaeamide B and the bananamides / D. D. Nguyen, A. V. Melnik, N. Koyama et al. // Nat Microbiol. — 2016. — Oct. — Vol. 2. — P. 16197.

159. Automated genome mining of ribosomal peptide natural products / H. Mohimani, R. D. Kersten, W. T. Liu et al. // ACS Chem. Biol. — 2014. — Jul. — Vol. 9, no. 7.— Pp. 1545-1551.

160. Molecular networking and pattern-based genome mining improves discovery of biosynthetic gene clusters and their products from Salinispora species / K. R. Duncan, M. Crusemann, A. Lechner et al. // Chem. Biol. — 2015. — Apr. — Vol. 22, no. 4. — Pp. 460-471.

161. Digitizing mass spectrometry data to explore the chemical diversity and distribution of marine cyanobacteria and algae / T. Luzzatto-Knaan, N. Garg, M. Wang et al. // Elife. — 2017. — May. — Vol. 6.

162. Medema M. H. et al. Minimum Information about a Biosynthetic Gene cluster // Nat. Chem. Biol. — 2015. — Sep. — Vol. 11, no. 9. — Pp. 625-631.

163. StreptomeDB: a resource for natural compounds isolated from Streptomyces species / X. Lucas, C. Senger, A. Erxleben et al. // Nucleic Acids Res. — 2013.

— Jan. — Vol. 41, no. Database issue. — Pp. D1130-1136.

164. ClassyFire: automated chemical classification with a comprehensive, computable taxonomy / Y. Djoumbou Feunang, R. Eisner, C. Knox et al. // J Cheminform. — 2016.— Vol. 8. —P. 61.

165. Challis G. L., Naismith J. H. Structural aspects of non-ribosomal peptide biosynthesis // Curr. Opin. Struct. Biol. — 2004. — Dec. — Vol. 14, no. 6. — Pp. 748756.

166. Surugamides A-E, cyclic octapeptides with four D-amino acid residues, from a marine Streptomyces sp.: LC-MS-aided inspection of partial hydrolysates for the

distinction of D- and L-amino acid residues in the sequence / K. Takada, A. Ni-nomiya, M. Naruse et al. // J. Org. Chem. — 2013. — Jul. — Vol. 78, no. 13. — Pp. 6746-6750.

167. Isolation and structural determination of a new hydrophobic peptide venepep-tide from Streptomyces venezuelae / S. Kodani, K. Sato, H. Hemmi, M. Ohnish-Kameyama// J. Antibiot. — 2014. — Dec. — Vol. 67, no. 12. — Pp. 839-842.

168. Two novel cyclic peptides with antifungal activity from the cyanobacterium Toly-pothrix byssoidea (EAWAG 195) / B. Jaki, O. Zerbe, J. Heilmann, O. Sticher // J. Nat. Prod. — 2001. — Feb. — Vol. 64, no. 2. — Pp. 154-158.

169. NRPSpredictor2-a web server for predicting NRPS adenylation domain specificity / M. Rottig, M. H. Medema, K. Blin et al. // Nucleic Acids Res. — 2011. — Jul. — Vol. 39, no. Web Server issue. — Pp. W362-367.

Список рисунков

1.1 Различные графы геномной сборки..........................................15

1.2 Вычислительный конвейер QUAST.....................21

1.3 Классификация мисассемблов........................23

1.4 Пример вычисления NA50..........................28

1.5 Веб-интерфейс QUAST...........................31

1.6 Статистика использования веб-QUAST...................33

1.7 Выравнивание сборок данных одноклеточного секвенирования

S. aureus на референсный геном.......................35

1.8 Количество скачиваний и цитирований QUAST..............37

2.1 Вычислительный конвейер MetaQUAST..................42

2.2 Процесс определения видового состава в MetaQUAST..........44

2.3 Процесс уточнения мисассемблов.....................47

2.4 Пример мисассембла, вызванного СВ...................48

2.5 Фрагмент сводного HTML отчета MetaQUAST..............50

3.1 Вычислительный конвейер Dereplicator..................61

3.2 Различные способы создания ложных пептидов..............62

3.3 Количество PSM и уникальных PNP, найденных Dereplicator в SpectraQNPs.................................67

3.4 Количество PNP, найденных Dereplicator в SpectraHigh..........68

4.1 Сетевые и несетевые стратегии вариативной идентификация PNP. . . . 72

4.2 Вычислительный конвейер VarQuest....................75

4.3 Соответствие между теоретическими спектрами PNP и его варианта. . 77

4.4 Предобработка базы соединений Peptides.................79

4.5 Нахождение соответствий экспериментальному пику s....................80

4.6 Визуализации VarQuest для новых вариантов PNP.........................88

4.7 Графы штаммов для наборов SpectracYANO и SpectraSTREPl......92

Список таблиц

1 Сравнение сборок данных одноклеточного секвенирования S. aureus. . 34

2 Производительность QUAST........................36

3 Результаты уточнения мисассемблов в эксперименте E. coli MG1655/DH10B...............................53

4 Производительность MetaQUAST......................54

5 Спектральные наборы данных, использованные для тестирования VarQuest........................................................................81

6 Детали создания базы PNPdatabase........................................82

7 Производительность четырех методов идентификации PNP. ............83

8 Сравнение четырех подходов к идентификации PNP на различных спектральных наборах данных. ............................................84

SAINT PETERSBURG STATE UNIVERSITY

Printed as a manuscript

Gurevich Alexey Alexandrovich

COMPUTATIONAL METHODS FOR ANALYSIS OF ERROR-PRONE METABOLOGENOMIC DATA

Specialty 03.01.09 — «Mathematical biology, bioinformatics»

Dissertation is submitted for the degree of Candidate of Physico-mathematical

Sciences

Scientific advisor:

Candidate of Physico-mathematical Sciences, Professor

Pevzner Pavel Arkadyevich

Saint Petersburg — 2018

Table of contents

P.

Introduction....................................123

Chapter 1. Quality assessment of genome assemblies.............130

1.1 Genome sequencing............................130

1.2 Genome assembly problem........................131

1.2.1 Overlap-Layout-Consensus strategy...............131

1.2.2 De Bruijn graph strategy.....................133

1.2.3 String graph strategy.......................133

1.3 Current ways to benchmark genome assemblies.............133

1.4 QUAST..................................135

1.4.1 Pipeline overview.........................135

1.4.2 Quality metrics..........................136

1.4.3 Output visualization.......................143

1.4.4 Web interface...........................144

1.5 Results...................................147

1.5.1 Comparison of single-cell S. aureus assemblies.........147

1.5.2 QUAST performance.......................148

1.5.3 Spread of QUAST in the research community..........150

Chapter 2. Metagenome assembly evaluation.................152

2.1 Metagenomic studies...........................152

2.1.1 Sequencing of uncultivated bacteria...............152

2.1.2 Metagenomic data specifics...................152

2.1.3 Metagenome assembly algorithms................153

2.2 MetaQUAST...............................153

2.2.1 Pipeline overview.........................154

2.2.2 Additional quality metrics....................155

2.2.3 Automated species content detection...............155

2.2.4 Structural variations detection and misassemblies refinement . . 158

2.2.5 Visualization...........................161

P.

2.3 Results...................................162

2.3.1 Species content detection sensitivity...............162

2.3.2 Misassemblies refinement efficiency...............164

2.3.3 MetaQUAST performance....................165

2.3.4 Critical assessment of metagenomics software..........166

Chapter 3. Dereplication of peptidic natural products through database

search of mass spectra........................168

3.1 PNP specifics...............................168

3.1.1 PNPs and medicine........................168

3.1.2 PNP synthesis ..........................168

3.1.3 Emerging high-throughput approaches to PNP discovery . . . .169

3.2 PNP dereplication.............................169

3.2.1 Existing PNP dereplication strategies..............170

3.3 Dereplicator algorithm..........................170

3.3.1 Pipeline overview ......................... 171

3.3.2 Generating decoy database....................171

3.3.3 Constructing theoretical spectra of PNPs ............174

3.3.4 Scoring PSMs ..........................174

3.3.5 Computing P-values of PSMs..................175

3.3.6 Computing FDR.........................175

3.4 Benchmarking Dereplicator........................176

3.4.1 Test data.............................176

3.4.2 Dereplication of SpectraoNPS..................177

3.4.3 Dereplication of Spectra High ..................177

Chapter 4. Variable identification of peptidic natural products .......179

4.1 PNP variants ...............................179

4.1.1 Variable identification problem..................179

4.1.2 PNP families...........................179

4.2 Current variable PNP identification strategies..............180

4.2.1 Spectral network approach ........................................181

4.2.2 Brute-force approach.......................182

4.3 VarQuest algorithm............................182

P.

4.3.1 Pipeline overview.........................183

4.3.2 Scoring of PNP spectrum matches................185

4.3.3 Candidate PNPs selection....................185

4.3.4 PNP database preprocessing...................187

4.3.5 Scoring of a spectrum against a PNP database..........187

4.4 Benchmarking VarQuest.........................189

4.4.1 Testdatasets ...........................189

4.4.2 Results..............................190

4.4.3 Validation of VarQuest identifications..............191

4.5 Microbiological aspects of VarQuest results...............193

4.5.1 Modifications and mutations identified by VarQuest......193

4.5.2 PNP variants identified by VarQuest...............194

4.5.3 PNP diversity revealed by VarQuest...............197

Conclusion.....................................200

List of abbverations and acronyms........................202

Glossary ......................................203

References.....................................206

Table of figures...................................223

Table of tables...................................224

Introduction

Motivation. Bioinformatics operates with various types of biological data: DNA, RNA, proteins, and metabolites. These substances are studied by the corresponding research fields of molecular biology — genomics, transcriptomics, proteomics, and metabolomics, respectively. Emerging subdisciplines of bioinformatics tend to combine different kinds of data for enhancing the capacity to analyze biological processes. A successful example of such combination is proteogenomics [1-3] which uses pro-teomic information to improve gene annotations. This work is focused on another actively developing research field, metabologenomics, a discipline at the intersection of genomics and metabolomics [4; 5].

Metabologenomics is extremely important for modern medicine since it helps to identify biologically active organic compounds that could be used as a natural source for novel antibiotics and other drugs [6-8]. The key conditions for the emergence of metabologenomics are both the appearance of new sequencing technologies in ge-nomics and the move towards high-throughput mass spectrometry-based analysis in metabolomics. However, computational methods are needed to process vast amounts of error-prone genomic and metabolomic data and to realize the promise of technological breakthroughs in sequencing and mass spectrometry.

A common metabologenomic pipeline takes on input biological data obtained from organism's genome (sequencing data) and metabolome (mass spectrometry data) and computationally analyses them. The genome processing part usually starts with sequencing data correction and quality control. It continues with genome assembly step, evaluation of the constructed assemblies, identification of feasible metabolite encoding fragments. The final step is the creation of a database of putative metabolites present in the sample. The metabolome analysis stage generally includes database search of mass spectra against already known metabolites (so-called dereplication) and further matching of the remaining mass spectra against the metabolites predicted from the genome analysis part.

Almost each of the described pipeline steps constitutes a challenging computational problem due to the huge amounts of data which typically also contain hardware and software errors. Some of these problems already have mature solutions, such as the genome assembly problem with dozens of software tools currently available [9-22]. At the same time, some others remain open computational problems. In this work, two of

these problems are addressed, one is related to the genomic part and the other is for the metabolomic part of the pipeline. In both cases, the problem formulations are similar: to compare experimental data with a reference sample. In addition, in these comparisons it is necessary to take into account that the reference may differ from the researched sample due to mutations or modifications. For both considered problems, algorithmic solutions are developed and implemented in novel software tools.

The first problem addressed in this work is the quality assessment of genome assemblies. Current DNA sequencing technologies cannot read the complete sequence of a genome. In contrast, they produce large amounts of short sequences which are combined together by genome assembly software to form longer regions. Errors in reads and large genomic repeats turn the assembly process into a difficult computational problem. Different algorithms use various heuristics to tackle these challenges which result in many differences in the assemblies they produce. Thus, the question of how to assess the quality of an assembly and how to compare different assemblies arises. This task is especially important since the downstream analysis is highly sensitive to genome assembly quality [23].

The state-of-the-art approach to genome assembly evaluation suggests to sequence a model organism, perform assembly using different algorithms and compare their output against the known reference genome of the researched sample. However, the creation of a high-quality reference sequence is usually a very time-consuming and expensive task, so a reference genome used for the quality assessment may be close but not exactly the same to the sequenced organism. This fact leads to a challenge of distinguishing between natural variations in the sequenced sample and true assembly errors. Moreover, in some cases, such as metagenomic studies (examination of complex communities and environmental samples), the researched organisms are completely unknown and corresponding reference genomes should be computationally identified. In this work, QUAST family of tools is described. This toolkit is dedicated to solve problems of genome assembly evaluation. The software package includes QUAST [24] utility intended for single genome experiments and its extension, MetaQUAST [25], designed for metagenomic study specifics.

The second considered problem is the dereplication of known metabolites and their new variants via database search of mass spectra. This work is focused on the identification of peptidic natural products (PNPs) which represent an important and widely used class of metabolites (commonly referred simply as natural products). Complex chemical structure (for example, cyclic or branch-cyclic) and presence of non-standard

amino acids greatly complicate the identification of PNPs and prevent the use of traditional proteomic methods for this problem [26]. Another major challenge in PNPs dereplication is a natural variability of these compounds. Most PNPs form families of related peptides, where compounds have similar or identical structures and amino acid sequences are different in few positions. In many cases, a PNP is absent in the database, but a more abundant representative of its PNP family is present there. Identification of an unknown PNP from its known variants is called variable (or modification-tolerant) identification (dereplication) and it is crucial for PNP discovery.

Recently launched Global Natural Products Social (GNPS) molecular networking infrastructure [27] brought together over a hundred laboratories that have already generated over a billion of mass spectra of natural products. However, their interpretation remains a bottleneck since computational methods for PNP identification are still in infancy. In this work, a method for high-throughput PNP identification was developed and implemented it in a novel software tool named Dereplicator [28]. Existing strategies for extending the method to variable identification are described here. Since all of them have serious limitations and cannot be applied in high-throughput pipelines, Var-Quest [29], a novel approach to this problem, was developed. VarQuest benchmarking demonstrates that it enables modification-tolerant search of the entire GNPS and leads to discoveries which are important from a microbiological point of view.

Aim and objectives. The aim of this work was to design novel methods for solving two important metabologenomic problems and implement them in software tools. The first problem is the quality assessment of genome assemblies. The second one is the identification of PNPs via database search of mass spectra. The following objectives were accomplished in order to achieve the aim. For the assembly evaluation problem:

1. study of common assembly quality metrics, selection of the best ones and designing novel ones if needed;

2. implementation of the selected metrics computation;

3. development of an algorithm for distinguishing true assembly errors from natural variabilities in the sequenced organism;

4. study and handling of metagenome assembly specifics with respect to their evaluation.

For the PNP identification problem:

1. development of a method for standard PNP identification which is compatible with high-throughput data analysis;

2. study of existing variable PNP identification strategies and their limitations;

3. designing and implementation of a novel algorithm for variable PNP identification solving the limitations of the existing methods;

4. implementation of web interfaces for the developed tools;

5. benchmarking of the developed tools on large-scale datasets.

Methods. The following theories and techniques were used in this work:

- string processing algorithms (especially sequence alignment algorithms);

- graph theory;

- statistical modeling;

- modular and object-oriented programming in C++ and Python.

Practical value and novelty. This work has resulted in the following novel bioin-formatics software:

- QUAST package (including QUAST and MetaQUAST): a set of tools for quality assessment of genome and metagenome assemblies (http: //cab.spbu.ru/software/quast/ and http://cab.spbu.ru/ software/metaquast/, registered with Rospatent, registration numbers are 2016661824 and 2016661838, respectively);

- Dereplicator and VarQuest: software for standard and variable PNP identification via database search of mass spectra (http://cab.spbu. ru/software/dereplicator/ and http://cab.spbu.ru/ software/varquest/, respectively).

QUAST package has become a widely accepted tool in the genome assembly field. It has more than 35,000 downloads1 and more than 500 citations via the Web of Science Core Collection2 since the start of the project in Summer 2012 and the first publication in 2013. To the best of our knowledge, Dereplicator and VarQuest are the first high-throughput methods for standard and variable PNP identification, respectively. Both of them were benchmarked on more than one hundred million of publicly available tandem mass spectra in GNPS. The tools identified an order of magnitude more PNPs (and their new variants) than any previous dereplication efforts [28; 29]. VarQuest is the only modification-tolerant approach capable of searching the entire GNPS at the moment [29].

1the total download number of all package versions based on https://sourceforge.net/p/quast (accessed on March 31, 2018)

2the total citation number of both [24] and [25] based on https://www.webofknowledge.com (accessed on March 31, 2018)

Work presentation. Results of this work were presented on seminars of the Center for Algorithmic Biotechnology (St. Petersburg State University) and the following conferences and meetings:

1. Increased diversity of peptidic natural products revealed by modification-tolerant database search of mass spectra. Talk at RECOMB 2018 (the highlight of the VarQuest paper). Paris, France. April 2018.

2. Genome assembly evaluation with QUAST. Talk at BiATA 2017. St. Petersburg, Russia. August 2017.

3. VarQuest: modification-tolerant identification of novel variants of peptidic antibiotics and other natural products. Poster at ISMB/ECCB 2017. Prague, Czechia. July 2017.

4. Identification of novel peptidic antibiotics via large scale scoring of mass spectra against natural products databases (about both Dereplicator and VarQuest). Poster at RECOMB 2017. Hong Kong, China. May, 2017; Poster at ISMB/ECCB 2017. Prague, Czechia. July 2017.

5. MetaQUAST: evaluating metagenome assemblies. Invited talk at CAMI evaluation meeting. Berlin, Germany. May 2015.

6. QUAST: quality assessment tool for genome assemblies. Poster at RECOMB 2013. Beijing, China. April 2013.

VarQuest poster was also accepted to ASMS 2018 and will be present in San Diego, USA in June 2018.

Main results of the dissertation:

1. The programs for quality assessment of genome (QUAST) and metagenome (MetaQUAST) assemblies are developed and implemented. The programs evaluate correctness, completeness, contiguity and other quality metrics of assemblies based on their alignments against corresponding reference genomes. The programs implement algorithms for allowing work with inaccurate references (distinguishing between true assembly errors and natural variations in the genome of the sequenced organism) or work with samples with unknown content (automatic identification of the putative reference genomes and their retrieval from the NCBI database).

2. The programs for standard (Dereplicator) and variable (VarQuest) PNP identification via database search of mass spectra. The programs compute the statistical significance of the reported PNPs which allows to significantly reduce the number of false positive identifications. VarQuest performs a search that

is tolerant of any modifications in PNPs. Moreover, VarQuest is able to identify variant PNPs even if their known forms are not present in the input mass spectrometry data.

3. The programs for identification of PNPs were benchmarked on more than one hundred million mass spectra from the GNPS platform. The benchmarking demonstrated the applicability of the developed approaches to processing metabolomic data in high-throughput pipelines. The analysis of the benchmarking results revealed a great diversity of PNPs at the chemical level which correlates with the recently discovered PNP diversity at the genomic level (diversity of PNP encoding biosynthetic gene clusters) [30; 31].

Publications. Main results of this work are described in four papers [24; 25; 28; 29] (all in co-authorship) published in journals indexed in the Web of Science Core Collection and Scopus databases (including two papers in Nature Publishing Group journals). The practical application of the developed software are also demonstrated in seven papers [16; 18; 32-36] co-authored by the dissertation's author. These papers are published in journals indexed in the Web of Science Core Collection and Scopus databases (including one paper in a Nature Publishing Group journal).

Personal contribution. The dissertation author was the primary author responsible for the research, design, software implementation and text writing in the QUAST [24] and VarQuest [29] papers. In the MetaQUAST [25] project, the author played the main role in text writing, designing and testing of the corresponding tool and also participated in the implementation of the algorithms. In the Dereplicator [28] paper, the author implemented web-version of the tool at the GNPS platform and also participated in the core tool implementation and benchmarking.

Structure of the work. The dissertation includes introduction, four chapters, and conclusion. The text of the dissertation is comprised of 106 pages, including 24 figures and 8 tables. References include 169 citations.

In the first chapter, the genome assembly problem and motivation to create an assembly evaluation toolkit are described. Aspects of reference-based evaluation are discussed. The pipeline of the developed quality assessment tool, QUAST, and its core algorithms are shown in details. This chapter is in part adapted from [24].

The second chapter is about QUAST adaptation for metagenome assemblies analysis. The problems and specifics of metagenomic studies are shown. MetaQUAST, the developed extension of QUAST for tackling these specifics, is introduced. This chapter is in part adapted from [25].

The third chapter is dedicated to PNP identification via database search of mass spectra. Importance and difficulties of PNP discovery are described. Representation of chemical structures via the PNP graph model and generation of theoretical spectra based on this model are shown. The scoring function, statistical estimation procedure, and the whole Dereplicator pipeline are given. Results of the entire GNPS processing with Dereplicator are demonstrated. This chapter is in part adapted from [28].

In the fourth chapter, aspects of variable PNP identification are discussed. The existing methods and their drawbacks are described. The VarQuest algorithm for variable PNP identification is proposed. A comprehensive benchmarking of VarQuest against competing approaches and standard PNP identification via Dereplicator is made. Validation of VarQuest identifications is demonstrated. The results of the modification-tolerant search of the entire GNPS are discussed from a microbiological point of view. This chapter is in part adapted from [29].

Chapter 1. Quality assessment of genome assemblies 1.1 Genome sequencing

Whole genome sequencing is the process of determining the precise order of nucleotides within an organism's genome. Knowledge of entire DNA sequences has a wide range of application from evolutionary and molecular biology to personalized medicine and forensics. Bacteriophage QX174 was the first completely sequenced genome. This work was done by Frederick Sanger and colleagues in 1977 [37]. The Sanger method was further used to sequence many short genomes, such as viruses, mitochondria and chloroplasts in 1970-1980 [38-41]. However, this approach was very expensive and time consuming because it required a lot of manual work.

The shift to automated sequencing methods in the 1990s allowed the sequence of much larger genomes to be determined. Haemophilus influenzae was the first free-living organism to have its entire genome known. This bacteria was sequenced in 1995 using the shotgun sequencing method [42]. The first eukaryotic genome, Sac-charomyces cerevisiae (a yeast), and the first animal genome, Caenorhabditis elegans (a worm) were also sequenced in the 1990s [43;44]. The first draft of the human genome sequence was published in 2001 [45; 46]. The Human Genome Project published the entire human genome in 2003 and presented the quality assessment of this sequence in 2004 [47]. However, it is still under refinement and analysis process, for example, the most up-to-date version of the human genome was released in the end of 2017 (GRCh38.p12).

Sanger sequencing was mainly replaced by so-called High-Throughput or Next-Generation Sequencing (NGS) technologies in the early 2000s. NGS technologies significantly reduced the cost and shorten the time of sequencing. The most remarkable NGS methods include Illumina/Solexa [48] (sequencing by synthesis), Ion Torrent [49] (Ion semiconductor sequencing), and others. Currently, thousands of genomes have been sequenced using NGS. However, the market of genome sequencing is in constant development and the recent leadership of NGS technologies is now in question due to rapidly improving Long-Read Sequencing (LRS) technologies. LRS technologies are currently represented by single molecule real time sequencing by Pacific Biosciences [50] and nanopore sequencing by Oxford Nanopore Technologies [51]. These

providers can read DNA fragments a few orders of magnitude longer than the ones captured by NGS. At the same time, LRS remains a rather expensive technology and it produces data with significantly higher error rates than its NGS competitors.

1.2 Genome assembly problem

Despite the breakthroughs in sequencing methods, there is still no technology able to read the entire chromosomes in a single run. In contrast, current approaches read numerous relatively short DNA fragments, called reads (typically 100-500 base pairs (bp) for NGS and up to dozens of thousands bp for LRS). Computer programs use the overlapping ends of different reads to reconstruct their order and assemble them into larger segments, called contigs (short for contiguous). This task is a challenging computational problem because of a huge number of reads, their error-prone nature, and such genomic features as the four-letter alphabet and the presence of many repeated sequences.

There are several conventional approaches to solving the genome assembly problem (Figure 1.1). All of them use graph theory but each one defines vertices and edges differently. A genome sequence is encoded in these graphs and corresponds to some graph traversal. An assembly usually represents a set of non-branching paths in the graph since a single unambiguous traversal is not possible due to complex graph topology, for instance, the presence of many branches and cycles. The three major classes of genome assembly algorithms are briefly described below altogether with examples of their software implementations.

1.2.1 Overlap-Layout-Consensus strategy

The Overlap-Layout-Consensus (OLC) approach constructs the overlap graph where vertices represent reads and two vertices are connected if their corresponding reads overlap (Figure 1.1B). The graph construction requires the finding of overlaps between all pairs of reads which is a very time-consuming task even using additional heuristics [9]. The OLC-based genome assemblers, such as Celera Assembler [9],

A) Genome sequence and corresponding sequencing reads. The genome consists of three unique fragments separated by a repeated sequence. B) the overlap graph; C) the de Bruijn graph; D) the string graph. This figure is partially adapted from [10].

Figure 1.1 — Various genome assembly graphs.

ARACHNE [52] and PHRAP [53], were successfully applied for processing Sanger reads. However, the OLC approach is hardly compatible with NGS data since the number of reads is huge and they are relatively short. Nevertheless, the OLC idea is still in use. There are several recently developed OLC-based genome assemblers, such as Canu [22] and FALCON [19], which are intended for assembling LRS data.

1.2.2 De Bruijn graph strategy

This method first chops reads into much shorter k-mers (strings of length k) and then uses all the k-mers to form the de Bruijn graph (DBG). DBG vertices are k-mers and two vertices are connected if they are a prefix and a suffix of the k + 1-mer presented in the input reads (Figure 1.1C). The graph could further be simplified into condensed DBG by replacing non-branching paths by single edges. The first DBG-based assembler EULER was published in 2001 by Pavel Pevzner and colleagues [10]. The emergence of NGS technologies demonstrated the promises of the DBG approach. Many short-read genome assemblers have since been developed based on DBG, such as Velvet [11], ABySS [12], AllPath-LG [15], SOAPdenovo [13], SPAdes [16], IDBA-UD [17] and others. Moreover, DBG was also adopted for processing LRS data, both in hybrid NGS-LRS [20] andLRS-only [21] assemblers.

1.2.3 String graph strategy

The string graphs were introduced by Eugene Myers in 2005. This concept is a refinement of the overlap graph approach. The string graph is built by first constructing an overlap graph, joining overlapping reads and further removing transitive edges and reads that are contained within some other read [54] (Figure 1.1D). The string graph is much more expensive to construct than the DBG but it usually better disambiguates short repeats (larger than k but shorter than the read length) and is more compact to store. The most widely used software implementation of the string graph approach is SGA [14].

1.3 Current ways to benchmark genome assemblies