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

• Пржибельский Андрей Дмитриевич
• кандидат наук
• 2020

Оглавление диссертации кандидат наук Пржибельский Андрей Дмитриевич

Введение

Глава 1. Задача сборки биологических последовательностей

1.1 Сборка последовательностей с нуля

1.2 Сборка генома по единичной клетке

1.3 Разрешение повторов и скаффолдинг

1.4 Сборка транскриптомов

1.5 Оценка качества сборки

Глава 2. Сборка генома

2.1 Существующие методы сборки генома

2.2 Геномный сборщик БРАс^й

2.3 Построение графа сборки

2.3.1 Построение графа де Брюйна

2.3.2 Упрощение графа

2.3.3 Итеративное построение графа

2.4 Разрешение повторов и скаффолдинг при помощи парно-концевых ридов

2.4.1 функция оценки продолжений пути

2.4.2 Обработка повторов

2.4.3 Скаффолдинг

2.4.4 Оценка параметров алгоритма

2.5 Использование парных библиотек с большим расстоянием вставки

2.5.1 Удлинение путей

2.5.2 Выбор продолжающих путей

2.5.3 Скаффолдинг при помощи парных библиотек с большим расстоянием вставки

2.5.4 Использование уникальных ребер в графе сборки

2.6 Результаты

2.6.1 Сборка стандартных парно-концевых библиотек

Стр.

2.6.2 Сборка парно-концевых библиотек, полученных по единичной клетке

2.6.3 Сборка библиотек с большим расстоянием вставки

2.6.4 Сравнение с другими геномными сборщиками

2.6.5 Сравнение различных технологий секвенирования

2.7 Заключение

Глава 3. Сборка транскриптома

3.1 От сборки генома к сборке транскриптома

3.2 Упрощение графа

3.2.1 Удаление хвостов

3.2.2 Удаление пузырей

3.2.3 Удаление химерических ребер

3.3 Выбор длины к-мера

3.4 Восстановление изоформ

3.4.1 Модификация модуля ех8РАпс!ег для транскриптомной сборки

3.4.2 Использование неоднородного покрытия

3.4.3 Сборка ните-специфичных данных

3.4.4 Вывод контигов

3.5 Оценка качества транскриптомных сборок

3.5.1 Оценка качества без референсного генома

3.5.2 Оценка качества по референсному геному

3.6 Результаты

3.6.1 Результаты на симулированных данных

3.6.2 Результаты на реальных данных

3.7 Заключение

Заключение

Список сокращений и акронимов

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

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

Стр.

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

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

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

Введение

Актуальность работы. Сравнительно низкая цена и высокая доступность технологий Секвенирования Второго Поколения (N08) позволили широко применять их в различных проектах, включающих в себя анализ последовательностей ДНК и РНК. Как правило, один эксперимент секвенирования дает на выходе гигабайты данных, которые нуждаются в быстрой и качественной обработке. В процессе разработки программ для анализа данных возникло множество алгоритмических и вычислительных задач, включая задачу сборки генома и транскриптома "с нуля". Несмотря на то, что в последние 15 лет было разработано множество программ, называемых сборщиками (или ассемблерами), задача сборки все еще не может считаться полностью решенной. Одна из причин — постоянно обновляющиеся протоколы секвенирования и новые биотехнологические экспериментальные установки. Поэтому, есть необходимость в постоянной поддержке и обновлении существующего программного обеспечения, а также разработке новых и усовершенствовании старых алгоритмов для анализа данных секвенирования.

Одним из недавних биотехнологических прорывов стала разработка метода секвенирования генома по единичной клетке [1;2]. Этот метод предоставил новые возможности для изучения некультивируемых бактерий, которые можно встретить практически в любых экосистемах, а также в эукариотических организмах, в том числе и человеке. Стоит отметить, что данные, полученные с помощью такого метода, значительно отличаются от стандартных данных секвенирования, и следовательно не могут быть корректно собраны с помощью существующего программного обеспечения. Для анализа этих данных требуется разработка новых алгоритмов сборки.

Задача сборки генома включает в себя множество различных аспектов, таких как исправление ошибок секвенирования, заполнение пропусков в покрытии и разрешение геномных повторов. Геномные повторы являются одной из главных проблем, решить которую невозможно одними лишь вычислительными методами. Для решения задачи разрешения повторов были разработаны различные методы секвенирования, позволяющие считывать парные риды, длинные риды и геномные карты [3;4]. Новые типы данных, в свою очередь, требовали создания новых вычислительных методов. Несмотря на то, что бактериальные

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

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

Основные задачи данной работы:

— разработка и реализация алгоритмов сборки бактериальных геномов по стандартным данным секвенирования, а также данным, полученным по единичной клетке; сравнение реализованных методов с существующими аналогами;

— разработка и реализация алгоритмов разрешения повторов и скаффол-динга для малых и среднеразмерных геномов; тестирование разработанных методов и сравнение с более ранними аналогами;

— разработка и реализация алгоритмов транскриптомной сборки по данным Н.\Л-8е<|: тестирование и сравнение с существующими аналогами на организмах с различной сложностью структуры генов.

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

— БРАс^й: геномный сборщик для бактериальных и других геномов небольшого размера (cab.spbu.ru/software/spades/);

— ех8РАпс!ег: модуль для разрешения повторов и скаффолдинга (является частью БРАс^й);

— rnaSPAdes: транскриптомный сборщик, основанный на SPAdes (cab. spbu.ru/software/rnaspades/).

Разработанные вычислительные методы были признаны одними из мировых лидеров в своей области [6; 7]. Основываясь на десятках пользовательских запросов ежемесячно, а также тысячах скачиваний, можно судить что оба сборщика широко используются биоинформатиками по всему миру. Некоторые из наиболее важных исследований осуществленных при помощи разработанного программного обеспечения представлены в завершающей главе данной диссертации. Стоит также отметить, что основная публикация, описывающая сборщик SPAdes [8], по состоянию на октябрь 2019 года имеет более 4900 цитирований по базе Scopus, что делает ее самой цитируемой российской статьей за последние десять лет.

Методы. Как и многие другие сборщики коротких ридов, SPAdes основан на концепции графа де Брюйна [9]. По сравнению с классическими ассемблерами, SPAdes хорошо справляется с обработкой данных с неравномерным покрытием, что позволяет делать качественные сборки на разных типах данных. Сборщик rnaSPAdes был реализован поверх геномной версии SPAdes и включает в себя важные модификации, которые позволяют эффективно обрабатывать данные транскриптомного секвенирования. Модуль ExSPAdner реализован как часть сборщика SPAdes и основан на идеи роста путей в графе сборки. Такой подход позволяет использовать различные типы данных секвенирования одновременно, а так же реализовывать алгоритмы для новых типов данных.

Все алгоритмы были реализованы на языках программирования С++ и Python.

Для тестирования и оценки качества работы разработанных методов были использованы утилиты QUAST [10], rnaQUAST [11], TransRate [12] и Detonate [13].

Апробация работы. Результаты данной работы были представлены в устных и стендовых докладах на нескольких международных конференциях:

1. Algorithmic challenges de novo transcriptome assembly, BiATA 2017, Санкт-Петербург, Россия, Август 2017;

2. rnaSPAdes: yet another genome assembler modified for RNA-Seq, UCSD, Сан-Диего, США, Март 2015;

3. ExSPAnder: a Universal Repeat Resolver for DNA Fragment Assembly, ISMB 2014, Бостон, США, Июль 2014; была получена награда Ian

Lawson Van Toch Memorial Award за лучшую студенческую/аспирантскую работу;

4. New Features in SPAdes Genome Assembler, Постер, ISMB 2014, Бостон, США, Июль 2014;

5. New Frontiers of Genome Assembly with SPAdes 3.1, BOSC 2014, Бостон, США, Июль 2014;

6. Genome Draft Assembly Algorithms: From the Very Beginning till Present-day Problems, High-Throughput Sequencing in Genomics, Новосибирск, Россия, Июль 2013;

7. Path-Extend: A New Approach for Repeat Resolution in Genome Assembly, Постер, WABI 2012, Любляна, Словения, Август, 2012.

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

Публикации. Помимо презентаций, результаты работы описаны в пяти научных статьях [8; 14-17], которые опубликованы в международных журналах индексируемых в базах Web of Science и Scopus. Три статьи из этих пяти опубликованы в журналах входящих в первую квартиль.

Основные положения, выносимые на защиту.

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

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

— При помощи кодовой базы SPAdes был разработан транскриптомный сборщик rnaSPAdes. Различными методами для оценки качества тран-

скриптомных сборок было показано, что он позволяет аккуратно и быстро собирать данные Н.\А-8е<| и имеет более высокое качество результатов по сравнению с другими существующими ассемблерами.

Личный вклад. В публикациях [8; 14] основным вкладом автора является разработка и поддержка программного обеспечения, его тестирование на различных данных, а также помощь при подготовке статей. Данная работа выполнена совместно с коллегами Центра Алгоритмической Биотехнологии.

В проекте по разработке модуля ех8РАпс!ег [15] автор является основным разработчиком значительной части алгоритмов. В рамках проекта автор также производил тестирование и оценку качества работы алгоритмов. В последующей публикации [16] автор принимал участие в реализации вычислительных методов и руководил проектом. Обе статьи были преимущественно написаны автором данной диссертации. Разработка модуля ех8РАпс!ег является совместной работой с Ириной Василинец и другими коллегами из Центра Алгоритмической Биотехнологии.

В проекте по разработке транскриптомного сборщика гпаЗРАскй [17; 18] автор принимал участие в реализации алгоритмов, производил их тестирование, руководил проектом в целом и подготовил статью к публикации. Данный проект был выполнен совместно с Еленой Бушмановой и Дмитрием Антиповым.

Объем и структура диссертации. Данная работа включает в себя введение, 3 главы и заключение. Общий объем работы — 92 страницы, включая 19 рисунков и 13 таблиц. Работа ссылается на 119 научных публикаций.

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

Вторая глава содержит описание основных методов, реализованных в рамках сборщика ЭРАс^й и модуля ех8РАпс1ег. Приведены ключевые алгоритмы разрешения повторов и скаффолдинга, а также представлены результаты на различных типах данных. В заключении главы приведено сравнение качества сборок полученных при помощи БРАс^й и других методов сборки.

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

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

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

и

Глава 1. Задача сборки биологических последовательностей

1.1 Сборка последовательностей с нуля

