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

• Антипов Дмитрий Юрьевич
• кандидат наук
• 2022

Оглавление диссертации кандидат наук Антипов Дмитрий Юрьевич

Введение

Глава 1. Введение в задачу сборки генома и геномный

сборщик SPAdes

1.1 Геном и ДНК

1.2 Технологии секвенирования

1.3 Методы сборки de novo

1.4 Краткое изложение алгоритма работы геномного сборщика SPAdes

1.4.1 Общая структура сборщика SPAdes

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

1.4.3 Удаление ошибочных ребер

1.4.4 Итеративное построение графа сборки

1.4.5 Использование информации о прикладывании парных чтений. Краткое изложение алгоритма exSPAnder

Глава 2. Гибридная сборка с помощью алгоритма hybridSPAdes

2.1 Технологии секвенирования третьего поколения

2.2 Подходы к гибридной сборке

2.3 Модуль гибридной сборки hybridSPAdes

2.3.1 Общая структура алгоритма hybridSPAdes

2.3.2 Построение выравнивания длинных чтений на граф де Брюйна

2.3.3 Дополнение отсутствующих в графе де Брюйна участков генома с помощью длинных чтений

2.3.4 Разрешение повторных участков генома с помощью информации о прикладывании длинных чтений

2.4 Результаты

2.5 Заключение

Стр.

Глава 3. Сборка и выделение плазмидных

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

3.1 Введение

3.2 Существующие методы

3.3 Равномерность покрытия в графах построенных по данным N08

3.4 Модуль plasmidSPAdes для сборки плазмид

3.4.1 Алгоритм plasmidSPAdes

3.4.2 Тестирование plasmidSPAdes

3.5 Модуль plasmidVeгify для проверки плазмидного происхождения последовательности

3.5.1 Алгоритм plasmidVeгify

3.5.2 Тестирование plasmidVeгify

3.6 Модуль metaplasmidSPAdes для сборки плазмид из данных метагеномного секвенирования

3.6.1 Введение

3.6.2 Алгоритм metaplasmidSPAdes

3.6.3 Результаты metaplasmidSPAdes

3.7 Заключение

Заключение

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

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

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

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

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

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

Введение

Актуальность работы. В настоящее время все большее число исследовательских задач в биологии не может обойтись без знания геномных последовательностей изучаемого организма. Первичная структура ДНК (геномная последовательность) определяется (или же секвенируется) с помошью специального инструмента — секвенатора. Результатом работы секвенатора является получение огромного количества очень коротких по сравнению с длиной полного генома подстрок изучаемого организма — так называемых чтений. Чтения могут содержать ошибки и дублирующуюся информацию. Для проведения дальнейшего анализа чаще всего требуется объединить их в возможно более длинные (в идеале соответствующие полным хромосомам) подстроки исходного генома — так называемые контиги. Процесс такого объединения называется сборкой генома и осуществляется специализированной компьютерной программой программой — геномным сборщиком. Можно выделить два базовых вида сборки: референсную, то есть использующую уже известный геном какого-либо родственника изучаемого организма, и de novo или сборку с нуля, без опоры на известные референсные последовательности. Далее в данной работе будут обсуждаться исключительно проблемы сборки de novo.

Развитие и удешевление технологий секвенирования после появления так называемых технологий секвенирования второго поколения привело к взрывному росту числа исследовательских проектов, связанных с секвенированием геномных последовательностей. Несмотря на то, что первые геномные сборщики были разработаны более тридцати пяти лет назад [98; 119], данная область продолжает активно развиваться. Это связано как с изменением технологий секвенирования, так и с увеличением объемов анализируемых данных, что выдвигает новые требования к эффективности используемых вычислительных алгоритмов. Наиболее популярные сборщики для технологий второго поколения основаны на так называемых графах де Брюйна [100].

Появление в 2010-х так называемых секвенаторов третьего поколения позволяет получать длинные геномные последовательности (десятки тысяч нуклео-тидов). Минусом этих технологий является большое количество ошибок в чтениях. Для таких данных не подходит использование популярных сборщиков, основанных на графах де Брюйна, напрямую, и требуется разработка новых

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

Часто исследователям интересен не весь геном изучаемого организма, а какая-то его часть. Одним из примеров таких потенциально интересных фрагментов генома в случае бактерий являются плазмиды — молекулы ДНК, находящиеся внутри клетки, физически обособленные от хромосом и способные к независимому размножению. Плазмиды, в частности, являются частыми носителями генов, отвечающих за устойчивость к антибиотикам, и участвуют в горизонтальном переносе генов между различными бактериями [70]. Отделять плазмиды от остального генома можно как на стадии пробоподготовки [41], так и после — на стадии геномной сборки и постпроцессинга результатов сборки.

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

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

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

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

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

— hybгidSPAdes: модуль для гибридной сборки (является частью SPAdes);

