Построение графа де Брюина – первая стадия работы сборщика. После построения граф упрощается. После этого на нем запускается алгоритм исправления ошибок.

Ошибки чтения порождают в графе структуры трех типов: отростки (tips), пузыри (bulges) и ошибочные ребра. Первые возникают из-за ошибок на концах чтений, вторые – из-за ошибок внутри чтений, а третьи – в результате повторных ошибок. Эти три типа ошибок удаляются одна за другой.

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

Критерий длины цепочки состоит в том, что удаляются только цепочки длины меньше 2k.

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

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

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

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

Заметим, что модифицирование путей – операция довольно дорогостоящая из-за дополнительной информации, хранящейся в графе.

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

Алгоритм EULER_USR изложен в статье «De novo fragment assembly with short mate-paired reads: Does the read length matter?» 2009 года (Mark J. Chaisson, Dumitru Brinza and Pavel A. Pevzner) [2].

Алгоритм состоит из трех шагов:

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

Построение на основе k-меров полученных префиксов графа повторов (repeat-graph).

Упрощение построенного графа.

Для исправления ошибок используется простые соображения, по которым k-меры делятся на две группы – надежные (solid) и все остальные. Надежными называются k-меры, которые встречаются в чтениях не меньше некоторого заранее выбранного числа m. Если все k-меры одного чтения являются надежными, то считается, что чтение не содержит ошибок. В противном случае производится попытка исправить ошибки в нем. Рассматриваются только ошибки замены, так как ошибки вставки и удаления редки в чтениях секвенатора Illumina.

Для исправления ошибок жадным образом ищется минимальное число исправлений, которое необходимо осуществить, чтобы сделать каждый k-мер в чтении надежным. Для каждого исправления на каждой позиции записывается, сколько k-меров становится надежными в результате этого исправления. Исправление, которое делает максимальное число k-меров надежными, применяется, если это число не меньше некоторого заранее выбранного порога t. Когда находится подходящее исправление, выводится максимальный по длине префикс чтения, содержащий только надежные kмеры. Суффикс k-мера, считающийся менее надежным, будет исправлен на более поздней стадии работы алгоритма.

Для выбора параметра k полагается, что распределение k-меров является смесью двух распределений – распределения ошибочных k-меров и распределения правильных (рис. 4). И те, и другие k-меры распределены по закону Пуассона, но распределение правильных k-меров имеет большое среднее, поэтому аппроксимируется распределением Гаусса. Параметр m выбирается как точка минимума распределения k-меров, параметры которых определяются исходя из частотного анализа k-меров.

Разработка метода сборки геномных последовательностей на основе восстановления фрагментов по парным чтениям Рис. 4. Экспериментально полученное распределение k-меров Подход, применяемый в сборщике ABySS (Assembly ByShort Sequences), изложен в статье «ABySS: A parallel assembler for short read sequence data» 2009 года (Jared T. Simpson, Kim Wong, Shaun D. Jackman, Jacqueline E. Schein, Steven J.M. Jones, Inanc Birol) [10]. По сути он ничем не отличается от подхода, применяемого в Velvet'е.

1.1.5. Сравнение рассмотренных методов исправления ошибок В табл. 1 представлено сравнение рассмотренных в обзоре методов исправления ошибок.

Сравнение проводилось по следующим пунктам:

способ представления данных;

возможность распараллеливания;