Технологии секвенирования следующего поколения поставили перед био-информатиками задачу сборки генома и транскриптома из миллионов коротких ридов. На сегодняшний день существует большое количество методов анализа данных РНК [19-25] и ДНК [26-31]. Однако, эти методы применимы только для изучения организмов, для которых существует референсный геном и его аннотация генов, таких как, например, мышь и человек. В то же время, в большом количестве научных проектов изучаются ранее не секвенированные виды. В зависимости от целей проекта, секвенируют геном, транскриптом или оба одновременно. Так как для многих видов неизвестны даже последовательности родственных геномов, необходимой становится сборка ридов "с нуля" (de novo).

Большинство современных методов сборки de novo по коротким ридам [32-41] основаны на концепции графа де Брюйна [9], или графа строк [42]. Несмотря на то, что в основе различных ассемблеров лежит одна и та же идея, качество сборок у них может сильно отличаться и зависит от свойств изначальных данных. Иными словами, требуются заметные усилия чтобы имея хорошую алгоритмическую идею реализовать качественное ПО для сборки последовательностей. Каждый сборщик включает в себя различные эвристики для анализа данных секвенирования, что и объясняет существенную разницу между результатами различных ассемблеров. Например, один из ассемблеров может производить высококачественные сборки на бактериальных данных, но при это проигрывать другим утилитам на больших геномах [43].

1.2 Сборка генома по единичной клетке

Стандартные методы полногеномного секвенирования (англ. WGS — whole genome sequencing) требуют миллионов идентичных клеток для проведения эксперимента. Если в проектах по изучению многоклеточных организ-

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

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

ар <о