— plasmidSPAdes: специализированный сборщик плазмид, основанный на SPAdes (https://cab.spbu.ru/software/plasmid-spades/, является частью SPAdes).

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

— plasmidVeгify: Модуль для проверки того является ли данная последовательность ДНК плазмидой, (https://github.com/ablab/ plasmidVerify)

Основываясь на результатах независимых сравнений (например [28; 78; 95]), можно утверждать, что данные модули являются как минимум одни-

ми из лидеров для решения соответствующих задач сборки. Это утверждение подтверждается большим числом цитирований соответствующих публикаций (более 9000 у SPAdes, 170 у hybridSPAdes и 180 у plasmidSPAdes вместе с metaplasmidSPAdes) в международной базе SCOPUS.

Методы. Сборщик SPAdes для представления данных использует граф де Брюйна [100]. Для удаления ребер, соответствующих ошибочным чтениям, используются в первую очередь соображения, связанные с топологией графа, а не с покрытием, что позволяет использовать SPAdes для сборки данных секве-нирования единичной клетки и модифицировать для сборки метагеномов [137] и транскриптомов [139]. hybridSPAdes использует выравнивания длинных ошибочных чтений на ребра графа с помощью bwa mem [74]. Далее эти выравнивания обрабатываются с использованием методов динамического программирования и графовых алгоритмов. Алгоритмы plasmidSPAdes и metaplasmidSPAdes используют различия в покрытии между плазмидными и хромосомными последовательностями ДНК. Модуль plasmidVerify основан на наивном байесовском классификаторе [45].

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

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

1. : Assembling Plasmids from Whole Genome Sequencing Data, устный доклад, RECOMB-SEQ 2016, Лос-Анджелес, США, апрель 2016.

2. New members of SPAdes assembly tools family, постер, RECOMB 2016, Лос-Анджелес, апрель 2016.

3. SPAdes Family of Tools for Genome Assembly and Analysis: What's New, постер, SFAF 2017, Санта-Фе, май 2017

4. Plasmid Detection and Assembly in Genomic and Metagenomic Datasets, устный доклад, ASM Conference on Rapid Applied Microbial Next-Generation Sequencing and Bioinformatic Pipelines, Тайсонс Корнер, США, сентябрь 2018

5. SPAligner: Alignment of long diverged molecular sequences to assembly graphs, устный доклад, BIATA 2019, Санкт-Петербург, 2019

6. metaplasmidSPAdes: Plasmid Detection and Assembly in Genomic and Metagenomic Datasets, устный доклад, MCCMB 2019, Москва, июль 2019

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

Публикации. Помимо докладов на конференциях, результаты работы описаны в пяти научных статьях [12; 93; 104; 136; 138], которые опубликованы в международных журналах индексируемых в базах Web of Science и Scopus. Три статьи из этих пяти опубликованы в журналах входящих в первый квартиль.

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

— Был разработан и реализован алгоритм hybridSPAdes — модуль для совместного использования данных секвенирования третьего поколения и данных секвенирования NGS. Было показано, что hybridSPAdes выдает сборки, сравнимые по качеству с другими сборщиками, и может превосходить их в случаях низкого покрытия секвенируемого генома чтениями третьего поколения.

— На основе кодовой базы SPAdes был разработан специализированный сборщик plasmidSPAdes для сборки плазмид из данных бактериального секвенирования. Было показано, что он умеет собирать плазмиды из данных секвенирования бактерий качественнее, чем альтернативные инструменты.

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

Личный вклад. В публикациях [12; 93] основным вкладом автора является разработка и поддержка программного обеспечения, его тестирование на различных данных, а также помощь при подготовке статей. Данная работа выполнена совместно с коллегами из Лаборатории Алгоритмической Биологии (Санкт-Петербургский Академический Университет).

В проекте по разработке модуля hybridSPAdes [136] автор является единственным автором алгоритмов. В рамках проекта автор также производил разработку, тестирование и оценку качества работы программного модуля.

В проекте по разработке специализированных модулей для сборки плаз-мид plasmidSPAdes и metaplasmidSPAdes [104; 138] автор занимался разработкой алгоритмов, реализацией и тестированием их имплементации в виде програм-ных модулей, а также готовил статьи к публикации. Данный проект был выпол-

нен совместно с Михаилом Райко, отвечавшим за реализацию и тестирование модуля plasmidVeгify.

Объем и структура диссертации. Данная работа включает в себя введение, 3 главы и заключение. Общий объем работы — 78 страницы, включая 5 рисунков и 12 таблиц. Работа ссылается на 142 научные публикации.

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

Вторая глава посвящена задаче гибридной сборки. В начале главы сформулирована задача и приведено краткое описание основных применяемых подходов. Далее излагается алгоритм hybгidSPAdes и проводится оценка вычислительной сложности его частей. В следующем разделе представлены результаты hybгidSPAdes на разных наборах данных и проведено сравнение с альтернативными методами. В конце главы кратко описаны направления для дальнейшего развития приведенного алгоритма. Данная глава основана на материалах работы [136].

Третья глава посвящена частному случаю сборки генома плазмид. В начале главы описаны ранее применяемые методы для поиска и лучшей сборки плазмидных последовательностей. Далее изложены алгоритмы plasmidSPAdes и metaplasmidSPAdes для сборки плазмид в данных секвенирования изолированных бактерий и метагеномов соответственно. Эта глава основана на работах [138] и [104]. В заключении приводятся некоторые примеры применения разработанных алгоритмов и программных модулей, и показывается значимость разработанных методов. Также в заключении перечисляются возможности развития методов, описанных в данной работе, как потенциальные, так и уже реализованные.

Глава 1. Введение в задачу сборки генома и геномный сборщик

SPAdes

1.1 Геном и ДНК

Носителем наследственной информации у большинства (за исключением части вирусов) организмов являются молекулы дезоксирибонуклеиновой кислоты (ДНК). Эти молекулы являются полимерами и состоят из повторяющихся мономеров — так называемых нуклеотидов. Каждый нуклеотид состоит из сахара, фосфатной группы, и одного из четырех азотистых оснований (аденин, цитозин, гуанин и тимин). Также общепринятым является обозначение по первой букве английского названия соответствующего основания —А для аденина, C для цитозина, G для гуанина и T для тимина. Соответственно, последовательность в ДНК-цепи можно представлять строкой над алфавитом A,C,G,T. Обычно ДНК существует в форме двух противоположно направленных комплементарных цепочек, связанных друг с другом водородными связями. При этом, каждому нуклеотиду в одной цепи противостоит один нуклеотид строго определенного вида — аденину тимин, а цитозину гуанин. Получение геномной последовательности —секвенирование генома — является отправной точкой для многих современных биологических исследований.

1.2 Технологии секвенирования

Все актуальные методы получения генома новых организмов основаны на чтении небольших участков генома, так называемых чтений (англ reads) и дальнейшей их сборке (англ. assembly) в более длинные последовательности, так называемые контиги (англ. contigs), соответствующие более длинным фрагментам исходной последовательности нуклеотидов в молекуле ДНК. В лучшем случае каждой молекуле ДНК в геноме соответствует один контиг, но для большинства видов этого сложно достичь. Первым полным секвенированным геномом является геном бактериофага Phi X174 [92]. Однако началом эпохи

массового геномного секвенирования считают [86] появление метода дробовика (англ. shotgun sequencing), [82]. В данном методе множественные копии генома случайным образом нарезаются на фрагменты. Секвенатор используется для того, чтоб автоматически считывать префикс каждого такого фрагмента. Метод дробовика был модифицирован в статье [126]. В этой модификации предлагается использовать только фрагменты одного размера, и для каждого такого фрагмента считывать и префикс и суффикс (точнее, префикс реверс-комплементарной последовательности). Этот метод был массово использован компанией Celera genomics для секвенирования геномов дрозофилы [142] и, позднее, человека [124]. Секвенирование по Сэнгеру давало относительно длинные (до 900 нуклеотидов) и корректные чтения, однако его стоимость была крайне высока. Следующее поколение секвенаторов — секвенаторы второго поколения или NGS (англ. Next-generation sequencing) — радикально удешевило стоимость и, соответственно, увеличило количество обрабатываемых прочтений. Однако при этом длина считываемых префиксов гораздо меньше чем при секвенировании по Сэнгеру (начиная от 35 нуклеотидов и до 300). Наибольшую популярность получили секвенаторы фирмы Solexa (позднее Illumina). Последней популярной на настоящий момент группой технологий являются секвенаторы так называемого третьего поколения, позволяющие считывать длинные последовательности (десятки тысяч нуклеотидов). Минусом этих технологий является большое количество ошибок. Чаще всего из секвенаторов третьего поколения используются секвенаторы фирм Pacific Bioscience и Oxford Nanopore.

Помимо технологий секвенирования задачи сборки отличаются и по типу входных данных. Наиболее типичный случай — секвенирование колонии бактерий или ткани многоклеточного организма. В таком случае нет проблемы получить необходимое количество ДНК. Однако, согласно [62; 117] более 99% видов бактерий в настоящее время невозможно культивировать. В тканях многоклеточных организмов последовательность ДНК может в разных клетках отличаться в раковых опухолях. Решением этой проблемы может служить технология полногеномной амплификации, называемая апмлификацией со множественным замещением цепи (англ. Multiple displacement amplification), обычно сокращаемая как MDA, позволяющая получать достаточное количество ДНК из одной клетки [72; 85; 107]. Однако, в результате этой применения этой технологии геном оказывается покрыт чтениями крайне неравномерно, что приводит к усложнению алгоритмической задачи сборки. Так же, в случае бактерий,

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

1.3 Методы сборки de novo

Первый собранный геном (вируса Phi X174, длиной 5.4кб) был собран вручную [92]. Однако довольно быстро стало понятно, что задача сборки генома может быть автоматизирована и это значительно ускорит и удешевит процесс. Первые программы для сборки генома [67; 98] использовали подход OLC (англ. Overlap layout consensus, перекрытие- расположение- консенсус), состоящий из трех базовых шагов:

— Поиск приближенных (с заданной точностью) перекрытий между парами чтений.

— Применение найденных перекрытий для определения взаимного расположения чтений.

— Определение консенсусной последовательности чтений покрывающих один и тот же участок генома.

Развитие технологий секвенирования NGS привело к активному использованию алгоритмов основывающихся на графах де Брюйна [61; 100]. Этот подход использует только точные перекрытия между чтениями небольшой фиксированной длины к (так называемые к-меры). Большинство сборщиков для данных NGS основано именно на этом подходе [2; 16; 30; 38; 54; 60; 110; 118; 127; 130]. Геномный сборщик SPAdes также использует графы де Брюйна.

Появление секвенаторов третьего поколения привело к модификации старых и созданию новых сборщиков, основанных на подходе OLC [9; 19; 59;75; 102]. Основное отличие от предыдущих OLC сборщиков заключается в модификации шага выравнивания, с учетом высокой доли ошибок в чтениях третьего поколения.

1.4 Краткое изложение алгоритма работы геномного сборщика

ВРЛаеэ

Геномный сборщик SPAdes был разработан для сборки геномов бактерий, секвенированных как с помощью технологии MDA, так и обычных бактериальных колоний, с помощью технологий NGS. Однако из-за его модульной структуры SPAdes легко модифицируется для работы с другими типами данных [8; 11; 14;81;84; 104; 112; 131; 136-138; 140]. Некоторые из этих модификаций ( [104; 136; 138]) будут подробно рассмотрены во второй и третьей главе данной работы.

1.4.1 Общая структура сборщика SPAdes

Геномный сборщик SPAdes состоит из четырех больших модулей.

— BayesHammeг — модуль используемый для предварительного исправления ошибок секвенирования в чтениях [90].

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

— Модуль exSPAndeг, предназначенный для построения контигов из ре-бёр графа с использованием дополнительной связывающей информации (например, информации о прикладывании к графу парных чтений).

— Модуль финальной коррекции ошибок сборки (полишинга) MismatchCoггection.

Предварительная коррекция ошибок в чтениях нужна для уменьшения размеров потребляемой памяти и ускорения работы ядра SPAdes. При необходимости BayesHammeг может быть заменен на альтернативные методы предварительной коррекции ошибок, как разработанные специально для SPAdes [66], так и внешние [17; 68; 80].

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

аналогичные по функциональности инструменты [42; 103] или отключен; также его можно использовать отдельно от 8РЛ(1е8 для полировки сборок полученных другими способами (например по референсу).

Поскольку и БауеэЫатшег и М1вта1сЬСоггесМоп являются опциональными модулями и в инструментах описанных в главах 2 и 3 могут либо использоваться без изменений, либо не использоваться вообще, далее в этой главе будут более подробно изложены детали работы только ядра сборщика и ехБРЛп(ег.

Мы будем пользоваться следующими обозначениями:

— 1 —длина строки 5

— 5[п] —символ номер п(при нумерации с 0) строки Б

— Б[х..у] —подстрока строки Б, начинающаяся на символе с номером х и заканчивающаяся на символе с номером у

— Б • Т —конкатенация строк Б и Т

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

Граф де Брюйна может быть определен следующим образом: назовем графом де Брюйна с параметром к ориентированный граф С = (V, Е), дополненный строковыми метками на вершинах /(V) и ребрах д(Е), и обладающий следующими свойствами:

— Для всех вершин у Е V, |/(г>)| = к,

— Для всех ребер е Е Е, |^(е)| = к + 1,

— Для всех ребер е = (у1,у2) Е Е, /(г^) = д(е)[0..к — 1] и /(у2) = д(е)[1..к]. Строковые метки вершин размера к из определения выше принято называть ^-мерами. Следует заметить, что в некоторых статьях (например [100]) параметром к обозначают длины меток на ребрах (а к — 1 —на вершинах).

Граф де Брюйна (С(У,Е),/(V),д(Е),к) соответствует множеству строк Я, если /(V) совпадает со множеством всех различных подстрок длины к всех строк г Е Я, а множество д(Е) совпадает со множеством подстрок длины к + 1 всех строк г Е Я. Очевидно, что по данному множеству строк Я соответствующий граф де Брюйна может быть явно построен. В случае задачи геномной сборки, множеством Я является множество всех чтений полученных с секвенатора.

Назовем однозначными такие вершины в ориентированном графе, что их исходящая и входящая степени (т.е. число входящих и исходящих ребер) равны 1, а неоднозначными —все остальные. Для каждого пути р = е1,е2 ... en в G определим функцию сжатия меток пути как конкатенацию первых символов всех ребер кроме последнего и всей метки последнего ребра (label (р) = g(e1)[0}g(e2)[0]...g(en—1)[0]g(en)) Назовем сжимаемым путь, начало и конец которого лежат в неоднозначных вершинах, а все промежуточные вершины — однозначные. По данному графу де Брюйна (G(V,E),f (V),g(E),к) можно построить новый граф G' = (V', Е' ) где V' это множество неоднозначных вершин G, а ребра Е' соответствуют всем сжимаемым путям в G. Метки на вершинах остаются теми же. Функция меток на ребрах нового графа label(Е') получаются сжатием меток соответствующих путей в оригинальном графе де Брюйна. Данный граф называется сжатым графом де Брюйна. Аналогично графу де Брюйна, его свойства можно описать следующим образом:

- Для всех вершин v Е V', \f (v )| = к

— Для всех ребер е Е Е', \label(e)\ > к + 1

- Для всех ребер е = (v1,v2) Е E',f(v1) = label(e)[0..k — 1] и f(v2) = label(e)[l — к + 1..1 — 1] где I = \label(e)\

— Для всех вершин v Е V', v неоднозначна.

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

1.4.3 Удаление ошибочных ребер

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

a) Тупики —ребра ведущие в или из висячей вершины

b) Пузыри —ошибочные ребра имеющие "похожий"альтернативный путь

^ Химеры —ребра соединяющие далекие участки генома.

Рисунок 1.1 — Основные виды ошибочных ребёр, определяемые ЭРАсЛез. Слева изображен пример тупикового ребра, посередине пузырь, справа химера. Во всех случаях ошибочное

ребро показано пунктиром.

На иллюстрации 1.1 можно увидеть простые примеры для этих типов ребёр.

Во всех трех случаях ЗРАсЛев удаляет только относительно короткие ребра. Ребра типа а и Ь обычно возникают из-за неболвших ошибок секвенатора. Если ошибка (однонуклеотидная замена или маленвкая вставка/удаление) оказвша-ются на конце чтения — чаще всего это приводит к появлению к-меров для которых отсутствует продолжение, т.е. тупиковых ребер. Ошибка посередине чтения может привести к появлению пузвфя. Также возможно появление пузырей из-за присутствия в геноме несколвких неточных копий повторной последовательности, неболвших вариаций в геноме секвенированной колонии бактерий или наличия в метагеноме близких штаммов одного вида. Химерические ребра чаще всего возникают из-за специфики процесса секвенирования по одной клетке. Также в случае секвенирования даннвк с болвшим и равномерным покрв1тием 8РАс1е8 рассматривает как ошибочные относителвно короткие ребра низкого покрв1тия вне зависимости от их расположения в графе. Все такие ребра итеративно удаляются из сжатого графа де Брюйна. После каждого удаления происходит процесс сжатия однозначных вершин, описанный в предыдущем разделе. Детали алгоритмов поиска и удаления ошибочных ребер, а также их практической реализации, можно найти в статвях [12; 93; 137].

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

1.4.4 Итеративное построение графа сборки

Описанные в предыдущем подразделе алгоритмв1 позволяют избавитвся от ребер полученнвгх из ошибочных чтений. Другой проблемой сборки явля-

ются так называемые разрывы в покрытии — отсутствие &-меров данного размера во входных чтениях. Эта проблема часто возникает при сборке данных с неравномерным покрытием, например, полученных с помощью технологии MDA, или в случае секвенирования метагеномов. При этом, при фиксированном наборе чтений чем больше значение параметра к, тем больше геномных &-меров будет отсутствовать в итоговом графе. Однако, за счет большего количества повторных участков малого размера, малое значение к значительно усложняет граф [60], а значит и разрешение повторов и скэффолдинг. SPAdes старается использовать преимущества и малых и больших значений к. Для этого шаги описанные в предыдущих двух подразделов применяются итеративно для разных значений к. Сначала граф строится с использованием относительно небольшого к. Далее в графе удаляются ошибочные ребра, а однозначные пути сжимаются, что позволяет собрать в один контиг часть участков малого покрытия. После этого ребра полученного графа сборки добавляются к исходным чтениям. Затем процесс построения и упрощения повторяется для больших значений к. Последовательность ребра графа сборки с предыдущей итерации может содержать &-меры отсутствующие в чтениях, т.е. позволяющие закрыть разрывы в покрытии.

SPAdes применяет разные наборы длин &-меров в зависимости от длин исходных чтений и типа входных данных. Эмпирически установлено, что сборщики основанные на графах де Брюйна на данных секвенирования изолятов обычно хорошо работают при значении параметра к несколько превышающем половину длины чтения. Поэтому по умолчанию, для чтений длины 100 нуклеотидов (а также для метагеномных данных и для данных секвенирования MDA вне зависимости от длин чтений) используется к из набора {21,33,55}; для чтений длины 150 —{21,33,55,77}, а для чтений длины 250 и более — {21,33,55,77,127}. Также набор длин используемых &-меров можно указать вручную. Величина параметра к сильно влияет на сложность итогового графа де Брюй-на. Оптимальное значение зависит от длины чтения, глубины секвенирования и равномерности покрытия генома чтениями. Задача оптимального выбора к рассмотрена, например, в статьях [23; 57]. Однако для итеративного построения графа сборки задача оптимального подбора к изучена недостаточно хорошо. В то же время, применение алгоритма разрешения повторов, описанного в разделе 1.4.5, позволяет нивелировать возможную неоптимальность подбора к.

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

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

1. ALE: a generic assembly likelihood evaluation framework for assessing the accuracy of genome and metagenome assemblies / Scott C Clark, Rob Egan, Peter I Frazier, Zhong Wang // Bioinformatics. — 2013. — Vol. 29, no. 4. — Pp. 435-443.

2. 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.

3. Accurate circular consensus long-read sequencing improves variant detection and assembly of a human genome / Aaron M Wenger, Paul Peluso, William J Rowell et al. // Nature biotechnology. — 2019. — Vol. 37, no. 10. — Pp. 1155-1162.

4. Amir Amihood, Lewenstein Moshe, Lewenstein Noa. Pattern matching in hypertext // Journal of Algorithms. — 2000. — Vol. 35, no. 1. — Pp. 82-99.

5. Analysis of metagenome-assembled viral genomes from the human gut reveals diverse putative CrAss-like phages with unique genomic features / Na-talya Yutin, Sean Benler, Sergei A Shmakov et al. // Nature communications.

— 2021. — Vol. 12, no. 1. — Pp. 1-11.

6. Antimicrobial resistance prediction and phylogenetic analysis of Neisseria gon-orrhoeae isolates using the Oxford Nanopore MinlON sequencer / Daniel Gol-parian, Valentina Dona, Leonor Sanchez-Buso et al. // Scientific reports. — 2018. — Vol. 8, no. 1. — Pp. 1-12.

7. 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.

8. 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.

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

10. Assessment of metagenomic assembly using simulated next generation sequencing data / Daniel R Mende, Alison S Waller, Shinichi Sunagawa et al. // PloS one. — 2012. — Vol. 7, no. 2. — P. e31386.

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

12. Bankevich Anton et al. SPAdes: A New Genome Assembly Algorithm and Its Applications to Single-Cell Sequencing. // Journal of Computational Biology.

— 2012. — Vol. 19. — Pp. 455-477. http://dx.doi.org/10.1089/cmb.2012. 0021.

13. Basic local alignment search tool / Stephen F Altschul, Warren Gish, Webb Miller et al. // Journal of molecular biology. — 1990. — Vol. 215, no. 3. — Pp. 403-410.

14. BiosyntheticSPAdes: reconstructing biosynthetic gene clusters from assembly graphs / Dmitry Meleshko, Hosein Mohimani, Vittorio Tracanna et al. // Genome research. — 2019. — Vol. 29, no. 8. — Pp. 1352-1362.

15. Blake Kevin S, Choi JooHee, Dantas Gautam. Approaches for characterizing and tracking hospital-associated multidrug-resistant bacteria // Cellular and Molecular Life Sciences. — 2021. — Pp. 1-22.

16. 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. http://dx.doi.org/10.1089/cmb.2009.0238.

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

— Pp. 2114-2120.

18. 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.

19. 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.

20. Cerulean: a hybrid assembly using high throughput short and long reads / Viraj Deshpande, Eric DK Fung, Son Pham, Vineet Bafna // Algorithms in Bioinformatics. — Springer, 2013. — Pp. 349-363.

21. Chaisson Mark J, Tesler Glenn. Mapping single molecule sequencing reads using basic local alignment with successive refinement (BLASR): application and theory // BMC bioinformatics. — 2012. — Vol. 13, no. 1. — P. 238.

22. Characteristics of ARG-carrying plasmidome in the cultivable microbial community from wastewater treatment system under high oxytetracycline concentration / Yanhong Shi, Hong Zhang, Zhe Tian et al. // Applied microbiology and biotechnology. — 2018. — Vol. 102, no. 4. — Pp. 1847-1858.

23. Chikhi Rayan, Medvedev Paul. Informed and automated k-mer size selection for genome assembly // Bioinformatics. — 2014. — Vol. 30, no. 1. — Pp. 31-37.

24. Clarridge Jill E. Impact of 16S rRNA gene sequence analysis for identification of bacteria on clinical microbiology and infectious diseases // Clinical microbiology reviews. — 2004. — Vol. 17, no. 4. — Pp. 840-862.

25. Comparative metagenomic and rRNA microbial diversity characterization using archaeal and bacterial synthetic communities / Migun Shakya, Christopher Quince, James H Campbell et al. // Environmental microbiology. — 2013. — Vol. 15, no. 6. — Pp. 1882-1899.

26. Complex archaea that bridge the gap between prokaryotes and eukaryotes / Anja Spang, Jimmy H Saw, Steffen L J0rgensen et al. // Nature. — 2015. — Vol. 521, no. 7551. — Pp. 173-179.

27. Critical assessment of metagenome interpretation—a benchmark of metage-nomics software / Alexander Sczyrba, Peter Hofmann, Peter Belmann et al. // Nature methods. — 2017. — Vol. 14, no. 11. — Pp. 1063-1071.

28. Critical evaluation of short, long, and hybrid assembly for contextual analysis of antibiotic resistance genes in complex environmental metagenomes / Connor L Brown, Ishi M Keenum, Dongjuan Dai et al. // Scientific reports. — 2021. — Vol. 11, no. 1. — Pp. 1-12.

29. Cultivation and functional characterization of 79 planctomycetes uncovers their unique biology / Sandra Wiegand, Mareike Jogler, Christian Boedeker et al. // Nature microbiology. — 2020. — Vol. 5, no. 1. — Pp. 126-140.

30. 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.

31. De novo likelihood-based measures for comparing metagenomic assemblies / Christopher M Hill, Irina Astrovskaya, Howard Huang et al. // 2013 IEEE International Conference on Bioinformatics and Biomedicine / IEEE. — 2013.

— Pp. 94-98.

32. De novo yeast genome assemblies from MinION, PacBio and MiSeq platforms / Francesca Giordano, Louise Aigrain, Michael A Quail et al. // Scientific reports. — 2017. — Vol. 7, no. 1. — Pp. 1-10.

33. 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.

34. Dijkstra Edsger W. A note on two problems in connexion with graphs // Numerische mathematik. — 1959. — Vol. 1, no. 1. — Pp. 269-271.

35. Draft genome sequencing of Vibrio cholerae O1 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.

36. Dynamics and stabilization of the human gut microbiome during the first year of life / Fredrik Bäckhed, Josefine Roswall, Yangqing Peng et al. // Cell host & microbe. — 2015. — Vol. 17, no. 5. — Pp. 690-703.

37. Ebola virus disease in the Democratic Republic of Congo / Gael D Maganga, Jimmy Kapetshi, Nicolas Berthet et al. // New England Journal of Medicine.

— 2014. — Vol. 371, no. 22. — Pp. 2083-2091.

38. Efficient de novo assembly of highly heterozygous genomes from whole-genome shotgun short reads / Rei Kajitani, Kouta Toshimoto, Hideki Noguchi et al. // Genome research. — 2014. — Vol. 24, no. 8. — Pp. 1384-1395.

39. 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. http://dx.doi.org/10.1093/ bioinformatics/btu266.

40. Extending rnaSPAdes functionality for hybrid transcriptome assembly / An-drey D Prjibelski, Giuseppe D Puglia, Dmitry Antipov et al. // BMC bioinformatics. — 2020. — Vol. 21, no. 12. — Pp. 1-9.

41. Facile recovery of individual high-molecular-weight, low-copy-number natural plasmids for genomic sequencing / Laura E Williams, Chris Detter, Kerrie Barry et al. // Applied and environmental microbiology. — 2006. — Vol. 72, no. 7.

— Pp. 4899-4906.

42. Fast and accurate de novo genome assembly from long uncorrected reads / Robert Vaser, Ivan Sovic, Niranjan Nagarajan, Mile Sikic // Genome research.

— 2017. — Vol. 27, no. 5. — Pp. 737-746.

43. Fast and accurate de novo genome assembly from long uncorrected reads / Robert Vaser, Ivan Sovic, Niranjan Nagarajan, Mile Sikic // Genome research.

— 2017. — Vol. 27, no. 5. — Pp. 737-746.

44. Fast and scalable minimal perfect hashing for massive key sets / Antoine Limasset, Guillaume Rizk, Rayan Chikhi, Pierre Peterlongo // arXiv preprint arXw:1702.0315l — 2017.

45. Friedman Jerome, Hastie Trevor, Tibshirani Robert. The elements of statistical learning. — Springer series in statistics New York, 2001. — Vol. 1.

46. Genome analysis of clinical multilocus sequence Type 11 Klebsiella pneumoniae from China / Ning Dong, Rong Zhang, Lizhang Liu et al. // Microbial genomics. — 2018. — Vol. 4, no. 2.

47. Genomic and phenotypic diversity of carbapenemase-producing enterobacteri-aceae isolates from bacteremia in china: A multicenter epidemiological, microbiological, and genetic study / Beiwen Zheng, Hao Xu, Lihua Guo et al. // Engineering. — 2020.

48. Genomic history of the seventh pandemic of cholera in Africa / Francois-Xavier Weill, Daryl Domman, Elisabeth Njamkepo et al. // Science.

— 2017. — Vol. 358, no. 6364. — Pp. 785-789.

49. Gr0nlund Hugo, Gerdes Kenn. Toxin-antitoxin systems homologous with relBE of Escherichia coli plasmid P307 are ubiquitous in prokaryotes // Journal of molecular biology. — 1999. — Vol. 285, no. 4. — Pp. 1401-1415.

50. Gunge N, Murata K, Sakaguchi K. Transformation of Saccharomyces cerevisi-ae with linear DNA killer plasmids from Kluyveromyces lactis. // Journal of bacteriology. — 1982. — Vol. 151, no. 1. — Pp. 462-464.

51. Gurevich Alexey et al. QUAST: quality assessment tool for genome assemblies // Bioinformatics. — 2013. — Vol. 29. — Pp. 1072-1075. http://bioinformatics.oxfordjournals.org/content/early/2013/03/ 09/bioinformatics.btt086.abstract.

52. HASLR: Fast hybrid assembly of long reads / Ehsan Haghshenas, Hossein As-ghari, Jens Stoye et al. // ¡science. — 2020. — Vol. 23, no. 8. — P. 101389.

53. Hayes Finbarr. Toxins-antitoxins: plasmid maintenance, programmed cell death, and cell cycle arrest // Science. — 2003. — Vol. 301, no. 5639. — Pp. 1496-1499.

54. High-quality draft assemblies of mammalian genomes from massively parallel sequence data / Sante Gnerre, Iain MacCallum, Dariusz Przybylski et al. // Proceedings of the National Academy of Sciences. — 2011. — Vol. 108, no. 4.

— Pp. 1513-1518.

55. High-quality draft assemblies of mammalian genomes from massively parallel sequence data / S. Gnerre, I. Maccallum, D. Przybylski et al. // Proceedings of the National Academy of Sciences. — 2011. — Vol. 108. — Pp. 1513-1518.

56. Hundreds of circular novel plasmids and DNA elements identified in a rat cecum metamobilome / Tue Sparholt J0rgensen, Zhuofei Xu, Martin Asser Hansen et al. // PloS one. — 2014. — Vol. 9, no. 2.

57. HyDA-Vista: towards optimal guided selection of k-mer size for sequence assembly / Basir Shariat, Narjes Sadat Movahedi, Hamidreza Chitsaz, Christina Boucher // BMC genomics. — 2014. — Vol. 15, no. 10. — P. S9.

58. Hybrid assembly of the large and highly repetitive genome of Aegilops tauschii, a progenitor of bread wheat, with the MaSuRCA mega-reads algorithm / Alek-sey V Zimin, Daniela Puiu, Ming-Cheng Luo et al. // Genome research. — 2017. — Vol. 27, no. 5. — Pp. 787-792.

59. Hybrid error correction and de novo assembly of single-molecule sequencing reads / Sergey Koren, Michael C Schatz, Brian P Walenz et al. // Nature biotechnology. — 2012. — Vol. 30, no. 7. — P. 693.

60. 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. http: //www.ncbi.nlm.nih.gov/pubmed/22495754.

61. Idury R.M., Waterman M.S. A new algorithm for DNA sequence assembly // Journal of Computational Biology. — 1995. — Vol. 2. — Pp. 291-306.

62. Impact of single-cell genomics and metagenomics on the emerging view of ex-tremophile "microbial dark matter" / Brian P Hedlund, Jeremy A Dodsworth, Senthil K Murugapiran et al. // Extremophiles. — 2014. — Vol. 18, no. 5. — Pp. 865-875.

63. In silico detection and typing of plasmids using PlasmidFinder and plas-mid multilocus sequence typing / Alessandra Carattoli, Ea Zankari, Aurora García-Fernandez et al. // Antimicrobial agents and chemotherapy. — 2014.

— Vol. 58, no. 7. — Pp. 3895-3903.

64. Insights into the bovine rumen plasmidome / Aya Brown Kav, Goor Sasson, Elie Jami et al. // Proceedings of the National Academy of Sciences. — 2012.

— Vol. 109, no. 14. — Pp. 5452-5457.

65. Introduction to Algorithms / Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, Clifford Stein. — MIT Press, 2001.

66. IonHammer: Homopolymer-Space Hamming Clustering for IonTorrent Read Error Correction / Vasily Ershov, Artem Tarasov, Alla Lapidus, Anton Ko-robeynikov // Journal of Computational Biology. — 2019. — Vol. 26, no. 2. — Pp. 124-127.

67. Kececioglu John D, Myers Eugene W. Combinatorial algorithms for DNA sequence assembly // Algorithmica. — 1995. — Vol. 13, no. 1-2. — P. 7.

68. Kelley David R, Schatz Michael C, Salzberg Steven L. Quake: quality-aware detection and correction of sequencing errors // Genome biology. — 2010. — Vol. 11, no. 11. — P. R116.

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

70. Koonin Eugene V, Makarova Kira S, Aravind L. Horizontal gene transfer in prokaryotes: quantification and classification // Annual Reviews in Microbiology. — 2001. — Vol. 55, no. 1. — Pp. 709-742.

71. Krawczyk Pawel S, Lipinski Leszek, Dziembowski Andrzej. PlasFlow: predicting plasmid sequences in metagenomic data using genome signatures // Nucleic acids research. — 2018. — Vol. 46, no. 6. — Pp. e35-e35.

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

73. Levenshtein Vladimir I. Binary codes capable of correcting deletions, insertions, and reversals // Soviet physics doklady. — Vol. 10. — 1966. — Pp. 707-710.

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

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

76. Li Heng. Minimap2: pairwise alignment for nucleotide sequences // Bioinfor-matics. — 2018. — Vol. 34, no. 18. — Pp. 3094-3100.

77. Li Heng, Durbin Richard. Fast and accurate long-read alignment with Burrows-Wheeler transform // Bioinformatics. — 2010. — Vol. 26, no. 5. — Pp. 589-595.

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

79. Margais Guillaume, Kingsford Carl. A fast, lock-free approach for efficient parallel counting of occurrences of k-mers // Bioinformatics. — 2011. — Vol. 27, no. 6. — Pp. 764-770.

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

81. Meleshko Dmitrii, Korobeynikov Anton. coronaSPAdes: from biosynthetic gene clusters to coronaviral assemblies // bioRxiv. — 2020.

82. Messing Joachim, Crea Roberto, Seeburg Peter H. A system for shotgun DNA sequencing // Nucleic acids research. — 1981. — Vol. 9, no. 2. — Pp. 309-321.

83. MetaSim—a sequencing simulator for genomics and metagenomics / Daniel C Richter, Felix Ott, Alexander F Auch et al. // PloS one. — 2008. — Vol. 3, no. 10. — P. e3373.

84. Metaviral SPAdes: assembly of viruses from metagenomic data / Dmitry An-tipov, Mikhail Raiko, Alla Lapidus, Pavel A Pevzner // Bioinformatics. — 2020. — Vol. 36, no. 14. — Pp. 4126-4129.

85. 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.

86. Myers Jr Eugene W. A history of DNA sequence assembly // It-Information Technology. — 2016. — Vol. 58, no. 3. — Pp. 126-132.

87. Needleman SB. Needleman-Wunsch algorithm for sequence similarity searches // J Mol Biol. — 1970. — Vol. 48. — Pp. 443-453.

88. Needleman Saul B, Wunsch Christian D. A general method applicable to the search for similarities in the amino acid sequence of two proteins // Journal of molecular biology. — 1970. — Vol. 48, no. 3. — Pp. 443-453.

89. Next generation sequencing data of a defined microbial mock community / Esther Singer, Bill Andreopoulos, Robert M Bowers et al. // Scientific data.

— 2016. — Vol. 3, no. 1. — Pp. 1-8.

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

91. Nonhybrid, finished microbial genome assemblies from long-read SMRT sequencing data / Chen-Shan Chin, David H Alexander, Patrick Marks et al. // Nature Methods. — 2013. — Vol. 10, no. 6. — Pp. 563-569.

92. Nucleotide sequence of bacteriophage ^X174 DNA / Frederick Sanger, Gilian M Air, Bart G Barrell et al. // nature. — 1977. — Vol. 265, no. 5596.

— Pp. 687-695.

93. 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.

94. Ogura Teru, Hiraga Sota. Mini-F plasmid genes that couple host cell division to plasmid proliferation // Proceedings of the National Academy of Sciences.

— 1983. — Vol. 80, no. 15. — Pp. 4784-4788.

95. On the (im) possibility of reconstructing plasmids from whole-genome short-read sequencing data / Sergio Arredondo-Alonso, Rob J Willems, Willem van Schaik, Anita C Schiirch // Microbial genomics. — 2017. — Vol. 3, no. 10.

96. Ordered restriction maps of Saccharomyces cerevisiae chromosomes constructed by optical mapping / David C Schwartz, Xiaojun Li, Luis I Hernandez et al. // Science. — 1993. — Vol. 262, no. 5130. — Pp. 110-114.

97. PERGA: a paired-end read guided de novo assembler for extending contigs using SVM and look ahead approach / Xiao Zhu, Henry CM Leung, Francis YL Chin et al. // PloS one. — 2014. — Vol. 9, no. 12.

98. Peltola H, Soderlund H, Ukkonen E. SEQAID: a DNA sequence assembling program based on a mathematical model. // Nucleic acids research. — 1984.

— Vol. 12, no. 1 Pt 1. — Pp. 307-321.

99. Pemberton JM. Degradative plasmids // International review of cytology. — Elsevier, 1983. — Vol. 84. — Pp. 155-183.

100. Pevzner Pavel A., Tang Haixu, Waterman Michael S. An Eulerian path approach to DNA fragment assembly // Proceedings of the National Academy of Sciences. — 2001. — Vol. 98. — Pp. 9748-9753. http://dx.doi.org/10. 1073/pnas.171285098.

101. The Pfam protein families database: towards a more sustainable future / Robert D Finn, Penelope Coggill, Ruth Y Eberhardt et al. // Nucleic acids research. — 2016. — Vol. 44, no. D1. — Pp. D279-D285.

102. Phased diploid genome assembly with single-molecule real-time sequencing / Chen-Shan Chin, Paul Peluso, Fritz J Sedlazeck et al. // Nature methods. — 2016. — Vol. 13, no. 12. — P. 1050.

103. Pilon: an integrated tool for comprehensive microbial variant detection and genome assembly improvement / Bruce J Walker, Thomas Abeel, Ter-rance Shea et al. // PloS one. — 2014. — Vol. 9, no. 11.

104. Plasmid detection and assembly in genomic and metagenomic data sets / Dmitry Antipov, Mikhail Raiko, Alla Lapidus, Pavel A Pevzner // Genome research.

— 2019. — Vol. 29, no. 6. — Pp. 961-968.

105. Plasmid flux in Escherichia coli ST131 sublineages, analyzed by plasmid constellation network (PLACNET), a new method for plasmid reconstruction from whole genome sequences / Val F Lanza, Maria de Toro, M Pilar Gar-cillan-Barcia et al. // PLoS Genetics. — 2014. — Vol. 10, no. 12. — P. e1004766.

106. Prodigal: prokaryotic gene recognition and translation initiation site identification / Doug Hyatt, Gwo-Liang Chen, Philip F LoCascio et al. // BMC bioinformatics. — 2010. — Vol. 11, no. 1. — P. 119.

107. Rapid amplification of plasmid and phage DNA using phi29 DNA polymerase and multiply-primed rolling circle amplification / Frank B Dean, John R Nel-

son, Theresa L Giesler, Roger S Lasken // Genome research. — 2001. — Vol. 11, no. 6. — Pp. 1095-1099.

108. Recycler: an algorithm for detecting plasmids from de novo assembly graphs / Roye Rozov, Aya Brown Kav, David Bogumil et al. // Bioinformatics. — 2017. — Vol. 33, no. 4. — Pp. 475-482.

109. Reducing assembly complexity of microbial genomes with single-molecule sequencing / Sergey Koren, Gregory P Harhay, Timothy PL Smith et al. // Genome biology. — 2013. — Vol. 14, no. 9. — P. R101.

110. SOAPdenovo2: an empirically improved memory-efficient short-read de novo assembler / Ruibang Luo, Binghang Liu, Yinlong Xie et al. // Gigascience. — 2012. — Vol. 1, no. 1. — Pp. 2047-217X.

111. SPAligner: alignment of long diverged molecular sequences to assembly graphs / Tatiana Dvorkina, Dmitry Antipov, Anton Korobeynikov, Sergey Nurk // BioRxiv. — 2019. — P. 744755.

112. Safonova Yana, Bankevich Anton, Pevzner Pavel A. dipSPAdes: assembler for highly polymorphic diploid genomes // Journal of Computational Biology. — 2015. — Vol. 22, no. 6. — Pp. 528-545.

113. Sequence and cultivation study of Muribaculaceae reveals novel species, host preference, and functional potential of this yet undescribed family / Ilias Lagk-ouvardos, Till R Lesker, Thomas CA Hitch et al. // Microbiome. — 2019. — Vol. 7, no. 1. — Pp. 1-15.

114. Shintani Masaki, Sanchez Zoe K, Kimbara Kazuhide. Genomics of microbial plasmids: classification and identification based on replication and transfer systems and host taxonomy // Frontiers in microbiology. — 2015. — Vol. 6. — P. 242.

115. Shotgun metagenomics reveals a wide array of antibiotic resistance genes and mobile elements in a polluted lake in India / Johan Bengtsson-Palme, Fredrik Boulund, Jerker Fick et al. // Frontiers in microbiology. — 2014. — Vol. 5. — P. 648.

116. Smith Temple F, Waterman Michael S. Identification of common molecular subsequences // Journal of molecular biology. — 1981. — Vol. 147, no. 1. — Pp. 195-197.

117. Solden Lindsey, Lloyd Karen, Wrighton Kelly. The bright side of microbial dark matter: lessons learned from the uncultivated majority // Current opinion in microbiology. — 2016. — Vol. 31. — Pp. 217-226.

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

119. Staden Rodger. A strategy of DNA sequencing employing computer programs // Nucleic acids research. — 1979. — Vol. 6, no. 7. — Pp. 2601-2610.

120. Structure, function and diversity of the healthy human microbiome / Curtis Huttenhower, Dirk Gevers, Rob Knight et al. // nature. — 2012. — Vol. 486, no. 7402. — P. 207.

121. 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.

122. 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. e1005595.

123. Use of simulated data sets to evaluate the fidelity of metagenomic processing methods / Konstantinos Mavromatis, Natalia Ivanova, Kerrie Barry et al. // Nature methods. — 2007. — Vol. 4, no. 6. — Pp. 495-500.

124. Venter J Craig et al. The sequence of the human genome // Science. — 2001. — no. 5507. — Pp. 1304-1351.

125. Virulence genes in isolates of Klebsiella pneumoniae from the UK during 2016, including among carbapenemase gene-positive hypervirulent K1-ST23 and 'non-hypervirulent'types ST147, ST15 and ST383 / Jane F Turton, Zoe Payne, Amy Coward et al. // Journal of medical microbiology. — 2018. — Vol. 67, no. 1. — Pp. 118-128.

126. Weber James L, Myers Eugene W. Human whole-genome shotgun sequencing // Genome research. — 1997. — Vol. 7, no. 5. — Pp. 401-409.

127. 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. http://dx.doi.org/10,1101/gr.074492.107.

128. Zhou Fengfeng, Xu Ying. cBar: a computer program to distinguish plas-mid-derived from chromosome-derived sequence fragments in metagenomics data // Bioinformatics. — 2010. — Vol. 26, no. 16. — Pp. 2051-2052.

129. Zimin Aleksey V, Salzberg Steven L. The genome polishing tool POLCA makes fast and accurate corrections in genome assemblies // PLoS computational biology. — 2020. — Vol. 16, no. 6. — P. e1007981.

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

131. cloudSPAdes: assembly of synthetic long reads using de Bruijn graphs / Ivan Tolstoganov, Anton Bankevich, Zhoutao Chen, Pavel A Pevzner // Bioinformatics. — 2019. — Vol. 35, no. 14. — Pp. i61-i70.

132. The complete sequence of a human genome / Sergey Nurk, Sergey Koren, Arang Rhie et al. // bioRxiv. — 2021.

133. A fatal outbreak of ST11 carbapenem-resistant hypervirulent Klebsiella pneumoniae in a Chinese hospital: a molecular epidemiological study / Danxia Gu, Ning Dong, Zhiwei Zheng et al. // The Lancet infectious diseases. — 2018. — Vol. 18, no. 1. — Pp. 37-46.

134. A framework for human microbiome research / Barbara A Methe, Karen E Nelson, Mihai Pop et al. // nature. — 2012. — Vol. 486, no. 7402. — P. 215.

135. The global distribution and spread of the mobilized colistin resistance gene mcr-1 / Ruobing Wang, Lucy van Dorp, Liam P Shaw et al. // Nature communications. — 2018. — Vol. 9, no. 1. — Pp. 1-9.

136. hybridSPAdes: an algorithm for hybrid assembly of short and long reads / Dmitry Antipov, Anton Korobeynikov, Jeffrey S McLean, Pavel A Pevzner // Bioinformatics. — 2016. — Vol. 32, no. 7. — Pp. 1009-1015.

137. 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.

138. plasmidSPAdes: assembling plasmids from whole genome sequencing data / Dmitry Antipov, Nolan Hartwick, Max Shen et al. // Bioinformatics. — 2016. — Vol. 32, no. 22. — Pp. 3380-3387.

139. rnaSPAdes: a de novo transcriptome assembler and its application to RNA-Seq data / Elena Bushmanova, Dmitry Antipov, Alla Lapidus, Andrey D Prjibels-ki // GigaScience. — 2019. — Vol. 8, no. 9. — P. giz100.

140. rnaSPAdes: a de novo transcriptome assembler and its application to RNA-Seq data / Elena Bushmanova, Dmitry Antipov, Alla Lapidus, Andrey D Prjibels-ki // GigaScience. — 2019. — Vol. 8, no. 9. — P. giz100.

141. 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. e1005072.

142. 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.

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

1.1 Виды ошибочных ребёр определяемые 8РЛ(1е8............. 15

2.1 Задача заполнения промежутков в скелетном выравнивании..... 26

3.1 Распределение покрытия длинных контигов для ЕКЛ000206 ..... 39

3.2 Распределение покрытия средних и длинных контигов для ЕЯЛ000206 40

3.3 Пример работы алгоритма те1ар1азш1(8РЛ(1е8............. 52

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

1 Сравнение сборщиков на наборах данных бактерии E.coli ............31

2 Сравнение сборщиков на наборах данных бактерии E.coli с различной глубиной покрытия............................................32

3 Сравнение сборщиков на наборах данных бактерии M.ruber DSM 1279 32

4 Сравнение сборщиков на наборах данных бактерии Streptomyces PAMC26508 ................................................................33

5 Сравнение сборщиков на наборах данных TM6..........................33

6 Равномерность покрытия генома бактерий короткими чтениями ... 38

7 Детальные результаты работы plasmidSPAdes на наборах данных с известными геномами ........................... 44

8 Сравнение plasmidSPAdes со SPAdes и Recycler на наборах бактериальных данных с известным геномом .............. 45

9 Результаты plasmidSPAdes на наборах данных с неполными сборками и отсутствием аннотированных плазмид. Жирным выделены предположительные плазмиды состоящие из одного циклического ребра в графе сборки. Адаптировано из [138] ..... 46

10 Результаты сравнения инструментов для верификации плазмид ... 48

11 Результаты тестирования алгоритма metaplasmidSPAdes для

наборов данных с известными референсами .............. 53

12 Результаты тестирования алгоритма metaplasmidSPAdes для

наборов данных с неизвестными референсами ............. 54

SAINT PETERSBURG STATE UNIVERSITY

Printed as a manuscript

Dmitry Antipov

DEVELOPMENT OF ALGORITHMS FOR SPECIAL CASES OF GENOME ASSEMBLY

Scientific speciality 1.5.8. Mathematical biology, bioinformatics

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

Sciences

Translated from Russian.

Scientific advisors:

Candidate of Physico-mathematical Sciences, professor

Pavel A. Pevzner Candidate of Biological Sciences Alla L. Lapidus

Saint Petersburg — 2021

Table of contents

Стр.

Introduction......................................................................82

Chapter 1. Introduction to the genome assembly and SPAdes

genome assembler................................................87

1.1 Genome and DNA........................................................87

1.2 Sequencing methods......................................................87

1.3 De novo assembly methods..............................................89

1.4 Summary of SPAdes assembler algorithm..............................89

1.4.1 General structure of the SPAdes assembler....................90

1.4.2 Construction and compression of the de Bruijn graph .... 91

1.4.3 Deleting erroneous edges........................................92

1.4.4 Iterative construction of the assembly graph ..................93

1.4.5 Application of paired reads mapping. Summary of the exSPAnder algorithm............................................94

Chapter 2. Hybrid assembly with the hybridSPAdes algorithm ... 96

2.1 Third-generation sequencing technologies..............................96

2.2 Hybrid assembly approaches............................................97

2.3 hybridSPAdes module for hybrid assembly..............................98

2.3.1 General structure of hybridSPAdes..............................98

2.3.2 Construction of the alignments of long reads to the de

Bruijn graph......................................................98

2.3.3 Filling the missing regions of the genome in the de Bruijn

graph with long reads......................105

2.3.4 Traversing repetitive genome regions with long read

alignment information .....................105

2.4 Results..................................106

2.5 Conclusion ................................................................108

Chapter 3. Assembling and extracting plasmid sequences from

whole genome sequencing data................111

Стр.

3.1 Introduction...............................111

3.2 Existing methods............................111

3.3 Uniformity of coverage in graphs constructed from NGS data .... 113

3.4 plasmidSPAdes module for plasmid assembly.............115

3.4.1 plasmidSPAdes algorithm....................116

3.4.2 plasmidSPAdes' benchmarking.................118

3.5 plasmidVerify module for plasmid verification.............120

3.5.1 plasmidVerify algorithm ....................120

3.5.2 Benchmarking of plasmidVerify ................123

3.6 metaplasmidSPAdes algorithm for assembling plasmids from metagenomic sequencing........................124

3.6.1 Introduction...........................124

3.6.2 metaplasmidSPAdes algorithm.................125

3.6.3 Benchmarking of metaplasmidSPAdes.............127

3.7 Conclusion................................129

Conclusions...................................130

List of abbverations and acronyms.....................132

Glossary.....................................133

References ........................................................................136

Table of figures.................................151

Table of tables.................................152

Introduction

Motivation. An increasing number of biological research projects use the genome sequences for the species under study. The DNA primary structure (genome sequence) is read (or sequenced) by a special machine, the so-called DNA sequencer. The result of the sequencer's run is a huge number of very short(in comparison to genome size) substrings of the genome under study. These sequences are called reads. Reads may contain errors and duplicate information. To use them in further analysis one usually should combine them into the longest possible (in ideal case corresponding to complete chromosomes) substrings of the original genome — the so-called contigs. This process is called genome assembly. Usually, it is performed by a specialized computer program — a genome assembler. Two basic types of assembly can be distinguished: reference-based assembly, that is, an assembly with help of an already known genome of some relative of the organism under study, and de novo assembly or assembly from scratch. De novo assembly does not use previously known reference sequences. This paper will discuss de novo assembly problems exclusively.

The development and cheapening of the sequencing technologies after the emergence of the so-called second generation sequencing technologies led to an explosion in the number of biological research projects which involve genome sequencing. Although the first genome assemblers were developed over thirty-five years ago [98; 119], genome assembly is still actively developing. Both changes in sequencing technologies and an increase in the volume of data analyzed put new demands on the efficiency of the computational algorithms used. Most popular assemblers for second-generation technologies are based on the so-called de Bruijn graph [100].

In the 2010s so-called third generation sequencing technologies appeared. They allow one to obtain long genomic sequences (tens of thousands of nucleotides). The downside of these technologies is a large number of errors in reads. For such data, popular assemblers based on de Bruijn graphs are not suitable directly and the development of alternative computational methods is required. One frequent approach to using third-generation sequencing data is to assemble them together with second-generation sequencing data — the so-called hybrid assembly.

Researchers are often interested not in the entire genome of the studied species, but rather in some part of its genome. One example of such potentially

interesting genome fragments in the case of bacterial genomes is plasmids — DNA molecules inside the cell, physically separated from the chromosomes and capable of independent reproduction. Plasmids are, in particular, frequent carriers of antibiotic resistance genes and participate in horizontal gene transfer between different bacteria [70]. Plasmids can be separated from the rest of the genome both at the stage of sample preparation [41] and after sequencing — at the stage of genomic assembly and postprocessing of assembly results.

Main goals of this work:

- development and implementation of algorithms for hybrid genome assembly from short and long reads; comparison of these methods with available alternatives.

- Development and implementation of algorithms that improve the assembly of plasmid sequences from genomic and metagenomic sequencing data. Benchmarking of these algorithms

The practical value and scientific novelty The following modules and software products were developed as a result of this work:

- SPAdes: a genome assembler for bacterial and other small genomes (https: //cab.spbu.ru/software/spades/);

- hybridSPAdes: a module for hybrid assembly (implemented as a part of SPAdes);

- plasmidSPAdes: a specialized plasmid assembler based on SPAdes (https: //cab.spbu.ru/software/plasmid-spades/, implemented as a part of SPAdes).

- metaplasmidSPAdes: specialized plasmid assembler from metagenomic sequencing data, based on SPAdes (implemented as a part of SPAdes);

- plasmidVerify: a module to verify whether a given DNA sequence is a plasmid, (https://github.com/ablab/plasmidVerify)

Based on the independent comparisons (e.g. [28; 78; 95]), we can claim that these modules are at least among the leaders in their fields. Acknowledgment of these modules can be also confirmed by a high number of citations of corresponding publications (more than 9000 for SPAdes, 170 for hybridSPAdes, and 180 for plasmidSPAdes together with metaplasmidSPAdes) in the SCOPUS database.

Methods. The SPAdes assembler uses the de Bruijn graph [100] to represent the data. Ideas related to graph topology rather than coverage are primarily used to remove edges that correspond to erroneous reads. This allows using SPAdes to

assemble single-cell sequencing data and to modify it to assemble metagenomes [137] and transcriptomes [139]. hybridSPAdes uses bwa mem [74] to align long erroneous reads onto graph edges. Further processing of these alignments is performed with dynamic programming techniques and graph algorithms. The plasmidSPAdes and metaplasmidSPAdes algorithms exploit coverage differences between plasmid and chromosomal DNA sequences. The plasmidVerify module is based on a naive Bayesian classifier [45].

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

Work presentation. The results of this work were presented at several international conferences either in oral talk or as a poster:

1. plasmidSPAdes: Assembling Plasmids from Whole Genome Sequencing Data, talk, RECOMB-SEQ 2016, Los Angeles, USA, April 2016.

2. New members of SPAdes assembly tools family, poster, RECOMB 2016, Los Angeles, April 2016.

3. SPAdes Family of Tools for Genome Assembly and Analysis: What's New, poster, SFAF 2017, Santa Fe, May 2017

4. Plasmid Detection and Assembly in Genomic and Metagenomic Datasets, talk, ASM Conference on Rapid Applied Microbial Next-Generation Sequencing and Bioinformatic Pipelines, Tysons Corner, USA, September 2018

5. SPAligner: Alignment of long diverged molecular sequences to assembly graphs, talk, BIATA 2019, Saint Petersburg, 2019,

6. metaplasmidSPAdes: Plasmid Detection and Assembly in Genomic and Metagenomic Datasets, MCCMB 2019, Moscow, July 2019

Also, some results of these works were presented at various research group meetings and scientific schools.

Publications. In addition to conference presentations, the results of the work were described in five papers [12; 93; 104; 136; 138], which were published in international journals indexed in the Web of Science and Scopus databases. Three of these five articles were published in journals ranked as Q1.

Main results of the dissertation.

- The hybridSPAdes algorithm was designed and implemented. hybridSPAdes is a module to assemble together third-generation sequencing data and NGS sequencing data. Benchmarks showed that hybridSPAdes produce assemblies of comparable quality to other assemblers and may outperform

them in cases of low coverage of the sequenced genome by third-generation sequencing reads.

- The specialized assembler plasmidSPAdes was developed (based on the SPAdes codebase) for assembling plasmids from bacterial sequencing data. Benchmarks showed that plasmidSPAdes can assemble plasmids from bacterial sequencing data better than alternative tools.

- The specialized assembler metaplasmidSPAdes was developed (based on the SPAdes codebase) for assembling plasmids from metagenomic sequencing data. This tool also includes the plasmidVerify module, which allows checking the plasmid assembly results.

Personal contribution In the papers [12; 93] the author contributed to the development of various algorithms, maintained the software, benchmarked it on various data, and contributed to the preparation of the manuscripts. This was a joint work with colleagues from the Algorithmic Biology Lab (St. Petersburg Academic University).

In the hybridSPAdes [136] paper, the author was the only author of the algorithms. In the project, the author also performed the development, testing, and benchmarking of the software module.

In the plasmidSPAdes and metaplasmidSPAdes [104; 138] plasmid assembly projects, the author performed the algorithm development, implementation, and benchmarking of the software modules, and also contributed to manuscript preparation. This was a joint work with Mikhail Raiko, who was responsible for the implementation and benchmarking of the plasmidVerify module.

The volume and the structure of the thesis This disseration consists of an introduction, 3 chapters, and a conclusion. The total volume of the work is 74 pages, including 5 figures and 12 tables. References include 142 citations.

The first chapter is an introductory one. It is devoted to the general problem of genome assembly. This chapter provides information about the development of the subject area. The first half of the chapter is devoted to the history of the sequencing technologies development as well as algorithmic approaches to genome assembly for different sequencing technologies. Then, the algorithm of the SPAdes genome assembler, which served as the basis for the algorithms presented in subsequent chapters, is briefly described. This chapter is partially based on [93] and [12].

The second chapter is devoted to the hybrid assembly problem. The problem is formulated and a brief description of the main approaches used is provided at the

beginning of this chapter. Next, the hybridSPAdes algorithm is described and the computational complexity of its parts is evaluated. Next subsection presents the results of hybridSPAdes on different data sets and compares them to alternative methods. Ideas for further development of the algorithm are briefly described at the end of the chapter. This chapter is based on [136].

The third chapter is devoted to a special case of plasmid genome assembly. Methods previously used to find and assemble plasmid sequences are described at the beginning of the chapter. plasmidSPAdes and metaplasmidSPAdes algorithms for assembling plasmids from the sequencing data of isolated bacteria and metagenomes respectively are described further. This chapter is based on the [138] and [104]. In the conclusion, some examples of applications of the developed algorithms and software modules are provided and the significance of the developed methods is shown. Also, some ideas for the extension of the methods described in this work are listed, both potential and already implemented.

Chapter 1. Introduction to the genome assembly and SPAdes genome

assembler

1.1 Genome and DNA

For the majority of species(with exception of some viruses), genetic information is stored in the deoxyribonucleic acid molecules (DNA). These molecules are polymers, composed of repeating monomer units — so-called nucleotides. Each nucleotide is composed of a sugar, phosphate group and one of 4 nucleobases —adenine, guanine, cytosine, and thymine. Usually, nucleotides are denoted by the first letter of corresponding nucleobases — A for adenine, C for cytosine, G for guanine, and T for thymine. Usually, DNA is composed of two opposite directed connected chains that are connected to each other with hydrogen bonds. Each nucleotide in one chain is connected to the strictly determined nucleotide in the second chain: — adenine to thymine and cytosine to guanine. Determination of the sequence of the DNA —DNA sequencing — is a common first step for lots of biological studies.

1.2 Sequencing methods

All methods to receive the genome of a species are based on sequencing small substrings of the genome, so-called reads. Then reads are assembled into larger sequences (so-called contigs), which corresponds to the larger fragments original DNA sequences. The best-case scenario is one contig corresponding for each DNA molecule, but for most species, it is often hard to achieve it. The first completely sequenced genome is the genome of Phi X174 [92]. However, the start of the age of genome sequencing is usually [86] connected to the invention of shotgun sequencing [82]. In this method, genome copies are randomly split into fragments. A sequencer is used to read a prefix of each such fragment.

The shotgun sequencing method was modified in [126]. This modification suggested to use fragments of the same size. For each fragment, both prefix and suffix

(or, more precisely, the prefix of reverse-complement sequence) are read. This method was massively used by Celera genomics for sequencing drosophila genome [142] and, later, human genome sequencing [124].

Sanger sequencing allowed to receive relatively long (up to 900 bases) and error-free reads, but it was very expensive. Second or next generation sequencing (NGS) radically reduced costs and increased the number of processed reads. However, the length of NGS reads is significantly lower: from 35 to 300 bases. Solexa and, later, Illumina become the most popular NGS sequencers.

Currently, the last generation of sequencers is so-called third generation sequencing. The third generation allows reading long (tens of thousands) sequences. The main disadvantage of these technologies is the high error rate. Pacific Bioscience and Oxford nanopore produce the most popular third generation sequencers.

In addition to the sequencing technologies being processed, assembly problems also differ in the type of input data. The most typical case is the sequencing of a bacterial culture or a tissue of a multicellular organism. In this case, there is no problem to receive the necessary amount of DNA. However, according to [62; 117] more than 99% of bacterial species are currently impossible to cultivate. In the tissues of multicellular organisms, the DNA sequence may differ in different cells in cancer tumors.

The solution to this problem can be a DNA amplification technology called Multiple displacement amplification, usually abbreviated as MDA, which allows obtaining a sufficient amount of DNA from a single cell [72; 85; 107]. However, as a result of this application of this technology, the genome is extremely unevenly covered with reads. This leads to significant complication of the assembly task. For the case of bacterial sequencing, it is possible to sequence the entire heterogeneous community (for example, bacteria living in a soil sample or human gut). This approach is called metagenomic sequencing. It also leads to uneven read coverage from an assembly point of view. Coverage variation, in this case, can be seen not within the same genome, but between the high and low-represented species of the community.

1.3 De novo assembly methods

The first assembled genome (Phi X174 virus, 5.4 kb long) was assembled manually [92]. However, it quickly became clear that the task of assembling the genome can be automated and that automatization of the genome assembly can significantly speed up and reduce the cost of the process. The first software for genome assembly [67; 98] used the Overlap Layout Consensus (OLC) approach, consisting of three basic steps:

- Search for approximate (with a given accuracy) overlaps between all pairs of reads.

- Layout of the found overlaps to determine the relative position of the reads.

- Identification of the consensus sequence of reads covering the same section of the genome.

The development of the NGS sequencing technologies resulted in the rise of de Bruijn graphs based algorithms [61; 100]. This approach uses only exact overlaps between reads of a small fixed length k (so-called k-mers). Most assemblers for NGS data are based on this approach [2; 16; 30; 38; 54; 60; 110; 118; 127; 130]. The SPAdes genome assembler also uses the de Bruijn graphs.

The rise of third-generation sequencing technologies led to the modification of the old and the creation of new assemblers based on the OLC approach [9; 19; 59; 75; 102]. The main difference from the previous OLC assemblers is the modification of the alignment step, taking into account the higher error rate in the third-generation reads.

1.4 Summary of SPAdes assembler algorithm

The SPAdes genome assembler was developed to assemble bacterial genomes sequenced with both MDA technology and conventional multi-cell sequencing data, using NGS reads. However, due to its modular structure, SPAdes is easily modified to work with other data types [8; 11; 14; 81; 84; 104; 112; 131; 136-138; 140]. Some of these modifications( [104; 136; 138]) will be discussed in details in the following chapters of this paper.

1.4.1 General structure of the SPAdes assembler

The SPAdes genome assembler consists of four large modules.

- BayesHammer — module used for preliminary correction of sequencing errors in reads [90].

- Assembler core, which implements the construction of the de Bruijn graph from the sequencing data and further processing of this graph (transformation to the assembly graph).

- exSPAnder module for constructing contigs from graph edges using additional linkage information (for example, information about the mapping of paired reads to the graph).

- MismatchCorrection module for correcting errors in the final assembly (polishing).

Preliminary error correction of reads is necessary to reduce memory consumption and to speed up the SPAdes core. BayesHammer can be replaced with alternative read correction methods, either developed specifically for SPAdes [66], or external [17; 68; 80].

MismatchCorrection is used to correct small errors in contigs (single-nucleotide substitutions, as well as small inserts and deletions) by aligning the reads to the preliminary assembly. It can be replaced with tools of similar purpose [42; 103] or disabled; it can also be used separately from SPAdes to polish assemblies obtained by other methods (for example, reference-based assembly).

Both BayesHammer and MismatchCorrection are optional modules and can be either used unchanged with the tools described in next chapters, or not to be used at all. So we'll provide more details in this section only for the SPAdes assembler core and exSPAnder module.

Following common notations will be used:

- IS| — length of string S

- S[n] — character number n(numeration starts from 0) of the string S

- S[x..y] — a substring of the string S, starting with the character number x and ending with the character number y

- S • T — concatenation of strings S and T

1.4.2 Construction and compression of the de Bruijn graph

The de Bruijn graph can be defined as follows: the de Bruijn graph with the parameter k is a directed graph G = (V,, E), accomplished with string labels on the vertices f (V) and edges g(E), which satisfy following conditions:

- For all vertices v £ V, \f (^)j = k,

- For all edges e £ E, \g(e)\ = k + 1,

- For all edges e = (v1,v2) £ E, f (i>i) = g(e)[0..k — 1] and f (v2) = g(e)[1..k]. String labels of vertices of size k from the definition above are usually called k-mers. Need to note that in some papers (for example [100]) the parameter k denotes the lengths of the labels on the edges (and k — 1 — on the vertices).

The de Bruijn graph (G(V,E), f (V),g(E), k) corresponds to the set of strings R if f (V) coincides with the set of all different substrings of length k of all strings from R, and the set g(E) coincides with the set of substrings of length k + 1 of all strings from R. It's easy to see that for a given set of strings R corresponding de Bruijn graph can be explicitly constructed.

In the case of the genome assembly problem, the set R is the set of all reads received from the sequencer.

Let's call unambiguous vertices such vertices in a directed graph that their outgoing and incoming degrees (i.e., the number of incoming and outgoing edges) are equal to 1, and ambiguous — all other vertices. For each path p = e1,e2... en in G, the path label compression function is defined as the concatenation of the first characters of all edges except the last one and the entire label of the last edge (label(p) = g(e1)[0}g(e2)[0}...g(en—1)[0]g(en)) Let's call compressible a path in which start and end are ambiguous vertices, and all intermediate vertices are unambiguous. For a given de Bruijn graph (G(V, E), f (V),g(E), k), one can construct a new graph G' = (V', Er) where V' is the set of ambiguous vertices G and edges E' correspond to all compressible paths in G. Labels on the vertices remain the same. Label function on the edges of the new graph label(E') is obtained by compressing the labels of the corresponding paths in the original de Bruijn graph. This new graph is called the compressed de Bruijn graph. Similar to the de Bruijn graph, its properties can be described as follows:

- For all vertices v £ V', \f (^)j = k

- For all edges e £ E', \label(e)\ > k + 1

— For all edges e = (^1,^2) £ 1) — label (e)[0..k — 1] and f(v2) = Za6eZ(e)[Z — k + 1..Z — 1] where / = |Za6eZ(e)|

— For all vertices v G V' 1 v is ambiguous.

SPAdes stores the de Bruijn graph using perfect hashing [44] to reduce the memory consumption. Procedure of compressed de Bruijn graph construction from the de Brujin graph follows its definition.

Errors in the reads used to construct the de Bruijn graph lead to the appearance of erroneous edges i.e. edges with labels that are not substrings of the sequenced genome. The erroneous edges removed by the SPAdes algorithm can be divided into the following three types:

a) tips — edges leading to or from a hanging vertex

b) bulges — erroneous edges with a "similar"alternative path

c) chimeric edges — edges connecting distant regions of the genome.

Figure 1.1 — Types of erroneous edges detected by SPAdes. Left figure depicts an example of a tip; middle one — bulge; right one shows an example of chimeric edge. Erroneous edges showed

with dotted line in all cases.

Figure 1.1 shows simple examples for all these types of erroneous edges. In all three cases, SPAdes remove only relatively short edges. Edges of type a) and b) usually occur due to small sequencing errors. Errors (a single-nucleotide substitution or a small insertion/deletion) occurring at the end of the read usually lead to the appearance of k-meis for which there is no continuation, i.e. dead-end edges. An error in the middle of reads may cause a bulge. It is also possible for bulges to represent inexact genomic repeats, small variations in the genome of a sequenced colony of bacteria, or the presence of similar strains of the same species in the metagenome. Chimeric edges usually occur due to the specifics of the single-cell sequencing process. For the case of sequencing data with high and uniform coverage SPAdes considers as erroneous all relatively short edges of low coverage, regardless of their location

1.4.3 Deleting erroneous edges

on the graph. All such edges are iteratively removed from the compressed de Bruijn graph. After each deletion, the unambiguous vertex compression process (described in the previous section) is triggered. Details of the algorithms for detection and removal of erroneous edges (and their practical implementation) can be found in the articles [12; 93; 137].

The resulting graph is supposed to contain only edges corresponding to the correct segments of the sequenced genome. Later, such graph will be called the assembly graph.

1.4.4 Iterative construction of the assembly graph

The algorithms described in the previous section allow us to get rid of the edges obtained from erroneous reads. Another assembly problem is the so-called gaps in the coverage — the absence of &-mers of a given size in the input reads. This problem often occurs in data with uneven coverage. For example, it is a usual issue for the data obtained with MDA technology or in the case of metagenome sequencing. At the same time, for a fixed set of reads, the greater is the value of the parameter k, the more genomic &-mers will be absent in the final graph. However, due to the larger number of repetitive regions longer than k, selecting the small value of k may significantly complicate the graph [60], and hence, the resolution of repeats and scaffolding. SPAdes tries to take advantage of using both small and large values of k. To do so, the steps described in the previous two subsections are applied iteratively for different values of k. First, the graph is constructed using a relatively small k. Next, erroneous edges are removed in the graph, and unambiguous paths are compressed, which allows one to collect a part of the small coverage sections in one contig. After that, the edges of the resulting assembly graph are added to the original reads. Then the construction and simplification process is repeated for larger values of k. The sequence of the edges of the assembly graph from the previous iteration can contain &-mers that are not present in the reads, i.e. that may help to close gaps in the coverage.

SPAdes applies different sets of &-mer lengths depending on the lengths of the input reads and the type of the input data. It is empirically established that assemblers based on the de Bruijn graphs usually work well (on isolate sequencing

data) when the value of the parameter k is slightly greater than half the read length. Therefore values of k from the set {21,33,55} are used by default for the reads of 100 nucleotides as well as for metagenomic data and MDA sequencing data regardless of the length of the reads. For the reads of the length 150 SPAdes uses &-mers from set {21,33,55,77}, and for reads of length 250 or more — from set {21,33,55,77,127}. Users can also specify the set of lengths of the &-mers used manually. The value of the parameter k strongly affects the complexity of the resulting de Bruijn graph. The optimal value depends on the length of the read, the depth of the sequencing, and the uniformity of the genome coverage by the reads. The problem of optimal choice of k is considered, for example, in the articles [23; 57]. However, for the iterative construction of the assembly graph, the problem of optimal selection of k is not well studied. At the same time, the use of the repeats resolution algorithm (described in the section 1.4.5) allows to mimic possible suboptimality of &-mer length selection.

1.4.5 Application of paired reads mapping. Summary of the

exSPAnder algorithm

The string labels of the edges of the assembly graph can already be considered as the result of the assembler's work. However, with the help of additional linkage information, one can often receive a less fragmented assembly. A typical case of linkage information is the information about mapping paired reads which were used to construct the graph. Information obtained with other technologies, such as optical maps [96] or long, erroneous reads, can also be considered as linkage information. The latter case will be discussed in detail in the next chapter. The SPAdes genomic assembler uses the exSPAnder module, which uses various types of data (for example, paired reads or mate pairs, i.e. paired reads with a large insert size) to close gaps in the assembly and to resolve repeats. exSPAnder is a modular, easily extendable algorithm based on the concept of "path expansion" [16; 97; 121]. It starts from initializing of the set of paths S with all relatively long edges. Then, for each path in S, exSPAnder successively tries to extend it using one of the potential extension edges that are edges starting from the vertex at which this path ends. Correct extension edge is selected using the decision rules defined

in exSPAnder, which evaluate how well each of the extension edges is supported by sequencing data. For example, information about mapping paired reads to the path and its potential extension can be used. exSPAnder supports the use of multiple decision rules. Usually, several decision rules correspond to different libraries or even data types. exSPAnder alternately and independently tries to apply all the decision rules until either one of them reports a suitable extension edge, or all of them "say" that there is not enough information to continue the path. As a final step, duplicated paths in S are removed, and remaining ones are output as assembly results.

More details on the exSPAnder module can be found in [8; 39].

Chapter 2. Hybrid assembly with the hybridSPAdes algorithm 2.1 Third-generation sequencing technologies

A huge amount of biological and medical research starts from the sequencing of the genome. With the appearance of short-read sequencing technologies (Solexa-Illumina), the cost of sequencing decreased by orders of magnitude when compared to Sanger. However, these technologies have a big disadvantage — the relatively short length of reads. This makes it impossible to resolve long repeats, which does not allow to finish even relatively simple genomes. One way to solve this problem is the technology of paired reads sequencing. However, for example, the gene encoding 16S RNA is usually present in the genome in several copies and has an average length of about 1.5 kilobases [24]. This significantly exceeds the commonly used insert sizes for paired read libraries. So, assembly of most bacterial genomes into a single contig using only NGS data is even theoretically impossible [109].

An alternative approach to sequencing is long-reading technologies developed independently by Pacific Biosciences and Oxford Nanopore. Both of these technologies allow to receive reads of tens and hundreds of kilobases (which is obviously longer than the maximum repeat length in almost any bacterial genome). However, both of these technologies suffer from a high (>10%) error rate. So, to receive high-quality assembly with PacBio/Nanopore one need high read coverage. This requirement increases the sequencing costs. During the last couple of years, the development of Pacific Biosciences' technology named HiFi gained significant popularity. HiFi reads the same fragments of the genome multiple times and then produces a consensus string. This allows receiving a significantly lower error rate than in conventional PacBio reads, at expense of decreasing read length. The error rate of HiFi reads, except for the incorrect determination of the multiplicity of homopolymers, is comparable to the error rate of NGS reads(<0.2%, [3]). HiFi-based hybrid assembly was used, for example, in recent work that improves the assembly quality of the human genome [132]. However, problems related to HiFi assembly will not be considered in this paper.

2.2 Hybrid assembly approaches

The first tool for hybrid assembly [59] used short reads to correct errors in long reads and then assembled long reads with the OLC approach. In the ALLPATHS-LG paper [55] authors proposed to align long reads to the de Bruijn graph constructed from short reads. These alignments are used to calculate the consensus of the long reads. Then de Bruijn graph with a significantly longer &-mer length is constructed from the obtained consensus sequences. The final step consists of the usage of the so-called mate-pairs. Mate-pairs is a special type of NGS pair reads with a large insert size.

The Cerulean [20] algorithm builds a de Bruijn graph from short reads and then transforms it into a skeletal graph by aligning long reads.

In the Masurca [58] assembler, the so-called super-reads — "unambiguous"DNA sequences are first constructed from the NGS data. Super-reads may be considered as a concept close to the edges of the assembly graph (without direct graph construction). Next, long reads are aligned to the super-read sequences. These alignments are used to connect super-reads.

The Unicycler [122] algorithm developed after the publication of hydridSPAdes also uses the alignment of long reads to the de Bruijn graph. Further resolution of complex repeated regions is done using the information about such alignments. Unicycler's implementation is based on the SPAdes code base. This algorithm uses coverage information to determine repeated edges. Because of this, Unicycler is not applicable to the data with highly uneven coverage, such as single-cell sequencing or metagenomic sequencing data.

For the datasets with sufficiently high coverage of long reads, one can use only them for the assembly. Long reads assembly can be done using the methods described in one of the papers [7; 9; 19; 75]. In this case, the short reads are used only at the final stage, for the correction of minor errors — so-called polishing [43; 103; 129]. Although it is not clear whether it is correct to call this approach hybrid assembly, it is necessary to mention that for bacterial datasets with sufficiently high long reads coverage this approach is currently the de facto standard.

2.3 hybridSPAdes module for hybrid assembly 2.3.1 General structure of hybridSPAdes

The hybridSPAdes assembler's algorithm consists of the following steps:

1. Construction and simplification of the de Bruijn graph

2. Construction of the alignments of the long reads to the de Bruijn graph

3. Filling the gaps in the de Bruijn graph with long reads

4. Resolution of the genomic repeats with the information about long reads mapping.

The first part is implemented with the SPAdes genome assembler (see chapter 1). Each of the remaining sections of the algorithm will be described in detail later in this section.

2.3.2 Construction of the alignments of long reads to the de Bruijn

graph

2.3.2.1 Global and local alignment of strings

Sequence alignment problem is one of the first algorithmic problems in bioinformatics. There are several possible formulations for this problem. Historically, the problem of optimal global alignment was the first to be considered [87]. Sequence alignment problem can be formulated as follows: Given strings s = (si ,s2... sm) and t = (t1,t2 ...tn) over the alphabet S, let's consider the auxiliary whitespace character e not included in S and define the alphabet S' as S U e. We introduce the auxiliary function g : (S')* ^ (S)* , which consists in removing all the occurences of e from the string above the alphabet S' (where (S')* and (S)* are the sets of all strings over the alphabets S' and S, respectively). The global alignment of the strings s and t are the strings s' and t' such that g(s') = s; g(t') = t; Vi, s'[f]l = e or t'№ = e; K| = It'|.

This can be represented as padding two string with whitespaces and writing them one above the other so that each character of one string corresponds to either a character of the other string or a whitespace. Optimal global alignment is that alignment that maximizes a similarity function f (s',t'). In the simplest case f (s',t') is |s'| h(s'KM'Kl), where h(x,y) = 1 if

x = y and 0 otherwise. More complex alignment similarity functions are also used.

Also, common problems are optimal local alignment (i.e., alignment maximizing the similarity function for all optimal global alignments of all pairs of substrings of given two strings) and semi-global alignment (i.e., maximizing the similarity function for all optimal global alignments of all substrings of the first string and complete second string)

In the case of global or semi-global alignment one can minimize the distance function, such as edit or Levenshtein distance [73] instead of maximizing the similarity function. In the simplest case, f (s',t') = sumi=i.\s'\h(s'[i],t'[i]), where h(x,y) = 0 if x = y, a if (x = e or y = e) and n in other cases, for positive a and In the classical Levenshtein formulation, n = a = 1. The parameters a and n are often referenced as the cost of indel and mismatch, respectively. For all these problems, there are classical quadratic algorithms [88; 116].

The problem of aligning reads to a genomic string is the semiglobal (or, sometimes local) alignment problem. For the case of sequencing data, one often needs to align gigabytes of input data. So, general quadratic-time algorithms are not applicable. Therefore, a variety of heuristic solutions [13; 21; 69; 75-77] are usually used. For some reads, they may not produce an optimal alignment, but for practical purposes, their accuracy is usually sufficient.

Similarly to the search for optimal local alignment of two strings, we can formulate the problem of search for optimal local alignment of a string R and a de Bruijn graph G. For this problem, one needs to optimize the similarity function between all substrings of R and strings read from all possible paths in G. The path for which the similarity function is maximized will be called alignment path. Semi-global alignment between a string and a graph can also be defined in a similar manner. Improving de Bruijn's graph-based assembly with third-generation reads naturally starts with solving alignment problem — finding how a long, highly error-prone read "traverses"the graph.

There were no software products practically applicable to aligning third-generation reads to de Bruijn graphs, before [136], which served as the basis for this

chapter, and universal algorithms described in [4] were not used by bioinformatics tools.

2.3.2.2 Alignment of reads to a compressed de Bruijn graph

The hybridSPAdes' search for the position of local alignment of a long read to a compressed de Bruijn graph consists of the following three steps:

1. Search for local alignments of the read to the edges of the compressed de Bruijn graph

2. Construction of an optimal "skeleton"alignment on the graph — a sequence of alignments to the edges found in the previous step

3. Filling the gaps in the skeleton alignment

hybridSPAdes uses only alignment paths for the hybrid assembly. The alignment itself is not explicitly constructed. However, as shown in [111], this alignment can also be easily reconstructed.

It should be noted that similar to read-to-string alignment tools, hybridSPAdes does not guarantee to find the optimal alignment to the graph for every read.

2.3.2.3 Alignment of long reads to the graph edges

The first step in constructing alignment of a long read to the compressed de Bruijn graph is to construct local alignments of this read to the string labels of edges of this graph. At the time when hybridSPAdes development started, there were no commonly used software solutions for quickly constructing alignments of long erroneous reads. Thus, a heuristic algorithm similar to [13;21] was implemented. It used the search for short common substrings (seed alignments) and their further merging. Later the widely used software product bwa [77] for string alignment was adapted to work with long, highly erroneous reads, and was used for this part of the algorithm. Short alignments (less than 200 bases), reported by bwa, can be unreliable and thus are not used in the further steps of the algorithm.

2.3.2.4 Combining alignments to the edges of the assembly graph into

a "skeleton"alignment

The position of the local alignment of a long read to an edge of the graph can be briefly recorded as a triplet (edgeid, (es,ee), (rs,re)) where edgeid is the edge to which the read is mapped. (es,ee) and (rs,re) are the start and end of alignment positions on the edge and the read respectively. The alignment length is defined as the difference of the positions of the end and the start of the alignment on the read (re — rs). We'll say that a triplet (edge2, (e2s,e2e), (r2s,r2e)) can follow a triplet (edgei, (eis,eie), (ris,rie)) if

1. T2s > Tie

2. (r2s — rie)(l + e) > (\edge\\ — eie + e2s + D) where D is the length of the shortest path in the graph between the end of edgei and the beginning of edge2 and e — a small constant (default value 0.3)

3. f2s — rie < 5000