участие в проекте de novo Genome Assembly Project (dnGASP, организован Национальным центром геномного анализа, Барселона, Испания, http://cnag.bsc.es);

Разработка метода сборки геномных последовательностей на основе восстановления фрагментов по парным чтениям Таблица 1. Сравнение рассмотренных в обзоре методов исправления ошибок Genome Sequencing and Assembly with HighThroughput, Short-Read Technologies (2007)

ALLPATHS: ALLPATHS

Does the read length matter?

parallel assembler for short read sequence data Разработка метода сборки геномных последовательностей на основе восстановления фрагментов по парным чтениям В настоящем разделе приводится обзор существующих методов сборки генома.

В статье [10] изложен подход к сборке контигов в программном средстве ABySS. Этот подход состоит из двух этапов:

сборка контигов без учета парной информации;

разрешение неоднозначностей с помощью парной информации и наращивание контигов.

В основе всего подхода лежит распределенный граф де Брюина.

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

На втором этапе между контигами устанавливаются связи, используя парную информацию.

Пара чтений называется связывающей два контига, если первое чтение картируется на первый контиг, а второе – на второй. Между двумя контигами устанавливается связь, если число связывающих их чтений больше некоторой константы p (по умолчанию используется p = 5). Для каждого контига Ci строится множество связанных с ним контигов Pi. Затем в графе связей контигов ищется уникальный путь, проходящий через все контиги из Pi. В качестве ограничений при поиске выступают оценка на расстояния между контигами на основе принципа максимального правдоподобия и эвристическая оценка на число посещенных вершин. После того, как поиск таких путей для каждого контига завершился (успешно или нет), согласующиеся пути сливаются, образуя конечные контиги.

Алгоритм, лежащий в основе сборщика ALLPATHS, изложен в статье [1]. Он также основан на графе де Брюина и состоит из нескольких этапов.

Первым этапом является создание начального приближения контигов. Для этого, как и в ABySS, рассматриваются последовательности смежных однозначных ребер, которые и объявляются приближением контигов.

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

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

Затем для каждого выбранного контига – центра локализации – рассматривается множество последовательностей (чтений и контигов), лежащих в пределах, например, 10000 нуклеотидов от краев этого контига – окрестность контига. Если построить приближение этого множества, то можно будет собрать небольшой участок генома, практически только из тех чтений, которые в него картируются. Это позволяет существенно уменьшить объем данных. Для начала выделяется набор почти уникальных в геноме первоначальных контигов, лежащих в рассматриваемом промежутке. Это происходит с помощью итеративного добавления новых контигов, связанных с уже найденными (рис. 5). При этом для каждого контига можно узнать его смещение относительно центра (с какой-то погрешностью), что позволяет отбросить далеко отстоящие контиги. Затем строятся два множества чтений: первичное, состоящее из чтений картирующихся в рассматриваемую область генома, но, возможно, не всех таких чтений, и вторичное, которое кроме интересующих чтений, возможно, содержит и некоторые другие. В первичное множество входят, все пары чтений, хотя бы одно из которых картируется на какой-либо из выбранных контигов. Во вторичное множество чтений входят те пары чтений, которые могут быть собраны из чтений из первичного множества. Затем Разработка метода сборки геномных последовательностей на основе восстановления фрагментов по парным чтениям перекрывающиеся пары чтений из вторичного множества сливаются, образуя пары более длинных последовательностей.

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

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

Алгоритм работы Velvet изложен в статье [12].

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

Зная распределение длин пропусков в парных чтениях, можно выделить длину L такую, что число парных чтений, имеющих пропуск длиннее L, ничтожно мало. Можно выделить «длинные»

вершины – вершины, длины которых не меньше чем L. Заметим, что таких «длинных» вершин должно быть достаточно много, поэтому значение L не должно быть слишком большим. Затем выделяются парные «длинные» вершины, связанные несколькими парными чтениями (рис. 7). Если после «длинной» вершины может следовать несколько «длинных» вершин, то она называется неоднозначной. Все узлы, на которые картируется чтение, парное к которому картируется на однозначную «длинную» вершину, помечаются. После этого уникальные узлы последовательно Разработка метода сборки геномных последовательностей на основе восстановления фрагментов по парным чтениям наращиваются, добавлением помеченных узлов, связанных с текущим. Этот процесс продолжается до тех, пор пока не встречается узел, у которого нет продолжения или есть несколько вариантов продолжения. Если несколько «длинных» вершин последовательно соединились такими путями, они объединяются в контиг.

Способ сборки, используемый в SOAPdenovo, описан в статье [4]. Этот алгоритм разработан в Пекинском геномном институте (Китай).

Как и многие другие сборщики из коротких чтений SOAPdenovo использует граф де Брюина.

После исправления ошибок пути, которые не содержат вершин с ветвлениями, объявляются первоначальным приближением контигов (рис. 8).

Затем происходит картирование парных чтений на контиги. Между двумя контигами устанавливается порядок и оценивается расстояние между ними, если их соединяют как минимум три пары чтений. Далее наборы контигов с совместимыми связями линеаризуются, образуя скэффолды.

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

Разработка метода сборки геномных последовательностей на основе восстановления фрагментов по парным чтениям В статье [2] изложены основы работы средства EULER-USR из набора EULER.

Сборщик EULER использует для сборки сведение к задаче о поиске эйлерова суперпути – пути, проходящем через все ребра и содержащем в качестве подпутей все пути из наперед заданного множества P. Эта задача, в свою очередь, сводится к задаче поиска эйлерова пути. Такая постановка задачи была сформулирована в статье [7]. В этой статье предлагается в качестве графа использовать граф де Брюина, а в качестве множества P для начала использовать пути, соответствующие чтениям.

Затем, после некоторых преобразований, упрощающих граф, рассмотреть все парные чтения (r1, r2) и найти все пути, соединяющие r1 и r2 и имеющие длину около ожидаемой, определенной из априорного распределения длин. Если такой путь единственный, то он добавляется в множество P.

Этот процесс повторяется до тех пор, пока в графе происходят изменения.

В статье [2] предлагается способ учета и тех парных чтений, для которых нашлось несколько путей. Пусть для парных чтений (readstart, readend) нашлось несколько путей (рис. 9). Обозначим за estart и eend ребра, в которых начинаются и заканчиваются readstart и readend соответственно. Для каждого пути p, соединяющего readstart и readend, рассмотрим величину support(estart,eend,p) – число парных чтений, поддерживающих этот путь – таких парных чтений (r1, r2), что одно из них картируется на ребро estart или eend, а другое на путь p. Из всех путей выбирается путь с максимальным значением support, если оно не меньше некоторого порогового значения MinSupport.

1.2.6. Сравнение рассмотренных методов сборки контигов В табл. 2 приведено сравнение рассмотренных в обзоре методов сборки контигов. Сравнение производилось по следующим пункта:

способ представления данных;

возможность распараллеливания;

Разработка метода сборки геномных последовательностей на основе восстановления фрагментов по парным чтениям Таблица 2. Сравнение рассмотренных в обзоре методов сборки контигов` parallel assembler for short read sequence data

ALLPATHS: ALLPATHS

Does the read length matter?

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

1.3. ФОРМАТЫ ПРЕДСТАВЛЕНИЯ ГЕНОМНЫХ ДАННЫХ

1.3.1. Шкала оценки качества геномных данных Phred В большинстве форматов представления геномных данных для хранения качества отдельных нуклеотидов используется шкала качества Phred [8]. В ней качество одного нуклеотида кодируется одним символом. Для получения вероятности того, что конкретный нуклеотид был считан правильно, необходимо получить число P. Для этого из кода символа необходимо вычесть код базового символа.

Базовый символ является разным в разных форматах. Вероятность ошибки составляет 10-P/10.

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

Формат FASTQ используется для хранения нуклеотидных последовательностей их информации об их качестве. Файлы в этом формате имеют расширение fastq. Файл в формате FASTQ представляет собой текстовый файл, состоящих из нескольких блоков [6]. Каждый блок состоит из четырх строк.

Первая строка начинается с символа @ и содержит идентификатор чтения и возможно его описание.

Вторая строка содержит нуклеотиды чтения, при этом символы A, T, G, C означают соответственно Аденин, Тимин, Гуанин, Цитозин, а символ N означает что соответствующий нуклеотид неизвестен.

Третья строка содержит один символ – плюс, и возможно идентификатор чтения, совпадающий с идентификатором чтения в первой строке.

Четвертая строка содержит описание качества чтения по одному символу на нуклеотид.

Качество записано по шкале качества Phred.

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

Формат FASTA используется для хранения нуклеотидных последовательностей или последовательностей аминокислот. Файлы в этом формате имеют расширение fasta. Файл в формате FASTA представляет собой текстовый файл, состоящих из нескольких блоков [3].

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

Разработка метода сборки геномных последовательностей на основе восстановления фрагментов по парным чтениям Таблица 3. Обозначения возможных нуклеотидов в формате FASTA Формат Standard Flowgram используется для хранения нуклеотидных последовательностей их информации об их качестве. Файлы в этом формате имеют расширение sff. Формат разработан в компании 454 Life Sciences и институтах Whitehead Institute for Biomedical Research и Sanger Institute [5]. Файл в этом формате состоит из трех секций.

Заголовок файла, встречается один раз в начале файла, содержит информацию о числе чтений в файле, версию файла, и другую служебную информацию.

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

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

Этот формат не является человеко-читаемым. Для работы с ним необходимо использование специальных библиотек.

Формат SAM используется для описаний чтений их выравниваний [11]. Файлы в этом формате имеют расширение sam. Файл в этом формате состоит из двух частей: заголовка и описаний выравниваний чтений Заголовок состоит из нескольких строк, начинающихся с символа @ и содержащих произвольную информацию о файле.

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

Разработка метода сборки геномных последовательностей на основе восстановления фрагментов по парным чтениям Формат BAM аналогичен формату SAM. Файл в формате BAM представляет собой файл формата SAM сжатый при помощи библиотеки BGZF аналогичной формату ZIP [13]. Отличие этого формата от простого сжатия формата SAM является быстрый доступ к произвольной позиции сжимаемого файла. Этот формат не является человеко-читаемым. Для работы с ним необходимо использование специальных библиотек.

В табл. 4 приведено сравнение описанных форматов.

Таблица 4. Сравнение форматов представления геномных данных.

FASTQ FASTA Standard Flowgram Format SAM BAM Разработка метода сборки геномных последовательностей на основе восстановления фрагментов по парным чтениям Алгоритмы исправления ошибок в наборе чтений геномной последовательности испоьзуют в качестве базового принципа работы граф де Брюина или частотный анализ встречаемости Алгоритмы сборки контигов (протяженных непрерывных фрагментов геномной последовательности), как правило, основаны на использовании графа де Брюина.

Одним из недостатков, которым обладают перечисленные программные средства, является большой объем оперативной памяти, необходимый им для сборки генома, сходного по размерам с геномом человека (2-3 миллиарда нуклеотидов). Так, например, SOAPdenovo необходимо порядка 140 гигабайт оперативной памяти, а ABySS – 21 компьютер с гигабайтами каждый (всего – 336 гигабайт). Такие затраты памяти обусловлены наличием ошибок секвенирования в исходных данных (такие ошибки ведут к увеличению размера графа де Брюина), а также неоптимальным методом хранения этого графа.

Еще одним недостатком существующих методов сборки является отсутствие внутреннего контроля качества сборки.

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

2. ВЫБОР И ОБОСНОВАНИЕ ОПТИМАЛЬНОГО ВАРИАНТА ПРОВЕДЕНИЯ

ИССЛЕДОВАНИЙ И ВЫБОР АРХИТЕКТУРЫ МЕТОДА СБОРКИ ГЕНОМНЫХ

ПОСЛЕДОВАТЕЛЬНОСТЕЙ

2.1. ВЫБОР И ОБОСНОВАНИЕ ОПТИМАЛЬНОГО ВАРИАНТА ПРОВЕДЕНИЯ ИССЛЕДОВАНИЙ

Одним из недостатков, которым обладают перечисленные программные средства, является большой объем оперативной памяти, необходимый им для сборки генома, сходного по размерам с геномом человека (203 миллиарда нуклеотидов). Так, например, SOAPdenovo необходимо порядка 140 гигабайт оперативной памяти, а ABySS – 21 компьютер с 16 гигабайтами каждый (всего – гигабайт). Такие затраты памяти обусловлены наличием ошибок секвенирования в исходных данных (такие ошибки ведут к увеличению размера графа де Брюина), а также неоптимальным методом хранения этого графа. Другим недостатком существующих методов сборки является отсутствие внутреннего контроля качества сборки.

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

При проведении теоретических исследований в рамках настоящего Государственного контракта планируется разработать два алгоритма:

алгоритм исправления ошибок в наборе чтений геномной последовательности;

алгоритм восстановления фрагментов геномной последовательности.

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

2.2. АРХИТЕКТУРА МЕТОДА СБОРКИ ГЕНОМНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ

Сборка генома в предлагаемом методе будет осуществляться в четыре этапа (рис. 10):

исправление ошибок в наборе чтений геномной последовательности;

восстановление фрагментов геномной последовательности по чтениям;

сборка контигов из восстановленных фрагментов;

сборка скэффолдов из контигов.

При этом для первых двух этапов будут разработаны в рамках настоящей НИР алгоритмы и выполнена их программная реализация, а для третьего и четвертого этапов – будт использоваться сторнние средства, выбор которых будет осуществлен при планировании экспериментальных исследований.

Разработка метода сборки геномных последовательностей на основе восстановления фрагментов по парным чтениям Исправление Рис. 10. Архитектура метода сборки геномных последовательностей Для алгоритмов будут создаваться теоретические описания, затем будет выполняться их программная реализация на языке программирования высокого уровня, а далее будет выполняться ряд вычислительных экспериментов с разработанной программой.

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

При разработке алгоритма восстановления фрагментов геномной последовательности будут применяться методы обработки битовых строк, методы поиска путей в графах, методы обхода графов и методы перебора. Применение указанных методов обосновывается их высокой эффективностью, которую доказывают результаты НИР, проводящихся в ведущих научных центрах мира, а также результаты предварительных исследований, проведенных в СПбГУ ИТМО.

ВЫВОДЫ ПО ГЛАВЕ

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

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

3. ПОДГОТОВКА ПЛАНА ПРОВЕДЕНИЯ ТЕОРЕТИЧЕСКИХ И

ЭКСПЕРИМЕНТАЛЬНЫХ ИССЛЕДОВАНИЙ

3.1. ПЛАН ПРОВЕДЕНИЯ ПЕРВОГО ЭТАПА ТЕОРЕТИЧЕСКИХ И ЭКСПЕРИМЕНТАЛЬНЫХ

ИССЛЕДОВАНИЙ

патентные исследования;

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

Результаты работ первого этапа:

научно-технический отчет;

отчет о патентных исследованиях.

3.2. ПЛАН ПРОВЕДЕНИЯ ВТОРОГО ЭТАПА ТЕОРЕТИЧЕСКИХ И ЭКСПЕРИМЕНТАЛЬНЫХ

ИССЛЕДОВАНИЙ

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

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

Результаты работ второго этапа:

научно-технический отчет.

3.3. ПЛАН ПРОВЕДЕНИЯ ТРЕТЬЕГО ЭТАПА ТЕОРЕТИЧЕСКИХ И ЭКСПЕРИМЕНТАЛЬНЫХ

ИССЛЕДОВАНИЙ

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

Результаты работ третьего этапа:

научно-технический отчет.

3.4. ПЛАН ПРОВЕДЕНИЯ ЧЕТВЕРТОГО ЭТАПА ТЕОРЕТИЧЕСКИХ И ЭКСПЕРИМЕНТАЛЬНЫХ

ИССЛЕДОВАНИЙ

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

подготовка заявки на регистрацию программы для ЭВМ;

проведение вычислительных экспериментов;

анализ результатов вычислительных экспериментов;

подготовка статьи для публикации в журнале из перечня ВАК.

Результаты работ четвертого этапа:

научно-технический отчет;

Разработка метода сборки геномных последовательностей на основе восстановления фрагментов по парным чтениям копия заявки на регистрацию программы для ЭВМ;

копия статьи для публикации в журнале из перечня ВАК;

3.5. ПЛАН ПРОВЕДЕНИЯ ПЯТОГО ЭТАПА ТЕОРЕТИЧЕСКИХ И ЭКСПЕРИМЕНТАЛЬНЫХ

ИССЛЕДОВАНИЙ

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

подача заявки на регистрацию программы для ЭВМ;

подготовка статьи для публикации в журнале из перечня ВАК.

Результаты работ пятого этапа:

научно-технический отчет;

копия заявки на регистрацию программы для ЭВМ;

копия статьи для публикации в журнале из перечня ВАК.

3.6. ПЛАН ПРОВЕДЕНИЯ ШЕСТОГО ЭТАПА ТЕОРЕТИЧЕСКИХ И ЭКСПЕРИМЕНТАЛЬНЫХ

ИССЛЕДОВАНИЙ

разработка рекомендаций по возможности использования результатов проведенной поисковой научно–исследовательской работы в реальном секторе экономики;

разработка рекомендаций по использованию результатов поисковой научно– исследовательской работы при разработке научно–образовательных курсов;

разработка научно–образовательных курсов на электронных носителях по новейшим направлениям науки и технологий;

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

Результаты работ шестом этапа:

итоговый научно-технический отчет.

ВЫВОДЫ ПО ГЛАВЕ

2. На первом этапе теоретических исследований разработана архитектура метода сборки геномных последовательностей.

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

4. ПРОВЕДЕНИЕ ПАТЕНТНЫХ ИССЛЕДОВАНИЙ

4.1. ПЕРЕЧЕНЬ СОКРАЩЕНИЙ, УСЛОВНЫХ ОБОЗНАЧЕНИЙ, СИМВОЛОВ, ЕДИНИЦ, ТЕРМИНОВ

ПО – Программное обеспечение.

DNA – Deoxyribonucleic acid, дезоксирибонуклеиновая кислота.

ДНК – дезоксирибонуклеиновая кислота.

РНК – рибонуклеиновая кислота.

ЭВМ – электронно-вычислительная машина.

ПЦР – полимеразная цепная реакция.

UML – Unified Modeling Language.

4.2. ОБЩИЕ ДАННЫЕ ОБ ОБЪЕКТЕ ИССЛЕДОВАНИЙ

– биокаталитические, биосинтетические и биосенсорные технологии;

– биомедицинские и ветеринарные технологии жизнеобеспечения и защиты человека и животных;

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

– клеточные технологии;

– биоинженерия;

– биоинформационные технологии» – тема «Разработка метода сборки геномных последовательностей на основе восстановления фрагментов по парным чтениям» (шифр «2011-1.2.1-201-007-050»), выполняемой в рамках Федеральной целевой программы «Научные и научно-педагогические кадры инновационной России» на 2009–2013 годы по государственному контракту № 16.740.11.0495, заключенному между Министерством образования и науки Российской Федерации и Государственным образовательным учреждением высшего профессионального образования «Санкт-Петербургский государственный университет информационных технологий, механики и оптики» на основании решения Конкурсной комиссии Министерства образования и науки Российской Федерации (протокол от 26.04.2011 г. № 3/0173100003711000032), а также для получения сведений об охранных и иных документах, которые могут препятствовать применению результатов данной НИР в Российской Федерации, и условиях использования таких документов.

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

работа с выходными данными секвенаторов второго поколения [14];

сравнительно низкие требования к используемым ресурсам компьютера, таким как оперативная память.

Патентный поиск проводился в соответствии с ГОСТ Р. 15.011-96 «Система разработки и постановки продукции на производство. Патентные исследования» [1]. Проверка патентоспособности проводимой научно-исследовательской работы осуществлялась на основе поиска патентных и других открытых документов, описывающих решения, максимально полно удовлетворяющие задаче исследования. Поиск патентной информации проводился в Бюллетене Федеральной службы по интеллектуальной собственности, патентам и товарным знакам Российской Федерации «Программы для ЭВМ, базы данных, топологии интегральных микросхем» (Роспатент, www.fips.ru), Бюро по Разработка метода сборки геномных последовательностей на основе восстановления фрагментов по парным чтениям патентам и товарным знакам США (USPTO, www.uspto.gov) и Европейского патентного бюро (EPO, ep.espacenet.com).

Патентный поиск проводился с 06 июня 2011 г. по 09 июня 2011 г.

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

сборка геномных последовательностей;

секвенирование нуклеотидных последовательностей.

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

В рамках патентного поиска производился анализ патентов, принадлежащих следующим категориям международной патентной классификации (рассматривались патенты, принадлежащие самому низкому указанному уровню):

Категория Содержание категории (рус.) Содержание категории (англ.) вычислений или обработки данных, or methods, specially adapted for specific вычислений или обработки данных, or methods, specially adapted for specific Кроме того, рассматривались следующие категории патентной классификации США (перевод на русский язык исполнителя отчета):

Категория Содержание категории (рус.) Содержание категории (англ.) Обработка данных: проектирование Разработка метода сборки геномных последовательностей на основе восстановления фрагментов по парным чтениям Симуляция неэлектрического Simulation Nonelectrical Device or System 703/ Также производился поиск без ограничения разделов классификаций по следующим ключевым словам: DNA, genome, assembly, sequencing.

Так как патенты, полностью удовлетворяющие поставленным перед исследованием требованиям, найдены не были, в качестве результата поиска рассмотрим наиболее близкие к теме исследования патенты:

1. Патент US 7939264 от 10.05.2011 «DNA sequencing method».

В патенте описывается новый способ секвенирования генома (стадия – получение ридов из непосредственно молекул ДНК) с помощью специфических энзимов. Утверждается, что скорость метода доходит до сотен оснований в секунду, а длина производимых им ридов достигает тысяч оснований. Данный патент затрагивает иную стадию процесса сборки генома, чем исследования, проводимые по контракту.

2. Патент US 7939256 от 10.05.2011 «Composition and method for nucleic acid sequencing».

Как и в предыдущем патенте, описывается способ получения информации непосредственно из молекул ДНК. Этот способ основан на контактировании обездвиженных цепочек ДНК с маркированными трифосфатами различных нуклеотидов. Как и предыдущий, данный патент затрагивает иную стадию процесса сборки генома, чем исследования, проводимые по контракту.

3. Патент US 7890268 от 15.02.2011 «De-novo sequencing of nucleic acids».

В данном патенте описан метод применения многостадийной масс-спектрометрии, ранее использовавшейся только для секвенирования по образцу, для секвенирования генома с нуля (de novo). Как и предыдущие, данный патент затрагивает иную стадию процесса сборки генома, чем исследования, проводимые по контракту.

4. Патент US 7881873 от 01.02.2011 «Systems and methods for statistical genomic DNA based analysis and evaluation».

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

5. Патент US 7835871 от 16.11.2010 «Nucleic acid sequencing system and method».

В этом патенте описывается секвенатор компании Illumina Inc., данные, производимые которым (короткие чтения), используются методом, исследуемым в рамках работ по контракту, для получения полного генома.

6. Патент US 7767400 от 03.08.2010 «Paired-end reads in sequencing by synthesis».

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

7. Патент US 7720613 от 18.05.2010 «Method for sequencing nucleic acids».

В этом патенте описывается способ секвенирования малых отрезков ДНК (до 15 оснований) путем сравнения спектра секвенируемого отрезка со спектром предполагаемого значения, модификацией не менее одного основания предполагаемого значения и повторения описанного процесса до совпадения секвенируемого и предполагаемого отрезка. Метод, описанный в данном патенте, невозможно применить для секвенирования полного генома в силу его неэффективности.

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

8. Патент US 7144699 от 05.12.2006 «Iterative resequencing».

Разработка метода сборки геномных последовательностей на основе восстановления фрагментов по парным чтениям В этом патенте описывается способ итеративного приближения для секвенирования последовательности нуклеотидов с использованием уже секвенированной и близкой к ней базовой последовательности. В отличие от данного патента, результаты исследований, проводимых по контракту, позволят секвенировать геном с нуля (de novo).

9. Патент US 6223128 от 24.04.2001 «DNA sequence assembly system».

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

Сводная информация по основным различиям рассмотренных патентов и задач проверяемого на патентоспособность исследования приведена в табл. 5.

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

Таблица 5. Отличия описываемых в патентах задач от темы исследования US US US US US US US US US

4.4. ИССЛЕДОВАНИЯ ПРОГРАММ ДЛЯ ЭВМ

Разработка метода сборки геномных последовательностей на основе восстановления фрагментов по парным чтениям Таблица 6. Результаты рассмотрения данных о регистрации программ для ЭВМ 2008614430 ПЦР-Дизайн Назначение программы – выбор Выполняет иную задачу 2008612975 BioUML Enterprise 2008612150 Программа для Предназначена для проведения При работе использует уже 2009615258 Программа, Программа предназначена для Выполняет иную задачу 2009610058 Программа для Программа предназначена для При работе использует 2009610743 Сравнение хромосом Программа предназначена для При работе использует уже 2009610744 Поиск нуклеотидных Программа предназначена для При работе использует уже Разработка метода сборки геномных последовательностей на основе восстановления фрагментов по парным чтениям 2009610745 Графическое Программа предназначениа для При работе использует уже человека (MegaDNA) плотности их распределения.

2010616107 Автоматизированный Программа позволяет эксперту При работе использует уже геномов из dbSNP индивидуальных геномов, 2010611465 Аналитическая Программа представляет собой При работе использует уже однонуклеотидных человека определенных 2009615516 Универсальная Программа предназначена дял При работе использует уже анализа структуры информации с использованием 2009615517 Универсальная Программа предназначениа для При работе использует уже 2010616973 РегистрЛабПЦР Программа предназначена для Использует данные, Разработка метода сборки геномных последовательностей на основе восстановления фрагментов по парным чтениям Из изложенного следует, что поиск не выявил наличия программ для ЭВМ, реализующих требуемую функциональность и тем самым препятствующих проведению исследований по теме «Разработка метода сборки геномных последовательностей на основе восстановления фрагментов по парным чтениям».

4.5. ИССЛЕДОВАНИЯ НЕПАТЕНТНЫХ ИСТОЧНИКОВ

Исследования в области секвенирования и сборки геномов различных видов живых существ ведутся в мире с 70–80-х годов XX века. Одним из наиболее значительных проектов в этой области «Геном человека» (Human Genome Project) был запущен в 1990 году и завершен в 2003 году получением геномной последовательности человека. В рамках этого проекта для секвенирования использовались так называемые технологии первого поколения [9].

В середине первого десятилетия XXI века широкое распространение получили технологии секвенирования второго поколения, разработанные, например, компанией Illumina. Эти технологии позволяют существенно быстрее и дешевле получать на порядок большие объемы данных о геномной последовательности. Их недостатком является то, что длины чтений при использовании составляют 80–100 нуклеотидов, а не 500–1000, как при использовании технологий второго поколения [14] Технологии секвенирования второго поколения активно развиваются, поэтому требуется постоянная разработка новых алгоритмов сборки генома по данным секвенирования и совершенствование существующих.

Одной из наиболее часто используемых при сборке генома математических моделей является так называемый граф де Брюина. На его использовании основаны следующие программные средства (со ссылками на описывающие их статьи): Velvet [12], ALLPATHS [1], AbySS [10], SOAPdenovo [4], EULER [8].

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

В статье [10] изложен подход к сборке контигов в программном средстве ABySS. Этот подход состоит из двух этапов:

сборка контигов без учета парной информации;

разрешение неоднозначностей с помощью парной информации и наращивание контигов.

В основе всего подхода лежит распределенный граф де Брюина [6].

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

На втором этапе между контигами устанавливается связи, используя парную информацию.

Пара чтений называется связывающей два контига, если первое чтение картируется на первый контиг, а второе – на второй. Между двумя контигами устанавливается связь, если число связывающих их чтений больше некоторой константы p (по умолчанию используется p = 5). Для каждого контига Ci строится множество связанных с ним контигов Pi. Затем в графе связей контигов ищется уникальный путь, проходящий через все контиги из Pi. В качестве ограничений при поиске выступают оценка на расстояния между контигами на основе принципа максимального правдоподобия и эвристическая оценка на число посещенных вершин. После того, как поиск таких путей для каждого контига завершился (успешно или нет), согласующиеся пути сливаются, образуя конечные контиги.

Алгоритм, лежащий в основе сборщика ALLPATHS изложен в статье [1]. Он также основан на графе де Брюина и состоит из нескольких этапов.

Первым этапом является создание начального приближения контигов. Для этого, как и в [10], рассматриваются последовательности смежных однозначных ребер, которые и объявляются приближением контигов.

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

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

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

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

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

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

Алгоритм работы Velvet изложен в статье [12].

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

Зная распределение длин пропусков в парных чтениях можно выделить длину L такую, что число парных чтений, имеющих пропуск длиннее L ничтожно мало. Можно выделить «длинные»

вершины – вершин, длины которых не меньше чем L. Затем на основе парных чтений выделяются парные «длинные» вершины, связанные несколькими парными чтениями (рис. 7). Если после «длинной» вершины может следовать несколько «длинных» вершин, то они называются неоднозначными. Все узлы, на которые картируется чтение, парное к которому картируется на однозначную «длинную» вершину, помечаются. После этого уникальные узлы последовательно наращиваются, добавлением помеченных узлов, связанных с текущим. Этот процесс продолжается до тех пор, пока не встречается узел, у которого нет продолжения или есть несколько вариантов продолжения. Если несколько «длинных» вершин последовательно соединились такими путями, то они объединяются в контиг.

Разработка метода сборки геномных последовательностей на основе восстановления фрагментов по парным чтениям Способ сборки, используемый в SOAPdenovo, описан в статье [4].

Как и многие другие сборщики из коротких чтений SOAPdenovo использует граф де Брюина.

После исправления ошибок пути, не содержащие вершин с ветвлениями, объявляются первоначальным приближением контигов (рис. 8).

Затем производится картирование парных чтений на контиги. Между двумя контигами устанавливается порядок и оценивается расстояние между ними, если их соединяют как минимум три пары чтений. Далее наборы контигов с совместимыми связями линеаризуются, образуя скэффолды.

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

В статье [8] изложены основы работы набора алгоритмов EULER.

Разработка метода сборки геномных последовательностей на основе восстановления фрагментов по парным чтениям Сборщик EULER использует для сборки сведение к задаче о поиске в графе повторов Эйлерова суперпути – пути проходящем через все ребра и содержащем в качестве подпутей все пути из наперед заданного множества P [8]. Эта задача, в свою очередь, сводится к задаче поиска Эйлерова пути.

Изначально в качестве множества P использовались пути, соответствующие чтениям. Затем проводились преобразования, упрощающие граф. После этого рассматривалась каждые парные чтения (r1, r2) и искался путь, соединяющий r1 и r2 и имеющий длину около ожидаемой, определенной из априорного распределения длин. Если такой путь находился единственный, то он добавлялся в множество P. Этот процесс повторялся до тех пор, пока граф менялся.

В статье [8] предлагается способ учета и тех парных чтений, для которых нашлось несколько путей. Пусть для парных чтений (readstart, readend) нашлось несколько путей (рис. 9). Обозначим за estart и eend ребра, в которых начинаются и заканчиваются readstart и readend соответственно. Для каждого пути p, соединяющего readstart и readend, рассмотрим величину support(estart, eend, p) – число парных чтений, поддерживающих этот путь – таких парных чтений (r1, r2), что одно из них картируется на ребро estart или eend, а другое на путь p. Из всех путей выбирается путь с максимальным значением support, если оно не меньше некоторого порогового значения MinSupport.

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

4.6. ОТЛИЧИЯ ПРОВОДИМОГО ИССЛЕДОВАНИЯ

Подавляющее большинство зарегистрированных программ для ЭВМ, в той или иной мере работающих с генетическим материалом, используют ранее собранные последовательности ДНК (2008612150, 2009610058, 2009610743, 2009610744, 2009610745, 2010616107, 2010611465, 2009615516, 2009615517). Остальные программы либо работают с оптическими данными чтений ДНК (2010616973), либо используются для хранения и отображения данных (2008612975), планирования химических экспериментов (2008614430) или контроля синтеза ДНК (2009615258).

Разработка метода сборки геномных последовательностей на основе восстановления фрагментов по парным чтениям Одним из недостатков, которым обладают программные средства, описанные в статьях [1, 4, 8, 12], является большой объем оперативной памяти, необходимый им для сборки генома, сходного по размерам с геномом человека (203 миллиарда нуклеотидов). Так, например, SOAPdenovo [4] необходимо порядка 140 гигабайт оперативной памяти, а ABySS [10] – 21 компьютер с 16 гигабайтами каждый (всего – 336 гигабайт). Такие затраты памяти обусловлены наличием ошибок секвенирования в исходных данных (такие ошибки ведут к увеличению размера графа де Брюина), а также неоптимальным методом хранения этого графа. Другим недостатком существующих методов сборки является отсутствие внутреннего контроля качества сборки.

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

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

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

1. ГОСТ Р. 15.011-96 «Система разработки и постановки продукции на производство. Патентные исследования».

2. Патентный закон РФ. http://www.legal-support.ru/information/laws/intellect/patent-law.html.

3. Watson J.D., Crick F.H. Molecular structure of nucletic acids; a structure for deoxyribose nucleic acid // Nature. Vol. 171. 1953, pp. 737–738.

4. Sanger F., Nicklen S., Coulson A. DNA sequencing with chain-terminating inhibitors // Proc. Natl. Acad.

Sci. USA. Vol. 74. 1977, pp. 5463–5467.

5. Staden R. A strategy of DNA sequencing employing computer programs // Nucleic Acids Res. Vol. 6.

1979, pp. 2601–2610.

6. Pevzner P. 1-Tuple DNA sequencing: computer analysis // J. Biomol. Struct. Dyn. 1989. V. 7, pp. 63–73.

7. Pevzner P. Computational molecular biology: an algorithmic approach. MIT Press, 2000.

8. Pevzner P., Tang H., Waterman M. An Eulerian path approach to DNA fragment assembly / Proc. Natl.

Acad. Sci. USA. Vol. 98. 2001, pp. 9748 – 9753.

9. International Human Genome Sequencing Consortium. Initial sequencing and analysis of the human genome // Nature. Vol. 409. 2001, pp. 860 – 921.

10. Butler J., MacCallum I., Kleber M., Shlyakhter I., Belmonte M., Lander E., Nusbaum C., Jaffe D.

ALLPATHS: de novo assembly of whole-genome shotgun microreads // Genome Res. 2008. No. 5, pp. 810– 820.

11. Zerbino D., Birney E. Velvet: algorithms for de novo short read assembly using de Bruijn graphs // Genome Res. No. 5, Vol. 18. 2008, pp. 821–829.

Разработка метода сборки геномных последовательностей на основе восстановления фрагментов по парным чтениям 12. Simpson J., Wong K., Jackman S., Schein J., Jones S., Birol I. ABySS: a parallel assembler for short read sequence data // Genome Res. 2009. No. 6, pp. 1117 – 1123.

13. Li R., Zhu H., Ruan J., Qian W., Fang X., Shi Z., Li Y., Li S., Shan G., Kristiansen K., et al. De novo assembly of human genomes with massively parallel short read sequencing // Genome Res. 2010, No. 6, pp. 265 – 272.

14. Schatz M., Delcher A., Salzberg S. Assembly of large genomes using second-generation sequencing // Genome Res. 2010. No. 6, pp. 295 – 315.

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

ЗАКЛЮЧЕНИЕ

выполнен аналитический обзор;

проведены патентные исследования;

выбран и обоснован оптимальный вариант проведения исследований;

выбрана архитектура метода сборки геномных последовательностей;

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

Аналитический обзор был выполнен по следующим направлениям:

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

форматы представления геномных данных.

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

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

алгоритм восстановления фрагментов геномной последовательности по набору парных чтений.

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

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

СПИСОК ЛИТЕРАТУРЫ

Vol. 18. No. 5, pp. 810 – 820.

2. Chaisson M. J., Brinza D., Pevzner P. A. De novo fragment assembly with short mate-paired reads:

Does the read length matter? // Genome Research. 2009. Vol. 19. No. 2,. pp. 336 – 346.

3. FASTA format. http://zhanglab.ccmb.med.umich.edu/FASTA/ 4. Li R., Zhu H., Ruan J., Qian W., Fang X., Shi Z., Li Y., Li S., Shan G., Kristiansen K., Li S., Yang H., Wang J., Wang J. De novo assembly of human genomes with massively parallel short read sequencing // Genome Research. 2010. Vol. 20, No. 2? pp. 265 – 272.

http://www.ncbi.nlm.nih.gov/Traces/trace.cgi?cmd=show&f=formats&m=doc&s=format 6. Cock P., Fields C., Goto N., Heuer M., Rice P. The Sanger FASTQ file format for sequences with quality scores, and the Solexa/Illumina FASTQ variants // Nucleic Acids Research, 2010, Vol.

38. No. 6, pp. 1767 – 1777.

7. Pevzner P. A., Tang H., Waterman M. S. An eulerian path approach to DNA fragment assembly / Proc. Natl Acad Sci U S A. 2001. Vol. 98. No. 17, pp. 9748 – 9753.

8. Phred -Quality Base Calling. http://www.phrap.com/phred/ 9. Sundquist A., Ronaghi M., Tang H., Pevzner P., Batzoglou S. Whole-Genome Sequencing and Assembly with High-Throughput, Short-Read Technologies // PLosS ONE. 2007.

10. Simpson J. T., Wong K., Jackman S. D., Schein J. E., Jones S. J. M., Birol I. Abyss: a parallel assembler for short read sequence data // Genome Res. 2009. Vol. 19, No. 6, pp. 1117 – 1123.

11. The SAM Format Specication. http://samtools.sourceforge.net/SAM1.pdf 12. Zerbino D. R., Birney E. Velvet: algorithms for de novo short read assembly using de Bruijn graphs // Genome Res. 2008. Vol. 18. No. 5, pp. 821 – 829.

13. UCSC Genome Browser: BAM Track Format. https://cgwb.nci.nih.gov/goldenPath/help/bam.html