(J

0 1 2 3 4 5

E.coli genome, Mbp

a

5000 4000 га 3000

чг

6 2000 и

1000

0

0 1 2 3 4 5

E.ccfl genome, Mbp

б

Рисунок 1.1 — Покрытие ридами генома кишечной папочки Е. coli в случаях (а) стандартного секвенирования и (Ь) секвенирования но единичной клетке методом MDA. Графики были получены путем картирования ридов с помощью программы BWA MEM |27| на реферепспый геном Е. coli str. К12 substr. MG1655.

Альтернативным методов секвенирования некультивируемых бактерий является секвенирование по единичной клетке. В конце 90-х начале 2000-х годов был разработан метод полногеномной амплификации (англ. WGA — whole genome amplification) называемый Multiple Displacement Amplification (MDA) [1; 2; 47; 48]. Этот метод позволил производить достаточное для секвенирования количество ДНК даже по одной бактериальной клетке. Хотя это открытие и дало новые возможности для изучения прокариот, оно также потребовало разработку новых алгоритмов сборки генома.

Большинство современных ассемблеров [32; 34-36; 40; 41] основаны на графе де Брюйна [9], для построения которого необходимо разбить исходные риды на более короткие последовательности фиксированной длины к (&-меры) и вычислить их представленность в ридах. В классическом геномном секвенирова-нии риды имеют относительно равномерное покрытие (Рис. 1.1а), что позволяет разделить корректные и ошибочные &-меры. Так как ошибки в коротких ридах случайны, &-меры содержащие ошибку зачастую представлены плохо и имеют низкое покрытие, в то время как часто встречающиеся &-меры (с покрытием в районе среднего) могут считаться корректными (Рис. 1.2). Этот факт используется подавляющим большинством ассемблеров для того чтобы определить отсечку покрытия, разделяющую корректные и ложные &-меры, исправить ошибки секвенирования и собрать более качественные последовательности.

По сравнению со стандартными данными, риды полученные по единичной клетке методом MDA характеризуются сильными вариациями в покрытии (Рис. 1.16), появляющимися вследствии неравномерной амплификации разных участков ДНК. Поэтому, существующие сборщики, большинство из которых фильтрует ошибочные последовательности по глубине покрытия, неприменимы для сборки такого рода данных, так как фильтрация по покрытию просто приведет к потере значительной части данных (Рис. 1.2). Сложность задачи сборки данных, полученных по единичной клетке, также обусловлена наличием химерических ридов, которые соединяют далекие друг от друга участки генома и могут вызывать структурные ошибки сборки.

— — Isolate — Single-cell

50000

1500 Coverage

Рисунок 1.2 Гистограмма покрытия данных секвенирования кишечной папочки Е. coli:

стандартные данные (пунктирная .пиния) и данные полученные но единичной клетке (сплошная .пиния). Каждая точка на графике отображает количество различных позиций в геноме с соответствующим значением покрытия. Графики были получены путем картирования ридов с номощю программы BWA МЕМ |27| на референсный геном Е. coli

str. К12 substr. MG1655.

1.3 Разрешение повторов и скаффолдинг

Геномные еборщики редко выдают полную геномную последовательность на выходе. Как правило, они собирают продолжительные участки, именуемые контигами. Pix длина и количество зависит от (1) ошибок секвенирования, (2) пробелов в покрытии и (3) геномных повторов. В то время как ошибки могут быть скорректированы при помощи различных алгоритмов [32; 49; 50] (например, основываясь на избыточности ридов), для того чтобы закрыть пробелы в покрытии или разрешить неоднозначности, вызванные геномными повторами, необходима дополнительная информация.

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

этот повтор разрешить. Похожая идея используется в задаче скаффолдипга — упорядочивании контигов, разделенных пробелами в покрытии. Парные риды, покрывающие ("перепрыгивающие" через) пробел могут быть использованы для соединения соседних контигов в скаффолды.

Было показано, что парные библиотеки могут быть эффективно использованы для решения задач скаффолдипга и разрешения повторов [15; 51-54]. Парно-концевые библиотеки (англ. paired-end) имеют расстояние до 1 кб и могут быть использованы для разрешения сравнительно коротких повторов. Другой тип библиотек — мейт-пары (англ. mate-pairs) могут иметь расстояние вставки до 20 кб и позволяют разрешать более длинные повторы. Чтобы обеспечить качественную и продолжительную сборку генома чаще всего используют несколько различных библиотек.

Недавно появившиеся технологии секвенирования Pacific Biosciences (PacBio) и Oxford Nanopore (ONT) позволяют получать длинные риды вплоть до 100-200 кб. Такие данные могут быть использованы для разрешения длинных повторов. Главным недостатком этих технологий является крайне высокий процент ошибок — до 10-30%. На сегодняшний день распространены два способа использования таких данных для решения задачи сборки геномов. В первом случае в дополнение к длинным ридам секвенируют также короткие риды с низким уровнем ошибок, что позволяет осуществлять гибридную сборку [41;55-57]. Как правило к графу сборки, построенному по коротким ридам, прикладывают длинные риды, что позволяет разрешить геномные повторы. Другой способ заключается в сборке длинных ридов без какой-либо дополнительной информации [58-60], что требует сравнительно высокого покрытия, а следовательно может быть достаточно дорогим для геномов большого размера.

1.4 Сборка транскриптомов

Анализ данных транскриптомного секвенирования в большинстве случаев производится при помощи методов, использующих референсный геном. Как правило, эти программы решают задачи выравнивания ридов [22; 23; 61; 62], сборки по референсному геному [21; 25; 63], квантификации генов [64-67], анализ дифференциальной экспрессии генов [20; 24;68], поиск фьюжн генов [69-71],

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

Так как молекулы мРНК заметно короче, чем ДНК, и не содержат длинных и сложных повторов, сборка транскриптомных последовательностей может показаться более простой задачей, чем сборка генома. Однако, в сборке транскриптомов есть свои алгоритмические сложности, такие как, например, восстановление последовательностей альтернативных изоформ и паралогичных генов. Также, данные RNA-Seq всегда характеризуются крайне неравномерным покрытием, которое возникает из-за разницы в уровнях экспрессии у различных генов и изоформ. Поэтому, алгоритмы сборки геномных последовательностей не могут быть напрямую применены к транскриптомным данным. На текущий момент было разработано множество алгоритмов для de novo сборки данных RNA-Seq. Некоторые были основаны на уже существующих геномных ассемблерах [38; 72-74], некоторые были разработаны с нуля [39; 75-77]. Несмотря на то, что методы, позволяющие анализировать транскриптомные данные при помощи референсного генома, как правило, позволяют охватить большее количество генов и изоформ [5], сборка с нуля является важной альтернативой для анализа транскриптомных данных.

1.5 Оценка качества сборки

Оценка качества сборки собранных последовательностей является еще одной важной задачей в биоинформатике. Методы для оценки качества сборки широко используются как разработчиками ассемблеров, так и их пользователями. Первые используют ПО для оценки качества с целью тестирования своих алгоритмов, сравнения их с другими методами, поиска слабых мест и возможных алгоритмических улучшений. В научных проектах, где требуется сборка геномов или транскриптомов, таким образом чаще всего осуществляют контроль качества полученных контигов/скаффолдов, а также производят поиск оптимальных вычислительных методов сборки.

Программное обеспечение для оценки качества сборки можно разделить на три категории: (1) не использующие референсный геном, (2) основывающи-

еся на референсном геноме и (3) использующие изначальный набор данных. Первый тип чаще всего является самым быстрым, но наименее информативным. Вторая категория методов требует наличие референсного генома трин-скриптома, что не всегда возможно. Однако, если достоверные референсные последовательности известны, такого рода утилиты [10; 11; 78] способны производить наиболее подробные и информативные данные о качестве сборок. Методы третьего типа зачастую требуют значительного времени для выравнивания ридов на коптиги. но также вычисляют информативные метрики, позволяющие оценить качество сборки [12; 13; 79].

Глава 2. Сборка генома 2.1 Существующие методы сборки генома

Задача сборки генома является одной из наиболее старых и сложных в биоинформатике. Самые первые геномные сборщики [80; 81] были разработаны для данных секвенирования по Сэнгеру, которые отличались сравнительно большой длинной до 900 нк и высокой точностью. В основе этих сборщиков лежал подход OLC (англ. overlap-layout-consensus), основными шагами которого были (1) попарное выравнивание ридов с целью поиска перекрытий между ними, (2) построение графа перекрытий, (3) топологическая сортировка и упорядочивание этого графа, и (4) поиск консенсусной строки.

Появившиеся в начале XXI века технологии секвенирования нового поколения (NGS), такие как Illumina (ранее известная как Solexa), Roche 454 и IonTorrent позволили секвенировать миллионы коротких ридов по куда более низкой цене, чем технология по Сэнгеру. Естественно, алгоритмы, разработанные ранее для длинных и точных ридов, были неприменимы к новому типу данных, в основном из-за того что они требовали слишком много вычислительных ресурсов. В 2001 году был предложен принципиально новый подход к сборке генома [9], который лег в основу множества различных геномных ассемблеров [32-36; 40; 41].

Появление длинных ридов технологий Pacific Biosciences и Oxford Nanopore стало новым прорывом в задаче сборки генома и вернуло к жизни подход OLC, который теперь используется некоторых новых ассемблерах [58-60]. Основным изменением, по сравнению с предыдущими сборщиками, основанными на OLC, стала модификация шага выравнивания и поиска перекрытий между ридами, которая позволила работать с крайне высоким процентом ошибок в ридах, характерным для ONT и PacBio.

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

Список литературы диссертационного исследования кандидат наук Пржибельский Андрей Дмитриевич, 2020 год

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

1. Rapid amplification of plasmid and phage DNA using phi29 DNA polymerase and multiply-primed rolling circle amplification / Frank В Dean, John R Nelson, Theresa L Giesler, Roger S Lasken // Genome research. — 2001. — Vol. 11, no 6 _ Pp 1095-1099.

2. Lasken Roger S. Single-cell genomic sequencing using Multiple Displacement Amplification. // Current opinion in microbiology. — 2007. — Vol. 10. — Pp. 510-516. — URL: http://dx.doi.Org/10.1016/j .mib.2007.08.005.

3. Read length and repeat resolution: exploring prokaryote genomes using next-generation sequencing technologies / Matt J Cahill, Claudio U Koser, Nicholas E Ross, John AC Archer // PloS one. — 2010. — Vol. 5, no. 7.

- P. ell518.

4. Ghurye Jay, Pop Mihai. Modern technologies and algorithms for scaffolding assembled genomes // PLoS computational biology. — 2019. — Vol. 15, no. 6.

- P. el006994.

5. Martin J. A., Wang Z. Next-generation transcriptome assembly // Nat. Rev. Genet. - 2011. - Oct. - Vol. 12, no. 10. - Pp. 671-682.

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

7. Holzer Martin, Marz Manja. De novo transcriptome assembly: A comprehensive cross-species comparison of short-read RNA-Seq assemblers // Giga-Science. — 2019. — Vol. 8, no. 5. — P. giz039.

8. Bankevich Anton et a,I. SPAdes: A New Genome Assembly Algorithm and Its Applications to Single-Cell Sequencing. // Journal of Computational Biology. _ 2012. - Vol. 19. - Pp. 455-477. - URL: http://dx.doi.org/10.1089/ cmb. 2012.0021.

9. Pevzner Pavel A., Tang Haixu, Waterman Michael S. An Eulerian path approach to DNA fragment assembly // Proceedings of the National Acade-

my of Sciences. - 2001. - Vol. 98. - Pp. 9748-9753. - URL: http: //dx.doi.org/10.1073/pnas.171285098.

10. Gurevich Alexey et al. QUAST: quality assessment tool for genome assemblies // Bioinformatics. — 2013. — Vol. 29. — Pp. 1072-1075.

- URL: http://bioinformatics.oxfordjournals.org/content/early/ 2013/03/09/bioinformatics.btt086.abstract.

11. rnaQUAST: a quality assessment tool for de novo transcriptome assemblies / Elena Bushmanova, Dmitry Antipov, Alia Lapidus et al. // Bioinformatics. — 2016. - Vol. 32, no. 14. - Pp. 2210-2212.

12. Smith-Unna Richard et al. TransRate: reference-free quality assessment of de novo transcriptome assemblies // Genome research. — 2016. — Vol. 2, no. 8.

- Pp. 1134-1144.

13. Li b. et al. Evaluation of de novo transcriptome assemblies from RNA-Seq data // Genome Biol. - 2014. - Vol. 15, no. 12. - P. 553.

14. Nurk Sergey et al. Assembling Single-Cell Genomes and Mini-Metagenomes From Chimeric MDA Products. // Journal of Computational Biology. — 2013. _ Vol. 20. - Pp. 1-24.

15. ExSPAnder: a universal repeat resolver for DNA fragment assembly / A. D. Pr-jibelski, I. Vasilinetc, A. Bankevich et al. // Bioinformatics. — 2014. — Jun.

- Vol. 30, no. 12. - Pp. i293-i301. - URL: http://dx.doi.org/10.1093/ bioinformatics/btu266.

16. Assembling short reads from jumping libraries with large insert sizes / Irina Vasilinetc, Andrey D Prjibelski, Alexey Gurevich et al. // Bioinformatics. _ 2015. - Vol. 31, no. 20. - Pp. 3262-3268.

17. rnaSPAdes: a de novo transcriptome assembler and its application to RNA-Seq data / Elena Bushmanova, Dmitry Antipov, Alia Lapidus, Andrey D Prjibelski // GigaScience. — 2019.

18. rnaSPAdes: a de novo transcriptome assembler and its application to RNA-Seq data / Elena Bushmanova, Dmitry Antipov, Alia Lapidus, Andrey D Prjibelski // hioRxiv. - 2018. - P. 420208.

19. Systematic evaluation of spliced alignment programs for RNA -seej data j Pär G Engström, Tamara Steijger, Botond Sipos et al. /j Nature methods. _ 2013. - Vol. 10, no. 12. - P. 1185.

20. Robinson Mark D, McCarthy Davis J, Smyth Gordon K. edgeR: a Bioconduc-tor package for differential expression analysis of digital gene expression data // Bioinformatics. - 2010. - Vol. 26, no. 1. - Pp. 139-140.

21. Trapnell Cole et al. Differential gene and transcript expression analysis of RNA-Seq experiments with TopHat and Cufflinks /j Nature protocols. — 2012. - Vol. 7, no. 3. - P. 562.

22. STAR: ultrafast universal RNA-seq aligner / Alexander Dobin, Carrie A Davis, Felix Schlesinger et al. // Bioinformatics. — 2013. — Vol. 29, no. 1. — Pp. 15-21.

23. Kim Daehwan et al. TopHat2: accurate alignment of transcriptomes in the presence of insertions, deletions and gene fusions /j Genome Biol. — 2013. — Vol. 14, no. 4. - P. R36.

24. Love Michael I, Huber Wolfgang, Anders Simon. Moderated estimation of fold change and dispersion for RNA-seq data with DESeq2 /j Genome biology. — 2014. - Vol. 15, no. 12. - P. 550.

25. Pertea Mihaela et al. StringTie enables improved reconstruction of a transcrip-tome from RNA-seq reads // Nature biotechnology. — 2015. — Vol. 33, no. 3. _ p. 290.

26. Langmead Ben, Salzberg Steven L. Fast gapped-read alignment with Bowtie 2 // Nature methods. - 2012. - Vol. 9, no. 4. - Pp. 357-359.

27. Li Heng. Aligning sequence reads, clone sequences and assembly contigs with BWA-MEM // arXiv preprint arXiv:1303.3997. - 2013.

28. Li Heng. Minimap2: pairwise alignment for nucleotide sequences /j Bioinformatics. - 2018. - Vol. 34, no. 18. - Pp. 3094-3100.

29. The sequence alignment/map format and SAMtools / Heng Li, Bob Handsak-er, Alec Wysoker et al. // Bioinformatics. — 2009. — Vol. 25, no. 16. — Pp. 2078-2079.

30. Genotype and SNP calling from next-generation sequencing data / Rasmus Nielsen, Joshua S Paul, Anders Albrechtsen, Yun S Song // Nature Reviews Genetics. - 2011. - Vol. 12, no. 6. - P. 443.

31. Ruffalo Matthew, LaFramboise Thomas, Koyutürk Mehmet Comparative analysis of algorithms for next-generation sequencing read alignment // Bioinfor-matics. - 2011. - Vol. 27, no. 20. - Pp. 2790-2796.

32. Zerbino Daniel R., Birney Ewan. Velvet: Algorithms for de novo short read assembly using de Bruijn graphs // Genome Research. — 2008. — Vol. 18. — Pp. 821-829. - URL: http://dx.doi.org/10.1101/gr.074492.107.

33. ALLPATHS: de novo assembly of whole-genome shotgun microreads / J. Butler, I. MacCallum, M. Kleber et al. // Genome Research. — 2008. — Vol. 18. - Pp. 810-820.

34. ABySS: a parallel assembler for short read sequence data / J.T. Simpson, K. Wong, S.D. Jackman et al. // Genome Research. — 2009. — Vol. 19. — P. 1117.

35. Boisvert Sébastien, Laviolette François, Corbeil Jacques. Ray: Simultaneous Assembly of Reads from a Mix of High-Throughput Sequencing Technologies // Journal of Computational Biology. — 2010. — Vol. 17. — Pp. 1519-1533. — URL: http : //dx. doi. org/10.1089/cmb. 2009.0238.

36. De novo assembly of human genomes with massively parallel short read sequencing / R. Li, H. Zhu, J. Ruan et al. // Genome Research. — 2010. — Vol. 20. - Pp. 265-272.

37. Simpson Jared T, Durbin Richard. Efficient construction of an assembly string graph using the FM-index // Bioinformatics. — 2010. — Vol. 26, no. 12. — Pp. i367-i373.

38. Robertson G. et al. De novo assembly and analysis of RNA-seq data // Nat. Methods. - 2010. - Vol. 7, no. 11. - Pp. 909-912.

39. Grabherr M. G. et al. Full-length transcriptome assembly from RNA-Seq data without a reference genome // Nat. Biotechnol. — 2011. — Jul. — Vol. 29, no. 7. - Pp. 644-652.

40. IDBA-UD: A de novo assembler for single-cell and metagenomic sequencing data with highly uneven depth. / Y Peng, H C M Leung, S M Yiu, F Y L Chin // Bioinformatics. - 2012. - Vol. 28. - Pp. 1-8. - URL: http://www.ncbi.nlm.nih.gov/pubmed/22495754.

41. Zimin Aleksey V et al. The MaSuRCA genome assembler // Bioinformatics. _ 2013. - Vol. 29, no. 21. - Pp. 2669-2677.

42. Myers Eugene W. The fragment assembly string graph // Bioinformatics. —

2005. - Vol. 21, no. suppl 2. - Pp. ii79-ii85.

43. GAGE: A critical evaluation of genome assemblies and assembly algorithms / Steven L Salzberg, Adam M Phillippy, Aleksey Zimin et al. // Genome research. - 2012. - Vol. 22, no. 3. - Pp. 557-567.

44. Meta-IDBA: a de Novo assembler for metagenomic data / Yu Peng, Henry CM Leung, Siu-Ming Yiu, Francis YL Chin // Bioinformatics. — 2011. - Vol. 27, no. 13. - Pp. i94—ilOl.

45. MEGAHIT: an ultra-fast single-node solution for large and complex metage-nomics assembly via succinct de Bruijn graph / Dinghua Li, Chi-Man Liu, Ruibang Luo et al. // Bioinformatics. — 2015. — Vol. 31, no. 10. — Pp. 1674-1676.

46. metaSPAdes: a new versatile metagenomic assembler / Sergey Nurk, Dmitry Meleshko, Anton Korobeynikov, Pavel A Pevzner // Genome research. — 2017. - Vol. 27, no. 5. - Pp. 824-834.

47. Mutation detection and single-molecule counting using isothermal rolling-circle amplification / Paul M Lizardi, Xiaohua Huang, Zhengrong Zhu et al. // Nature genetics. - 1998. - Vol. 19, no. 3. - Pp. 225-232.

48. Whole-genome multiple displacement amplification from single cells / Claudia Spits, Cedric Le Caignec, Martine De Rycke et al. // Nature protocols. —

2006. - Vol. 1, no. 4. - Pp. 1965-1970.

49. Kelley D.R., Schatz M.C., Salzberg S.L. Quake: quality-aware detection and correction of sequencing errors // Genome Biology. — 2010. — Vol. 11. — P. R116.

50. Nikolenko S.I., Korobeynikov A.I., Alekseyev M.A. BayesHammer: Bayesian clustering for error correction in single-cell sequencing // BMC Genomics. — 2013. - Vol. 14.

51. Pop M.. Kosack D. S., Salzberg S. L. Hierarchical scaffolding with Bambus // Genome Res. - 2004. - Jan. - Vol. 14, no. 1. - Pp. 149-159.

52. Gao S., Sung W. K., Nagarajan N. Opera: reconstructing optimal genomic scaffolds with high-throughput paired-end sequences // J. Comput. Biol. — 2011. - Nov. - Vol. 18, no. 11. - Pp. 1681-1691.

53. Telescoper: de novo assembly of highly repetitive regions / M. Bresler, S. Shee-han, A.H. Chan, Y.S. Song // Bioinformatics. — 2012. — Vol. 28. — Pp. 311-317.

54. Donmez N., Brudno M. SCARPA: scaffolding reads with practical algorithms // Bioinformatics. — 2013. — Feb. — Vol. 29, no. 4. — Pp. 428-434.

55. Chevreux Bastien. MIRA: an automated genome and EST assembler. — 2007.

56. Antipov Dmitry et a,I. hybridSPAdes: an algorithm for hybrid assembly of short and long reads // Bioinformatics. — 2015. — Vol. 32, no. 7. — Pp. 1009-1015.

57. Unicycler: resolving bacterial genome assemblies from short and long sequencing reads / Ryan R Wick, Louise M Judd, Claire L Gorrie, Kathryn E Holt // PLoS computational biology. — 2017. — Vol. 13, no. 6. — P. el005595.

58. Canu: scalable and accurate long-read assembly via adaptive k-mer weighting and repeat separation / Sergey Koren, Brian P Walenz, Konstantin Berlin et al. // Genome research. — 2017. — Vol. 27, no. 5. — Pp. 722-736.

59. Li Heng. Minimap and miniasm: fast mapping and de novo assembly for noisy long sequences // Bioinformatics. — 2016. — Vol. 32, no. 14. — Pp. 2103-2110.

60. Assembly of long, error-prone reads using repeat graphs / Mikhail Kolmogorov, Jeffrey Yuan, Yu Lin, Pavel A Pevzner // Nature biotechnology. — 2019. — P. 1.

61. Liao Yang, Smyth Gordon K, Shi Wei. The Subread aligner: fast, accurate and scalable read mapping by seed-and-vote // Nucleic acids research. — 2013. — Vol. 41, no. 10. - Pp. el08-el08.

62. Kim Da ehwa n, Langmead Ben, Salzberg Steven L. HISAT: a fast spliced aligner with low memory requirements // Nature methods. — 2015. — Vol. 12, no. 4.

_ p. 357.

63. Shao Mingfu, Kingsford Carl. Accurate assembly of transcripts through phase-preserving graph decomposition // Nature biotechnology. — 2017. — Vol. 35, no. 12. - P. 1167.

64. Li Bo, Dewey Colin N. RSEM: accurate transcript quantification from RNA-Seq data with or without a reference genome // BMC bioinformatics. _ 2011. - Vol. 12, no. 1. - P. 323.

65. Anders Simon, Pyl Paul Theodor, Huber Wolfgang. HTSeq^a Python framework to work with high-throughput sequencing data // Bioinformatics. — 2015. - Vol. 31, no. 2. - Pp. 166-169.

66. Patro Rob, Duggal Geet, Kingsford Carl. Salmon: accurate, versatile and ultra-fast quantification from RNA -seq data using lightweight-alignment // bioRxiv. _ 2015. - P. 021592.

67. Near-optimal probabilistic RNA-seq quantification / Nicolas L Bray, Harold Pi-mentel, Pali Meisted, Lior Pachter // Nature biotechnology. — 2016. — Vol. 34, no. 5. - P. 525.

68. limma powers differential expression analyses for RNA-sequencing and microar-ray studies / Matthew E Ritchie, Belinda Phipson, Di Wu et al. // Nucleic acids research. — 2015. — Vol. 43, no. 7. — Pp. e47 e47.

69. Kim Daehwan, Salzberg Steven L. TopHat-Fusion: an algorithm for discovery of novel fusion transcripts // Genome biology. — 2011. — Vol. 12, no. 8. — P. R72.

70. deFuse: an algorithm for gene fusion discovery in tumor RNA-Seq data / Andrew McPherson, Fereydoun Hormozdiari, Abdalnasser Zayed et al. // PLoS computational biology. — 2011. — Vol. 7, no. 5. — P. el001138.

71. InFusion: advancing discovery of fusion genes and chimeric transcripts from deep RNA-sequencing data / Konstantin Okonechnikov, Aki Imai-Matsushima, Lukas Paul et al. // PloS one. - 2016. - Vol. 11, no. 12. - P. e0167417.

72. Schulz Marcel H et a,I. Oases: robust de novo RNA-seq assembly across the dynamic range of expression levels // Bioinform,aMcs. — 2012. — Vol. 28, na g. _ Pp 1086-1092.

73. Peng Yu et a,I. IDBA-tran: a more robust de novo de Bruijn graph assembler for transcriptomes with uneven expression levels // Bioinformatics. — 2013.

- Vol. 29, no. 13. - Pp. i326 i334.

74. Xie Yinlong et a,I. SOAPdenovo-Trans: De novo transcriptome assembly with short RNA-Seq reads // Bioinformatics. — 2014. — P. btu077.

75. Bridger: a new framework for de novo transcriptome assembly using RNA-seq data / Zheng Chang, Guojun Li, Juntao Liu et al. // Genome biology. — 2015.

- Vol. 16, no. 1. - P. 30.

76. BinPacker: packing-based de novo transcriptome assembly from RNA-seq data / Juntao Liu, Guojun Li, Zheng Chang et al. // PLoS computational biology. _ 2016. - Vol. 12, no. 2. - P. el004772.

77. Nip Ka Ming. RNA-Bloom: de novo RNA-seq assembly with Bloom filters: Ph.D. thesis / University of British Columbia. — 2017.

78. Plantagora: Modeling Whole Genome Sequencing and Assembly of Plant Genomes / Roger Barthelson, Adam J. McFarlin, Steven D. Rounsley, Sarah Young // PLoS ONE. - 2011. - 12. - Vol. 6. - P. e28436.

79. Hunt Martin et al. REAPR: a universal tool for genome assembly evaluation // Genome Biol. - 2013. - Vol. 14, no. 5. - P. R47.

80. A whole-genome assembly of Drosophila / Eugene W Myers, Granger G Sutton, Art L Delcher et al. // Science. - 2000. - Vol. 287, no. 5461. - Pp. 2196-2204.

81. The sequence of the human genome / J Craig Venter, Mark D Adams, Eugene W Myers et al. // science. - 2001. - Vol. 291, no. 5507. - Pp. 1304-1351.

82. Bolger Anthony M, Lohse Marc, Usadel Bjoern. Trimmomatic: a flexible trimmer for Illumina sequence data // Bioinformatics. — 2014. — Vol. 30, no. 15.

- Pp. 2114-2120.

83. Martin Marcel. Cutadapt removes adapter sequences from high-throughput sequencing reads // EMBnet. journal. — 2011. — Vol. 17, no. 1. — Pp. pp-10.

84. Compeau F., Pevzner P.A., Tesler G. How to apply de Bruijn graphs to genome assembly // Nature Biotechnology. — 2011. — Vol. 29. — Pp. 987-91.

85. Scaffolding pre-assembled contigs using SSPACE / M. Boetzer, C. V. Henkel, H. J. Jansen et al. // Bioinformatics. — 2011. — Feb. — Vol. 27, no. 4. — Pp. 578-579.

86. Chaisson M.J., Pevzner P.A. Short read fragment assembly of bacterial genomes // Genome Research. — 2008. — Vol. 18. — P. 324.

87. Simpson Jared T, Durbin Richard. Efficient de novo assembly of large genomes using compressed data structures // Genome research. — 2012. — Vol. 22, no. 3. - Pp. 549-556.

88. Souvorov Alexandre, Agarwala Richa, Lipman David J. SKESA: strategic k-mer extension for scrupulous assemblies // Genome biology. — 2018. — Vol. 19, no. 1. - P. 153.

89. Efficient de novo assembly of single-cell bacterial genomes from short-read data sets / Hamidreza Chitsaz, Joyclyn L. Yee-Greenbaum, Glenn Tesler et al. // Nature Biotechnology. - 2011. - Vol. 29. - Pp. 915-921. - URL: http: //dx.doi.org/10.1038/nbt.1966.

90. Assembling large genomes with single-molecule sequencing and locality-sensitive hashing / Konstantin Berlin, Sergey Koren, Chen-Shan Chin et al. // Nature biotechnology. — 2015. — Vol. 33, no. 6. — P. 623.

91. Fast and accurate de novo genome assembly from long uncorrected reads / Robert Vaser, Ivan Sovic, Niranjan Nagarajan, MileSikic // Genome research. _ 2017. - Vol. 27, no. 5. - Pp. 737-746.

92. Grabherr M.G., Mauceli E., Ma, L.J. Genome Sequencing and Assembly // Methods in molecular biology (Clifton, NJ). — 2011. — Vol. 722. — P. 1.

93. Bankevich Anton, Pevzner Pavel A. TruSPAdes: barcode assembly of TruSeq synthetic long reads // Nature methods. — 2016. — Vol. 13, no. 3. — P. 248.

94. Borodino, Tatiana, Ad,jo,ye James, Sultan Marc. A strand-specific library preparation protocol for RNA sequencing // Methods in enzymology. — Elsevier, 2011. - Vol. 500. - Pp. 79-98.

95. Sim,a,o Felipe A et al. BUSCO: assessing genome assembly and annotation completeness with single-copy orthologs // Bioinformatics. — 2015. — Vol. 31, na 19_ _ Pp_ 3210-3212.

96. Altschul Stephen F et al. Basic local alignment search tool // Journal of molecular biology. - 1990. - Vol. 215, no. 3. - Pp. 403-410.

97. Versatile and open software for comparing large genomes / Stefan Kurtz, Adam Phillippy, Arthur Delcher et al. // Genome Biology. — 2004. — Vol. 5. _ p. Ri2. _ URL: http://genomebiology.eom/2004/5/2/R12.

98. Camacho Christiam et al. BLAST+: architecture and applications // BMC bioinformatics. — 2009. — Vol. 10, no. 1. — P. 421.

99. Kent W. J. BLAT-the BLAST-like alignment tool // Genome Res. - 2002. _ Apr. - Vol. 12, no. 4. - Pp. 656-664.

100. Wu Thomas D, Watanabe Colin K. GMAP: a genomic mapping and alignment program for mRNA and EST sequences // Bioinformatics. — 2005. — Vol. 21, na 9 _ pp. 1859-1875.

101. Near-optimal probabilistic RNA-seq quantification / Nicolas L Bray, Harold Pi-mentel, Pall Melsted, Lior Pachter // Nature biotechnology. — 2016. — Vol. 34, no. 5. - P. 525.

102. Ebola virus disease in the Democratic Republic of Congo / Gaël D Maganga, Jimmy Kapetshi, Nicolas Berthet et al. // New England Journal of Medicine. _ 2014. - Vol. 371, no. 22. - Pp. 2083-2091.

103. The role of China in the global spread of the current cholera pandemic / Xavier Didelot, Bo Pang, Zhemin Zhou et al. // PLoS genetics. — 2015. — Vol. 11, no. 3. - P. el005072.

104. Genomic history of the seventh pandemic of cholera in Africa / François-Xavier Weill, Daryl Domman, Elisabeth Njamkepo et al. // Science. _ 2017. - Vol. 358, no. 6364. - Pp. 785-789.

105. Defining endemic cholera at three levels of spatiotemporal resolution within Bangladesh / Daryl Domman, Fahima Chowdhury, Ashraful I Khan et al. // Nature genetics. — 2018. — P. 1.

106. Draft genome sequencing of Vibrio cholerae 01 El Tor isolates collected in the Russian Federation from imported cholera cases / Konstantin V Kuleshov, Sergey O Vodop'ianov, Vladimir G Dedkov et al. // Genome Announc. — 2014.

- Vol. 2, no. 4. - Pp. e00624 14.

107. Whole-genome sequences of Chlamydia trachomatis directly from clinical samples without culture / Helena MB Seth-Smith, Simon R Harris, Rachel J Skilton et al. // Genome research. — 2013. — Vol. 23, no. 5. — Pp. 855-866.

108. Candidate phylum TM6 genome recovered from a hospital sink biofilm provides genomic insights into this uncultivated phylum / Jeffrey S McLean, Mary-Jane Lombardo, Jonathan H Badger et al. // Proceedings of the National Academy of Sciences. - 2013. - Vol. 110, no. 26. - Pp. E2390-E2399.

109. plasmidSPAdes: assembling plasmids from whole genome sequencing data j Dmitry Antipov, Nolan Hartwick, Max Shen et al. // hioRxiv. — 2016. — P. 048942.

110. Plasmid detection and assembly in genomic and metagenomic data sets / Dmitry Antipov, Mikhail Raiko, Alia Lapidus, Pavel A Pevzner // Genome research. _ 2019. - Vol. 29, no. 6. - Pp. 961-968.

111. IDBA-MT: de novo assembler for metatranscriptomic data generated from next-generation sequencing technology / Henry CM Leung, Siu-Ming Yiu, John Parkinson, Francis YL Chin // Journal of Computational Biology. — 2013. - Vol. 20, no. 7. - Pp. 540-550.

112. Leung Henry CM, Yiu Siu-Ming, Chin Francis YL. IDBA-MTP: a hybrid Metatranscriptomic assembler based on protein information // Journal of Computational Biology. — 2015. — Vol. 22, no. 5. — Pp. 367-376.

113. Highly parallel direct RNA sequencing on an array of nanopores / Daniel R Gar-aide, Elizabeth A Snell, Daniel Jachimowicz et al. // Nature methods. — 2018.

- Vol. 15, no. 3. - P. 201.

114. Defining a personal, allele-specific, and single-molecule long-read transcrip-tome / Hagen Tilgner, Fabian Grubert, Donald Sharon, Michael P Snyder // Proceedings of the National Academy of Sciences. — 2014. — P. 201400447.

115. Nanopore long-read RNAseq reveals widespread transcriptional variation among the surface receptors of individual B cells / Ashley Byrne, Anna E Beaudin, Hugh E Olsen et al. // Na,ture Communications. — 2017. _ Vol. g. _ p. 16027.

116. Exploiting single-molecule transcript sequencing for eukaryotic gene prediction / André E Minoche, Juliane C Dohm, Jessica Schneider et al. // Genome biology. - 2015. - Vol. 16, no. 1. - P. 184.

117. A survey of the sorghum transcriptome using single-molecule long reads / Salah E Abdel-Ghany, Michael Hamilton, Jennifer L Jacobi et al. // Nature communications. — 2016. — Vol. 7. — P. 11706.

118. Widespread polycistronic transcripts in fungi revealed by single-molecule mR-NA sequencing / Sean P Gordon, Elizabeth Tseng, Asaf Salamov et al. // PloS one. - 2015. - Vol. 10, no. 7. - P. e0132628.

119. Microfluidic isoform sequencing shows widespread splicing coordination in the human transcriptome / Hägen Tilgner, Fereshteh Jahanbani, Ishaan Gupta et al. // Genome research. - 2018. - Vol. 28, no. 2. - Pp. 231-242.

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

1.1 Покрытие генома ридами, полученными методами стандартного секвенирования и секвенирования по единичной клетке................12

1.2 Гистограмма покрытия стандартных данных и данных, полученных

по единичной клетке........................................................14

2.1 Примеры ошибочных ребер в графе де Брюйна........................21

2.2 Итеративное построение графа сборки в БРАс^й........................22

2.3 Парный рид, соединяющий два ребра в графе..........................25

2.4 Пример повтора в графе сборки..........................................28

2.5 Пример тандемного повтора в графе сборки............................28

2.6 Пример короткого потенциального продолжения пути..................32

2.7 Построение множества продолжающих путей............................35

2.8 Пузырь и цикл в графе сборки............................................36

2.9 Скаффолдинг при помощи данных с большим расстоянием вставки. 37

3.1 Хвосты в транскриптомном графе сборки................................53

3.2 Пузыри в транскриптомном графе сборки ..............................54

3.3 Химерические ребра в транскриптомном графе сборки................55

3.4 Формирование химерических контигов при транскриптомной сборке 56

3.5 Восстановление изоформ по покрытию..................................59

3.6 Использование ните-спецпфичных данных..............................60

3.7 Зависимость доли 95%-собранных генов от покртыия на симулированных данных..................................................67

3.8 Доля 95%-собранных генов на всех данных..............................67

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

1 Геномные данные, использованные для тестирования алгоритмов . . 40

2 Результат работы модуля exSPAnder на парно-концевых данных бактерии В. cereus............................. 42

3 Результат работы модуля exSPAnder на парно-концевых данных бактерии Е. coli.............................. 42

4 Результат работы модуля exSPAnder на парно-концевых данных бактерии P. marinus, полученных по единичной клетке........43

5 Результат работы модуля exSPAnder на различных данных

бактерии В. faecium............................ 44

6 Результат работы модуля exSPAnder на данных типа NexteraMP

для бактерии L. monocytogenes...................... 45

7 Сравнение различных геномных сборщиков на стандартных данных

Е. coli.................................... 46

8 Сравнение различных геномных сборщиков на данных S. aureus, полученных по единичной клетке.................... 46

9 Сравнение сборок бактерии A. mi/rum, полученных с помощью различных технологий секвенирования................. 48

10 Сравнение сборок бактерии Е. coli, полученных с помощью различных технологий секвенирования................. 49

11 SPAdes и другие сборщики на данных транскриптомного секвенирования нематоды С. elegans......................................51

12 Сравнение транскриптомных сборщиков на симулированных данных 66

13 Сравнение транскриптомных сборщиков на реальных данных .... 68

SAINT PETERSBURG STATE UNIVERSITY

Printed as a manuscript

Andrey D. Przhibelskiy

DEVELOPMENT OF ALGORITHMS FOR DE NOVO GENOME AND TRANSCRIPTOME ASSEMBLY

Specialty 03.01.09 -«Mathematical biology, bioinformatics»

PhD thesis

Scientific advisers: PhD, professor Pavel A. Pevzner PhD, professor Alia L. Lapidus

Saint Petersburg — 2019

Table of contents

P.

Introduction......................................................................96

Chapter 1. Sequence assembly problem.................101

1.1 De novo sequence assembly.......................101

1.2 Single-cell genome assembly ......................101

1.3 Repeat resolution and scaffolding ...................104

1.4 Transcriptome assembly ........................105

1.5 Assembly quality evaluation......................105

Chapter 2. De novo genome assembly..................107

2.1 Existing approaches to genome assembly problem...........107

2.2 SPAdes genome assembler pipeline...................108

2.3 Assembly graph construction......................108

2.3.1 De Bruijn graph construction .................108

2.3.2 Graph simplification ......................109

2.3.3 Iterative graph construction..................110

2.4 Repeat resolution and scaffolding using paired-end reads.......Ill

2.4.1 The scoring function......................113

2.4.2 Dealing with repeats......................115

2.4.3 Scaffolding............................117

2.4.4 Parameters estimation.....................118

2.5 Incorporating long-rage mate-pair libraries ..............119

2.5.1 Path-to-path extension.....................119

2.5.2 Choosing extension paths....................120

2.5.3 Scaffolding using mate-pairs..................122

2.5.4 Using unique edges of the assembly graph...........124

2.6 Results..................................125

2.6.1 ExSPAnder performance on conventional paired-end datasets 127

2.6.2 ExSPAnder performance on single-cell paired-end dataset . . 129

2.6.3 ExSPAnder performance on mate-pair datasets........129

P.

2.6.4 Comparison against other genome assemblers.........131

2.6.5 Comparison with other sequencing technologies........132

2.7 Conclusion................................134

Chapter 3. De novo transcriptome assembly..............135

3.1 From single-cell genome to transcriptome assembly..........135

3.2 De Bruijn graph simplification.....................137

3.2.1 Tip clipping...........................137

3.2.2 Bulge removal..........................138

3.2.3 Chimeric edge removal.....................139

3.3 Selecting k-mer size...........................140

3.4 Isoform reconstruction .........................141

3.4.1 Modifying exSPAnder for transcriptome assembly ......142

3.4.2 Exploiting uneven coverage depth...............142

3.4.3 Assembling strand-specific data................143

3.4.4 Outputting contigs.......................145

3.5 Quality assessment of transcriptome assemblies............146

3.5.1 Reference-free quality evaluation................146

3.5.2 Reference-based quality evaluation...............146

3.6 Results..................................148

3.6.1 Results on simulated data...................148

3.6.2 Results on real RNA-Seq data.................151

3.7 Conclusion................................152

Conclusions...................................154

List of abbverations and acronyms.....................157

Glossary.....................................158

References....................................162

Table of figures.................................174

Table of tables.................................175

Introduction

Motivation. Due to low cost and high availability, Next Generation Sequencing (NGS) technologies revealed novel possibilities for studying sequences of DNA and RNA molecules. Typically, a single NGS experiment produces gigabytes of digital data, which requires fast and high-quality analysis. Demand m data processing software have raised new algorithmic and computational challenges, including problems of de novo genome and transcriptome assembly from short reads. Even though many tools (called assemblers) were developed in the last 15 years, these problems are still not considered as being completely solved. One of the reasons is that a rapidly growing field of biotechnology constantly produces new sequencing protocols and improves experimental instruments, which, indeed, requires bioinformatics tools to be kept up to date. Thus, researches need to permanently design novel algorithms and improve previously developed software.

One of such biotechnological improvements was the invention of single-cell bacterial sequencing [1; 2], which opened new wide possibilities for studying genomes of uncultivated prokaryotes that can be found everywhere in natural environments and higher organisms. Data obtained with this method, however, significantly differs from the one generated by conventional sequencing, and therefore, could not be adequately assembled using existing tools. Novel computational assembly methods were required to take full benefit from single-cell sequencing.

Genome assembly problem implies multiple different issues, such as presence of sequencing errors, coverage gaps and genomic repeats. The later one is considered to be one of the key challenges and cannot be solved by algorithmic improvements alone. Various sequencing methods, such as paired reads, long error-prone reads and genomic maps were designed to address the problem of repeat resolution [3; 4]. Indeed, new types of data have a need for novel computational methods. Although bacterial genomes are know to be far less complex than large eukaryotic genomes in terms of repeat structure, accurate and reliable algorithms for resolving repeats are still required to produce high-quality bacterial assemblies, especially for the case single-cell data.

To complement genomic studies, various protocols for RNA sequencing were designed to enable analysis of gene expression and RNA-related processes. For organisms with known genome sequence, transcriptomes and gene expression profiles

are typically studied via reference-based analysis. However, high-quality reference genomes are available only for the small fraction of known organisms, which brings the problem of de novo transcriptome assembly. While being somewhat similar to the genome assembly, it has some crucial differences and therefore requires special tools to be designed. Although various transcriptome assemblers were developed in the past decade, none of them can be considered as perfect and there is a space for further algorithmic improvements in this area [5].

The main goals of this work include

— development of algorithms for de novo assembly of bacterial genomes from standard and single-cell data, and its comparison against state-of-the-art assemblers;

— design and implementation of algorithms for repeat resolution and scaffolding of small and medium-sized genomes, as well as its benchmarking on different types of sequencing data;

— design and development of algorithms for de novo transcriptome assembly from RNA-Seq data; its benchmarking on organisms with different gene structure complexity.

The practical value and the novelty. This work has resulted in the following software tools and submodules:

— SPAdes: de novo assembly framework for bacterial and other small-sized genomes from conventional and single-cell sequencing data (cab.spbu.ru/ software/spades/);

— exSPAnder: the algorithm for repeat resolution and scaffolding (implemented as a part of SPAdes genome assembler);

— rnaSPAdes: SPAdes-based de novo transcriptome assembler (cab.spbu.ru/ software/rnaspades/).

The developed computational methods were acknowledged as one of the best in their fields [6; 7]. Based on the number of user requests (dozens per month) and thousands of downloads from different countries across the globe, one can state that both tools appear to be widely used by the scientific community. Some of the most notable studies performed using the developed assemblers are listed in the concluding chapter of the manuscript. Worths noting, that the main SPAdes publication [8] has more than 4900 citations according to Scopus database (as for October 2019), which makes it the most cited Russian paper in the last decade.

Methods. Similar to other modern assembly tools, SPAdes is based on the de Bruijn graph approach [9]. In contrast to conventional assembly software, SPAdes successfully deals with highly uneven coverage depth, which allows it to generate high-quality assemblies on both standard and single-cell datasets. RnaSPAdes was implemented on top of SPAdes framework and includes several important modifications that allow to effectively assemble transcript sequences from RNA-Seq data. ExSPAdner framework was developed as a SPAdes submodule and is based on path extension approach in the assembly graph. Such idea allowed to utilize various types of sequencing data simultaneously and effectively implement algorithms for novel data types by reusing existing methods.

All tools were implemented using C++ and Python languages.

For testing and benchmarking of the developed methods, such utilities as QUAST [10], rnaQUAST [11], TransRate [12] and Detonate package [13] were used.

Work presentation. Results of this work were presented at following international meetings and conferences either as an oral talk or as a poster:

1. Algorithmic challenges de novo transcriptome assembly, BiATA 2017, St. Petersburg, Russia, August 2017;

2. rnaSPAdes: yet another genome assembler modified for RNA-Seq, UCSD, San Diego, USA, March 2015;

3. ExSPAnder: a Universal Repeat Resolver for DNA Fragment Assembly, ISMB 2014, Boston, USA, July 2014; received Ian Lawson Van Toch Memorial Award for Outstanding Student Paper;

4. New Features in SPAdes Genome Assembler, Poster at ISMB 2014, Boston, USA, July 2014;

5. New Frontiers of Genome Assembly with SPAdes 3.1, BOSC 2014, Boston, USA, July 2014;

6. Genome Draft Assembly Algorithms: From the Very Beginning till Present-day Problems, High-Throughput Sequencing in Genomics, Novosibirsk, Russia, July 2013;

7. Path-Extend: A New Approach for Repeat Resolution in Genome Assembly, Poster at WABI 2012, Ljubljana, Slovenia, August 2012.

In addition, multiple presentations and talks on this work were given at various scientific schools and research group meetings.

Publications. In addition to listed presentations, the results were described in five papers [8; 14-17] that were published in journals indexed in Web of Science

and Scopus databases. Three of these papers are published in journals currently ranked as Ql.

Main results of the dissertation.

— During this work, multiple computational modules and algorithms were developed within SPAdes genome assembler. Various benchmarks, including third-party ones, showed that SPAdes allows to perform high-quality assemblies of bacterial and other small genomes from conventional and single-cell sequencing data, and typically outperforms other state-of-the-art assemblers.

— The exSPAnder algorithm for repeat resolution and scaffolding was designed and implemented as a part of SPAdes genome assembler. ExSPAnder is developed as a universal framework capable of exploiting various kinds of genome linkage information and allows to easily enhance its functionality for novel data types, such as, for example, genomic maps. Different comparisons show that exSPAnder accurately resolves repeats in bacterial genomes, and thus allows SPAdes to deliver stable and reliable assemblies.

— A de novo transcriptome assembler rnaSPAdes was developed on top of SPAdes. It produces accurate assemblies from RNA-Seq data and, according to various benchmarks, shows good results comparing to previously developed transcriptome assemblers.

Personal contribution. In the papers [8; 14] the author contributed to the design and implementation of various algorithms, maintained the software, performed testing and benchmarking on various datasets, contributed to the manuscripts preparation. This is a joint work with the colleagues from Center for Algorithmic Biotechnology.

In the exSPAnder paper [15] the author proposed and developed exSPAnder basic algorithms, performed benchmarking on multiple data sets. In the subsequent paper [16] the author participated in the design and implementation of exSPAnder improvements and supervised the research. The developed exSPAnder module is a joint work with Irina Vasilinetc and other colleagues from Center for Algorithmic Biotechnology. Both papers were written primary by the author of this thesis.

In the rnaSPAdes project [17; 18] the author designed and implemented several algorithms, supervised the project and wrote the manuscript. RnaSPAdes is a joint research with Elena Bushmanova and Dmitry Antipov.

Structure of the work. The dissertation includes an introduction, 3 chapters and a conclusion. The text of the dissertation contains 83 pages, including 19 figures and 13 tables. References include 119 citations.

In the first chapter the problem of de novo sequence assembly is formulated and information on the current state of this field is provided. In particular, this chapter focuses on the problems of assembling data with uneven coverage depth, repeat resolution and scaffolding. Additionally, main challenges of transcriptome assembly problem are briefly discussed.

The second chapter presents of the core ideas and methods implemented in SPAdes genome assembler and the exSPAnder module. The key algorithms of exSPAnder approach are described and its benchmarking on different types of data is given. In addition, several quality reports for SPAdes and other state-of-the-art assembly tools are provided.

In the third chapter the discussion on the problem of de novo sequence assembly continues from the perspective of transcriptomics. This chapter describes the key differences between genome and transcriptome assembly problems, and presents modifications introduced in rnaSPAdes assembler. In addition, quality evaluation of de novo transcriptome assemblies is discussed, and comparison between rnaSPAdes and other methods is presented on various RNA-Seq datasets.

The conclusion briefly discusses the proposed methods, their impact on scientific community and potential further direction for their development.

Chapter 1. Sequence assembly problem

1.1 De novo sequence assembly

Next-generation sequencing technologies have raised challenging problems of de novo genome and transcriptome assembly from millions of short reads. While multiple reference-based methods are now available for analysis of both RNA [1925] and DNA sequencing data [26-31], these tools are designed for well-studied organisms with quality constructed reference genomes and gene databases, such as e.g. H. sapiens, M. musculus, E. coli etc. At the same time, there are thousands of ongoing research projects studying previously unsequenced species. Depending on the goal of the particular project, they may include sequencing of a genome, a transcriptome or both. Since for some species even sequences of related genomes are not available, de novo assembly comes to the rescue.

Most state-of-the-art methods for de novo sequence assembly from NGS reads [32-41] are based on the de Bruijn graph approach [9] or later developed String graph [42]. However, performance of these tools may greatly vary depending on the data set properties, even though their core algorithms are based on the same idea. It appears that there is a long road from a great computational idea to the high-quality assembly software, that is capable of providing decent results on real sequencing data. All tools include their own heuristics for analyzing sequencing data, which make them work differently. For example, while one assembler may generate the best assemblies for small bacterial genomes, another one may outperform the first one on large mammalian genomes [43].

1.2 Single-cell genome assembly

Conventional whole genome sequencing (WGS) experiment requires millions of identical cells containing copy of a single genome. While this requirement usually sets no limitations for projects studying eukaryotic organisms, it may become a stumbling block in bacterial studies. Typically, in order to obtain multiple copies of

the same genome, bacteria is being artificially cultivated in the laboratory (called isolate). However, a lot of bacterial communities contain hundreds or even thousands of different species and strains, thus making it virtually impossible to reproduce suitable conditions in the lab for a single selected type of bacteria. Therefore, the majority of existing bacterial species remain uncultivated.

To overcome this issue, one may use a popular metagenomic approach that implies sequencing of whole bacterial community at once. Metagenomic datasets are usually large and contain reads from various species and strains, which at the same time have different abundances across the community. However, current methods for metagenome assembly [44 46] typically require extreme computational resources for processing large amount of data, while the resulting sequences tend to appear rather fragmented and hard to classify.

a

b

Figure 1.1 — Coverage distribution along the genome for E. coli (a) isolate and (b) single-cell MDA datasets. These plots were obtained by mapping reads using BWA MEM |27| to the E. coli

str, K12 substr, MG1655 reference genome.

Another approach for sequencing an uncultivated bacteria is so called single-cell sequencing. In late 1990;s whole genome amplification (WGA) method called Multiple Displacement Amplification (MDA) [1; 2; 47; 48] revealed the possibility to obtain enough genomic material for a sequencing experiment from a single copy of of bacterial genome. Even though this breakthrough opened new possibilities for

studying prokaryotae, it also raised new computational problems in de novo genome assembly.

The majority of modern short-read genome assembly methods [32;34 36;40;41] are based on the de Bruijn graph approach [9], which includes splitting reads into shorter sequences of a fixed length k (called fc-mers) and counting their abundances in reads. In conventional genome sequencing, reads typically have relatively uniform coverage across the genome (Fig. 1.1a), thus making it possible to separate erroneous and true genomic fc-mers. Since sequencing errors are random, fc-mers containing errors typically have low abundance, while more frequent fc-mers (with coverage similar to average) can be considered as correct (Fig. 1.2). This fact is usually used by the majority genome assemblers to detect coverage threshold, correct sequencing errors and, thus, generate high-quality assemblies.

In contrast to conventional data, reads generated from a single cell via MDA typically have highly uneven coverage depth (Fig. 1.1b) due to non-uniform amplification of different genomic regions. Therefore, most of existing methods that incorporate filtering by coverage are inapplicable for assembling single-cell data sets, since coverage cut-off just drops significant part of the data (Fig. 1.2). The challenge of assembling such data is further amplified by the presence of chimeric reads that connect distant genomic regions and cause misassemblies.

— — Isolate — Single cell

50000

40000

.9 30000

-a

E

20000

10000

!\

i\

V /

........ \

SD0

1000

1500

Coverage

Figure 1.2 Coverage histogram for E. coli isolate (dashed) and single-cell (solid) sequencing

data. Each point in the plot represent a number of distinct positions having corresponding coverage. The plot was obtained by mapping reads using BWA MEM |27| to the E. coli str, K12

substr, MG1655 reference genome.

1.3 Repeat resolution and scaffolding

De novo assemblers rarely produce the entire genome sequence as an output. Assembly tools typically generate long genomic regions called contigs, the number and length of which may vary depending on (i) sequencing errors, (ii) coverage gaps and (iii) genomic repeats. While sequencing errors can be usually eliminated or corrected using various existing algorithms [32; 49; 50] (e.g. based on coverage depth), additional information is needed to close gaps or resolve genomic repeats.

One of the possible ways to resolve ambiguities caused by genomic repeats that are longer than the read length is to sequence paired reads — a couple of genomic fragments, outer ends of which are separated by approximately known distance called insert size. In case when the length of a repeat is shorter than the insert size, paired reads may span over this repeat thus making it possible to map read pairs to its unique flanking regions and resolve it. Similar idea can be used for scaffolding — ordering contigs separated by coverage gaps. Reads spanning a coverage gap may be useful for joining neighboring contigs into a scaffold.

Paired reads proved to be effective for repeat resolving and scaffolding procedures [15; 51-54]. Paired-end libraries typically have insert size shorter that 1 kbp and are used for resolving short repeats, while mate-pair libraries may have insert size up to 20 kbp and are useful for resolving relatively long repeats. For large genomes multiple paired libraries are usually sequenced in order to obtain continuous and correct assembly.

Recently emerged Pacific Biosciences and Oxford Nanopore sequencers allow to obtain reads up to 100-200 kbp long, and thus can be used for resolving very long repeats. However, the main drawback for these technologies is the extreme error rate of 10-30%. In general, there are two possible ways to utilize such error-prone sequencing data. The first one is to sequence both long erroneous and accurate short reads and perform hybrid assembly [41; 55-57], i.e. map long reads to the assembly graph in order to resolve repeats and close gaps. Another method — assembling long reads without any additional information [58-60], requires relatively high coverage of the dataset and thus may appear to be costly in case of large eukaryotic genomes.

1.4 Transcriptome assembly

Currently, reference-based approaches dominate in the field of transcriptomics. These methods typically address the problems of RNA-Seq read alignment [22; 23; 61;62], reference based assembly [21;25;63], RNA quantification [64-67], differential gene expression analysis [20;24;68], fusion gene discovery [69-71], etc. However, these methods are designed for the model organisms with high-quality reference genome and gene annotation. Since multiple research project aim to study transcriptomes of previously unsequenced species, transcriptomics also requires a de novo assembly.

Indeed, mRNA molecules are much shorter than DNA and do not contain complex repeats, thus making de novo transcriptome assembly to look like a simpler problem than genome assembly. However, assembling RNA-Seq data has its own algorithmic challenges, such as correct reconstruction of paralagous genes and alternatively spliced isoforms, as well as dealing with highly uneven coverage depth caused by varying expression levels of different genes and isoforms. This issues (especially the later one) do not allow to apply genome assembly tools directly to RNA-Seq data. Currently, the problem of transcriptome assembly is addressed by several tools, some of which are based on previously developed genome assemblers [38; 72-74], and some of which are implemented from scratch [39; 75-77]. Although de novo assemblers typically produce fewer full-length transcripts that the reference based methods [5], they provide viable alternative for reference-free transcriptome analysis.

1.5 Assembly quality evaluation

Assessing quality of sequences generated by the assembly algorithms present another important challenge in computational genomics and transcriptomics. Such methods are highly demanded by the developers of the assembly tools and their users. The first ones mostly use quality assessment software for testing, benchmarking and comparing against existing tools on various types of data in order to find weak points, improve their algorithms and prove that the developed methods outperform the existing ones. Bioinformaticians who work on real assembly projects

use evaluation software for comparing different tools and performing quality control of the generated contigs.

Assembly quality software approaches can be categorized into three groups: (i) reference-free, (ii) reference-guided and (iii) read-based. The first one requires no additional information and is typically quick, but least informative of all three. The second approach requires a high-quality reference genome and a gene database in some cases, which may not be available for studied organism. However, if the ground truth is known, reference-based evaluation tools [10; 11; 78] produce the most informative reports and allows to perform excessive analysis of the generated assemblies. The last group of tools typically require more time for aligning reads back onto the assembly, but also produce useful statistics and information about the generated assemblies [12; 13; 79].

Chapter 2. De novo genome assembly 2.1 Existing approaches to genome assembly problem

The problem of de novo genome assembly is one of the oldest and most challenging bioinformatics problems. The very first assemblers [80; 81] developed for accurate and long Sanger reads were based on the concept of overlap-layout-consensus (OLC). OLC approach typically includes such steps as pairwise alignment of all reads, detection of overlapping regions and construction of overlap graph based on these alignments, graph layout and computation of consensus sequence.

Originated in the very beginning of XXI century Next-Generation Sequencing (NGS) technologies, such as Illumina (previously known as Solexa), Roche 454 and later IonTorrent allow to produce millions of short reads for a far lower price comparing to Sanger. Indeed, previously designed algorithms appeared to be inapplicable to NGS data, mainly due to their computational performance. In 2001, a novel approach for genome assembly based on the de Bruijn graph was proposed [9]. Later, multiple great tools were developed based on this concept [32-36; 40; 41].

Possibility to generate long error-prone reads using Pacific Biosciences and Oxford Nanopore sequencers became a recent breakthrough in the field of DNA sequencing and brought OLC back to life, which is now implemented in multiple genome assemblers [58-60]. The key modification in these tools comparing to previously designed pipelines is an improved overlap detection step, which can handle extreme error rates of ONT and PacBio reads.

All mentioned tools, however, are designed for conventional sequencing data, characterized by the uniform coverage depth along the genome. Since multiple implemented heuristics are heavily based on this data property, they are not applicable for single-cell assembly, where coverage can be extremely uneven. This chapter is devoted to the description of developed novel assembly algorithms capable of assembling data with non-uniform coverage. In particular, it focuses on the problem of repeat resolution and scaffolding using assembly graph and various types of read-pair sequencing data. In conclusion, benchmarks of the developed computational method on multiple datasets and its comparison against other assemblers are provided.

2.2 SPAcles genome assembler pipeline

SPAdes de novo genome assembler was initially developed for single-cell bacterial assemblies. Later, its functionality was extended to enable assembly of conventional datasets for bacterial and small-size genomes. SPAdes pipeline consists of three major modules: (i) BayesHammer read error correction tool [50], (ii) core assembly module and (iii) MismatchCorrector tool for contig polishing. The fist and the last modules can be excluded from the assembly pipeline. E.g., BayesHammer can be substituted with, for example, Quake error correction tool [49], or faster trimming software, such as Trimmomatic [82] or cutadapt [83]. Polishing step is also optional and is turned off by default. MismatchCorrection is designed to reduce mismatch and short indel error rates and does not affect other assembly characteristics.

The core assembly module includes the major following steps: (i) de Bruijn graph construction, (ii) graph simplification, (iii) read alignment and (iv) repeat resolution and scaffolding using exSPAnder module. During two first stages the de Bruijn graph (defined below) is constructed and cleaned from erroneous edges of various origin. The resulting graph is often referred to as the assembly graph. Then, read pairs and long reads are aligned to the graph. Further, this information is exploited for repeat resolution and scaffolding procedures in order to obtain long genomic fragments called contigs and scaffolds respectively.

2.3 Assembly graph construction

2.3.1 De Bruijn graph construction

SPAdes assembler is designed for assembling short reads and based on the concept of the de Bruijn graph [9; 84], which can be defined as follows. Let Sf denote a substring of string S of length k starting at position i (often referred to as &-mer). A de Bruijn graph for string S and a parameter k is defined as an oriented graph with set of vertices V = | i = 1... IS | — k + 1} and set of edges

E = {(u,v)lu G V,v G V, 3i : u + v\ = Sf+1}. Informally speaking, vertices of the de Bruijn graph are all possible fc-mers from S, which are connected by k + 1-mers from S (edges) in such way that starting vertex is a prefix and terminal vertex is a suffix of a corresponding k + 1-mer.

A condensed de Bruijn graph is obtained from usual de Bruijn graph by merging all unambiguous paths. Let indegree(v) be incoming and outdegree(v) be outgoing degree of vertex v. The condensation operation can be applied to vertices u, v and w connected by edges (u,v) and (v, w) if vertex v has no other adjacent edges (indegree(v) = outdegree(v) = 1) and substitutes edges (u,v) and (v,w) with a single edge (u,w), such that its corresponding sequence equals u + vI + (thus preserving initial sequence). The condensed graph contains no vertices with indegree(v) = outdegree(v) = 1, beside trivial loops (v,v).

To perform the assembly, the de Bruijn graph is constructed from all input reads and their reverse-compliment copies, thus making the graph symmetric. I.e., for each vertex v in the graph there is a conjugate vertex v and for each edge (u,v) there is an edge (v,u). Conjugate graph element are assigned with reverse-complement sequences. Since k value is typically chosen as odd, every vertex in the graph has a conjugate pair. However, there is a possibility of having self-conjugate edges, i.e. e = e. These edges correspond to reverse-complement palindromic sequences of even length, e.g. AAATTT.

2.3.2 Graph simplification

Since input data typically contains sequencing errors, de Bruijn graphs constructed from reads contain multiple erroneous edges, which have to be removed. The process of cleaning the graph is called simplification, while the cleaned graph is referred to as the assembly graph. Various types of errors in sequencing data result in a different substructures in the de Bruijn graph. Typically, they are classified into three categories: (i) tips — dead-end or dead-start edges (Fig. 2.1a), (ii) bulges — erroneous alternative paths (Fig. 2.1b) and (iii) chimeric connections — edges with no typical structure which often connect distant parts of the graph (Fig. 2.1c). Since such edges may result into incorrect contigs in the assembler output, correct classification and removal of erroneous edges is essential for genome assembly.

e o

"e7

a

ei

c >

b

ei

cK>

\e

->o

o

e3 e4

c

->o

Figure 2.1 — Examples of erroneous edges in de Bruijn graph: (a) a tip; (b) a bulge; (e) a chimeric connection. In each figure erroneous edge is drawn with dashed line and noted as e',

correct edges are drawn with solid lines.

While most of the existing assemblers rely on fc-mer coverage depth [32; 3436], SPAdes simplification procedure are designed specifically to deal with uneven coverage depth. In order to address the problem of assembling data with non-uniform coverage and chimeric junctions SPAdes implements various techniques for removing erroneous edges based mostly on the de Bruijn graph topology, and less dependent on coverage depth. Details on these methods are described in [8; 14].

e

e

2.3.3 Iterative graph construction

Another problem caused by single-cell sequencing methods is the presence of regions with extremely low coverage that negatively affect assembly contiguity. In such regions the number of overlapping bases between reads may simply be not enough to create a connection in the de Bruijn graph. While lowering the fc-mer size solves the problem, it also makes the resulting graph extremely tangled, which complicates further analysis, such as repeat resolution and scaffolding. Larger k values, on the other hand, result in a more fragmented graph consisting of multiple disjoint components.

To address this issue SPAdes implements iterative graph construction technique, which allows to use multiple fc-mer sizes. During the first iteration, the assembly graph is constructed with a relatively small k value, which allows to restore low-covered regions where overlaps between neighboring reads are short. Then, sequences from the graph edges are extracted and along with the initial reads are fed as an input to the next assembly iteration with larger fc-mer size (Fig. 2.2). Low-covered regions assembled during the first iteration contain fc-mers that are

not present in the initial reads and thus allow to preserve missing connections in the graph. At the same time, larger k resolves short repeats and creates a less tangled graph. The graph obtained at the final iteration is then processed to the repeat resolution module.

Figure 2.2 — A pipeline for the iterative graph construction implemented in SPAdes assembler.

Depending on the properties of the dataset, SPAdes uses various sets offc-mer lengths. For read length of 100 bp SPAdes has three iterations with k equal to 21, 33, 55. For datasets with longer reads, SPAdes increases the number of iterations and value of last k being used up to an approximately read length divided by 2. For single-cell datasets, however, the nearly optimal values remain 21, 33, 55 regardless of the read length.

2.4 Repeat resolution and scaffolding using paired-end reads

Once the final assembly graph is constructed, reads pairs and long error-prone reads are aligned to the graph in order to obtain connections between edges. Depending on the type of sequencing data, SPAdes either uses existing mapping tools, such as BWA MEM [27], or internal alignment algorithm based on the exact fc-mer matching.

By mapping paired-reads SPAdes constructs so called paired index a specially developed data structure for storing linkage information between edges. For each pair of edges a distance between them according to paired-reads and the number of pairs that support this distance are stored. After paired reads are aligned, the index is processed to estimate true distances between edges, restore missing and remove contradictory information.

While conventional assembly tools perform repeat resolution and scaffolding steps independently, in SPAdes both procedures are implemented a single module called exSPAnder [15], and are performed simultaneously. ExSPAnder takes as input an assembly graph, paired information indices constructed from multiple read-pair libraries and paths obtained from mapping long reads. Since hybrid assembly using short accurate and long error-prone reads is not a part of this work, only algorithms that exploit paired libraries are described in this manuscript.

ExSPAnder iteratively constructs paths in the assembly graph and outputs them as resulting contigs and scaffolds. Similar path-extension-based methods were previously implemented in Ray [35] and Telescoper [53]. The exSPAnder algorithm starts with long reliable edges that are not included in any path yet and iteratively extends the paths in both directions. At every step, the algorithm attempts to select the best extension according to a scoring function (described below). If several sequencing libraries are provided as an input, scoring functions are constructed separately for each library and are applied individually one by one in the given order, until the extension edge is successfully chosen. The path is being extended until no reliable extension can be chosen or extension cannot be selected unambiguously using all available information. Path construction is performed until every edge of the graph is included in at least one path. After the paths are constructed, overlap removal procedures are applied in order to avoid duplicated sequences in the resulting assembly.

By implementing new scoring functions and extension selection procedure it is possible to easily design new pipelines and adapt exSPAnder for different types of sequencing data. Although currently exSPAnder is capable of exploiting multiple types of data, support for paired-end reads was the first and the most important part, since nowadays it remains the most common short-read sequencing protocol. In order to utilize paired-end libraries for repeat resolution, at every step exSPAnder considers only edges, outgoing from the terminal vertex of the current path and selects one extension at a time. Extension edges are ranked using scoring function and top-scored edge is selected if its score (i) exceed a certain threshold 6 and (ii) is at least C times larger than a second ranked extension.

2.4.1 The scoring function

The key algorithmic challenge in the path-extension framework is to properly design a scoring function for a given type of sequencing data. As SPAdes was initially designed for bacterial single-cell assembly, which is characterized by extremely nonuniform coverage depth and elevated rate of chimeric reads/read-pairs, a proper scoring function should not depend on (i) coverage depth, (ii) chimeric read-pairs and (iii) edge lengths. To meet these conditions, scoring function for paired-end reads developed in exSPAnder (i) takes into account only read-pairs with insert size within expected value range in order to minimize influence from chimeric read-pairs and (ii) relies rather on uniformity of read-pairs connecting the path and its extension edges, rather that simply on the count of read-pairs. The scoring function is described as follows.

r\ T'2

i

X\\ x2 o-1----------------o—^-k)

ei

< D '

Figure 2.3 — Examples of a paired read (ri,r2) mapping to edges e\ and e2 at positions X\ and x2 respectively. The distance between these edges according to the read-pair (r\,r2) is computed as D = I mean — RL — x2 + wher e /mea™ is the average insert size of the 1 ibrarv and RL is the

read length. This figure is adapted from |15|,

A pair of reads connects two edges if each read in this pair has at least partial mapping to the corresponding edge (Fig. 2.3). Let F(x) be the empirical insert size distribution, that can be obtained by mapping read-pairs to relatively long edges of the assembly graph (e.g. longer than 1 kbp), and Ic = [Imin, Imax] be an 80% confidence interval of F(#). Let e1 and e2 be a pair of edges in the graph and d be the fixed distance between them. Using these parameters, one can calculate the number of expected read-pairs that have insert size within Ic and connect e1 and e2 in the ideal case, i.e. when the coverage is ideally uniform. This value is further denoted as Expected(e1,e2,d).

Observed(e1, e2, d) is defined as the number of real read-pairs connecting edges e1 and e2 at distance d and having inserts size within the confidence interval Ic (denoted as Pointsd(e1, e2) in [15]). Clearly, the raw number of read-pairs connecting

edges of the current path being extended and its possible extension edges cannot be utilized since it heavily depends on the coverage depth and edge lengths. To avoid such bias, the read-pair density is introduced as

Observed(eb e2,d) Density(ei, e2, d) = E „ 1 62 , (2-1)

i2

and represents relative paired coverage between edges. Density(ei, e2, d) = 0 for the case when Expected(ei, e2,d) = 0, which can occur when the distance is too large, i.e. d > length(ei) + Imax. Two edges are considered as supported by the read-pair library if their paired-end density exceeds a small threshold *. More formally

Supportsi, e^.d) = J 1, DenSttV(eu ^d) > * (2.2)

0,

Let the path P = (pi,...,pn) be the path that is being extended and e be its possible extension edge (i.e. outgoing from terminal vertex ofpn). Let di be the distance from pi to e according to P: di = ength(pj). A scoring function is

defined as

S ( ) = En=0 SuPPort(Pj, e^ dj) ■ Expected(pj ^, dj)

En=o Expected(pj, e,dj)

This scoring function has a value range [0; 1] and represents the ratio between how