Бесплатный автореферат и диссертация по биологии на тему

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

ВАК РФ 03.01.03, Молекулярная биология

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

авах рукописи

КАСЬЯНОВ Артем Сергеевич

НОВЫЕ МЕТОДЫ ОБРАБОТКИ ДАННЫХ, ПОЛУЧЕННЫХ С ПОМОЩЬЮ СОВРЕМЕННЫХ ТЕХНОЛОГИЙ СЕКВЕНИРОВАНИЯ, ДЛЯ РЕШЕНИЯ ЗАДАЧ АНАЛИЗА ЭКСПРЕССИИ ГЕНОВ

03.01.03 - Молекулярная биология

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

е ДЕК 2012

Москва 2012

005056850

005056850

Работа выполнена в Лаборатории биоинформатики и системной биологии Федерального государственного бюджетного учреждения науки Института молекулярной биологии им. В.А. Энгельгардта Российской академии наук.

Научный руководитель:

Официальные

оппоненты:

Заведующий Лабораторией биоинформатики и системной биологии Федерального государственного бюджетного учреждения науки Института молекулярной биологии им. В.А. Энгельгардта Российской академии наук, доктор физико-математических наук, профессор

Туманян В.Г.

Профессор факультета биоинженерии и биоинформатики Федерального государственного бюджетного учреждения высшего профессионального образования «Московский государственный университет имени М.В. Ломоносова», кандидат физико-математических наук, доктор биологических наук

Миронов A.A.

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

Артамонова И.И.

Ведущая

организация

Государственный научный центр Российской Федерации ФГУП Государственный научно-исследовательский институт генетики и селекции промышленных микроорганизмов

Защита состоится « Об » (Шиь&ЬЯ- 2012 г. в

002.^35.01 при Федеральном государственном

Ж

часов на заседании

Диссертационного Совета бюджетном учреждении науки Институте молекулярной биологии им. В.А. Энгельгардта Российской академии наук по адресу: 119991, г. Москва, ул. Вавилова 34,

С диссертацией можно ознакомиться в библиотеке Федерального государственного бюджетного учреждения науки Института молекулярной биологии им. В.А. Энгельгардта Российской академии наук. Автореферат разослан «{9_» М/У1?-&^?2012 г.

Ученый секретарь диссертационного совета

кандидат химических наук /] <\.М. Крицын

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Технологии секвенирования нового поколения наряду со своей основной задачей, т.е. получением последовательностей генома, позволяют решать задачи, связанные с анализом экспрессии генов (RNA-Seq), специфического ДНК-белкового взаимодействия и структуры хроматина (ChlP-Seq), метилирования ДНК (Methyl-Seq). В результате получается, что задачи анализа биологических макромолекул, которые до сих пор решались различными методами (микрочипы, футпринтинг и т.д.) можно решить с помощью технологий секвенирования нового поколения, что является значительным преимуществом, так как оборудование для секвенирования стремительно дешевеет. Специфика применения секвенаторов нового поколения для решения различных биологических задач заключается в методах подготовки образцов и последующей обработке данных с помощью методов биоинформатики. При разработке алгоритмов обработки данных секвенирования нового поколения (next-generation sequencing, NGS) имеют место как чисто алгоритмические сложности, связанные с огромным объемом данных, так и специфические сложности связанные с характером биологической задачи. Хотя методы секвенирования нового поколения возникли совсем недавно, было разработано огромное количество специфичных для них алгоритмов обработки данных; однако вследствие быстро растущих объемов данных и непрерывного развития технологий эффективность существующих алгоритмов недостаточна. Более того, многие существующие алгоритмы были разработаны под решение конкретных задач и неприменимы в других условиях. Таким образом, обработка данных остается лимитирующим фактором, ограничивающим использование технологий секвенирования. В результате разработка новых

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

В отличии от секвенаторов, построенных на основе классического метода Сенгера, технологии секвенирования нового поколения дают большое количество сравнительно коротких нуклеотидных последовательностей. На данный момент наиболее распространенными технологиями высокопроизводительного секвенирования являются секвенирование путем синтеза с обратимой терминацией (Illumina), пиросеквенирование (Roche), секвенирование путем лигирования (SOLiD), полупроводниковое секвенирование (Ion torrent). Длина чтений (последовательностей, полученных в результате секвенирования), выдаваемых секвенаторами, построенными на основе этих технологий, варьируется от 30 п.н. до 700 п.н., а классический метод Сенгера дает чтения длиной 1000 п.н.. Вследствие этого программное обеспечение, предназначенное для обработки данных, полученных с секвентаров по Сэнгеру, не эффективно при работе с данными нового поколения. Кроме того, вследствие постоянного роста производительности секвенаторов, объем обрабатываемых данных постоянно растет. Данная ситуация осложняется постоянной доработкой существующих технологий, а также появлением абсолютно новых технологических платформ, что, в частности, приводит к изменению шумовых характеристик получаемых данных. Данные трудности постоянно стимулируют создание новых методов обработки NGS данных, потребность в которых на данный момент полностью не удолетворена.

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

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

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

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

2. Аппробация программного обеспечения, разработанного на основе предложенных методов, на базе проекта de novo секвенирования транскриптомов двух видов гречихи F.escalentum и F.talaricum.

3. Разработка методов и алгоритмов для de novo сборки транскриптомов полиплоидных организмов.

4. Аппробация программного обеспечения, разработанного на основе предложенных методов, на базе проекта de novo секвенирования транскриптома тетраплоида Capsella bursa-pastoris.

5. Разработка методов подготовки первичных данных для последующего анализа результатов ChlP-Seq экспериментов для выявления участков ДНК, специфически связывающих белки - регуляторы транскрипции.

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

Предложены новые подходы для первичной обработки ChIP-Seq данных. Предложен новый метод для разделения гаплоидных транскриптов при сборке de novo транскриптомов полиплоидов. Разработанные методы позволят повысить эффективность анализа экспрессии генов в RNA-Seq и ДНК-белкового узнавания в ChIP-Seq экспериментах.

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

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

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

Был разработан конвейер для сборки de novo транскриптома полиплоидного организма с выделением гаплоидных вариатов транскриптов. С использованием данного программного обеспечения была проведена сборка de novo и анализ транскриптома тетраплоидного растения Capsella bursa-pastoris.

Программы и методы, составляющие материал настоящей диссертации использовались при выполнении работ по ГК от 13 июля 2011 года №07.514.11.4005 «Создание программного комплекса, предназначенного для обработки данных, полученных на секвенирующих установках нового поколения, включая сборку протяженных последовательностей и коррекцию ошибок секвенирования».

Апробация работы. Результаты работы были представлены на конференции «Meeting on Advances and Challenges of RNA-Seq Analysis» в городе Халле, Германия в июне 2012 года, на конференции «Bioinformatics of Genome

Regulation and StructureVSystems Biology — BGRS\SB-2012» в г. Новосибирске в июле 2012, на конференции «11th European Conference on Computational Biology» в г. Базель, Швейцария в сентябре 2012,

Публикация. Материалы диссертационной работы отражены в 5 публикациях, из них 3 статьи в рецензируемых журналах и 3 публикации в рецензируемых трудах конференций.

Структура и объем диссертации. Диссертационная работа состоит из введения, 4 глав, заключения и списка литературы содержащего 104 ссылки. Работа изложена на 104 страницах, содержит 20 рисунков и 17 таблиц.

СОДЕРЖАНИЕ РАБОТЫ

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

Представлен обзор основных технологий секвенирования 2-го и 3-го поколения, таких как технологии Illumina

[http://www.illumina.com/pages.ilmn?ID=203], 454/Roche

[http://www.454.com/enablingtechnology/the-system.asp], SOLiD

[http://marketing.appliedbiosystems.com/images/Product/SolidKnowledge/ flash/102207/solid.html], PacBio [www.pacificbiosciences.com], Helicos [www.helicosbio.com], IonTorrent [www.iontorrent.com]. Приведены сравнительные характеристики технологий [Pettersson Е. et al., 2009].

Алгоритмы сборки можно разбить на две большие группы: алгоритмы на основе де Брейн графов и алгоритмы на основе «перекрытие-расположение-консенсус» (ПРК, т.н. overlap-layout-consensus, OLC [Myers EW et al., 1995]) подхода. К программам, основанным на алгоритмах на основе де Брейн графов относятся следующие сборщики - EULER [Pevzner Р.А. et al., 2001], VELVET [Zerbino D.R. et al., 2008], ABYSS [Simpson J.T. et al., 2009], ALLPATHS [Butler J. et al., 2008], SOAPdenovo [Li R. et al., 2009]. К программам основанным на алгоритмах на основе ПРК подхода относятся следующие сборщики -NEWBLER [Margulies M. et al., 2005], Celera Assembler [Myers EW et al., 2000], ARACHNE [Batzoglou S. et al., 2002], SHORTY [Hossain MS. et al., 2009].

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

Глава 2. Разработка алгоритмов для анализа дифференциальной экспрессии генов, по данным севенирования нового поколения транскриптомов близких видов, последовательности полных геномов которых неизвестны.

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

Введем понятие «Сравнение транскриптомов двух видов, последовательности полных геномов которых неизвестны, на основе данных секвенирования» для этого нам понадобиться ряд дополнительных определений.

а=(А|С|Т|С)* (2.1)

А= {аьа2, а3,...,а„} (2.2)

Строки, состоящие из четырех символов, будем обозначать строчными латинскими буквами (2.1), а множество строк прописными латинскими буквами (2.2).

Введем понятие (ш,1,с1)-эквивалентности двух строк. Две строки считаются (т,¡^-эквивалентными в случае если одну строку можно преобразовать в другую с введением не более т замен символов, вставкой не более 1 символов и удалением не более с1 символов. Обозначать это отношение

mJ.il

будем символом ~ .

Введем понятие (т,!,(1)-эквивалентности двух множеств. Множество А считается (т,¡^-эквивалентным множеству В в случае если для каждой строки из множества А можно найти (т,1,^-эквивалентную в множестве В.

Данное отношение не является коммутативным, в отличие от (m,i,d)-эквивалентности двух строк.

Транскриптом можно считать множеством строк, соответственно процесс секвенирования можно представить в виде операции преобразующей множество строк, соответствующее транскриптому в множество (m,i,d)-эквивалентное множеству подстрок строк принадлежащих множеству, соответствующему транскриптому. Будем обозначать такое отбражение символом SEQ.

Пусть Sa - это множество задаваемое следующим образом:

Sa = SEQ(A) (2.3)

Также введем множества ЕА,в; UA; UB следующим образом:

Еа,в = {а, Ь | а е А, Ь е В, аЬ) (2.4)

Ua=A\Ea,b (2.5)

UB = В \ Еа,в (2.6)

Введем алгоритмы equal, unique следующим образом Алгоритм equal, принимая на вход множества SA и Sb, конструирует множество ЕАВ Алгоритм unique, принимая на вход множества SA и SB, конструирует множество UA. Задача «Сравнение транскриптомов двух видов, последовательности полных геномов которых неизвестны, на основе данных секвенирования», для множеств А и В состоит в нахождении ЕАВ, UA, Ub при наличии только множеств SA и SB.

Для решения данной задачи требуется построение алгоритмов equal и unique.

Для большей части отображений SEQ (сюда относятся и большинство практически важных случаев) не удастся построить точное решение задачи «Сравнение транскриптомов двух видов, последовательности полных геномов которых неизвестны, на основе данных секвенирования», так как получающиеся в результате их применения к исходному множеству множества не содержат необходимой информации. Поэтому имеет большое практическое значение отыскание приближенных решений этой задачи Ел в, ил, ив таких что для них существуют подмножества, являющиеся подмножествами точных решений:

- m.i.d

ЭС:СсЕа.в,С ~ ЕЛ„ (2,9)

30:0£иА,0~иА (2.10)

ЗЕ:Есив,Ет~4ив (2.11)

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

Рисунок 1. Программный комплекс для анализа дифференциальной экспрессии

генов двух видов

На основе разработанного алгоритма был разработан программный комплекс (рисунок 1) для анализа дифференциальной экспрессии двух видов, последовательности полных геномов, которых неизвестны, на основе результатов секвенирования их транскрнптомов с использованием секвенаторов нового поколения:

1. На первом этапе производится сборка чтений, полученных в результате секвенирования транскрнптомов, с использованием программы MIRA [Chevreux В. et al., 1999]. В результате получаем две сборки транскрнптомов.

2. Полученные на предыдущем этапе сборки картируются друг на друга с использованием программы BLAST [Altschul S. et al., 1990].

3. Из полученных на предыдущем этапе картирований получаем три набора данных:

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

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

• Контиги, найденные в обеих сборках.

Описанный пайплайн был использован для сравнительного анализа транскриптомов двух близких видов гречихи F.esculentum и F.tataricum. Результаты данного исследования были опубликованы в работе [1]. Секвенирование и сборка транскриптомов двух видов гречихи. Для секвенирования использовались нормализованные библиотеки кДНК растений F.esculentwn и F.tataricum. Полученные образцы были секвенированы с использованием Roche GS FLX. Было получено 266782 ридов для F.esculentum и 229031 ридов для F.tataricum. Средняя длина ридов - 349 п.н. для F.esculentwn и 341 п.н для F.tataricum.

Для удаления полиА последовательностей использовался программный пакет SeqCIean [http://compbio.dfci.harvard.edu/tgi/software/]. К сожалению данный программный пакет показал полную несостоятельность при применении его для удаления адаптерных последовательностей, поэтому для этих целей автором был разработан новый алгоритм, основанный на получении парных выравниваний последовательности чтения и адаптерной последовательности с пределом по количеству несовпадений (замен, вставок, делеций) в 4 символа и на основе него была разработана специализированная программа для удаления адаптерных последовательностей.. На следующем этапе для анализа предобработанных данных применялся разработанный программный комплекс. Результаты первого этапа его выполнения приведены в таблице 1.

Таблица 1. Характеристика исходных ридов и контигов.

Fagopyrum esculentum Fagopyrum tataricum

1 2 3

Число ридов 266782 229031

Средняя длина(мин-макс) 349(40-971) 340(40-976)

Число контигов 25435 25401

Продолжение таблицы 1.

1 2 3

Средняя длина (мин-макс) 698,4(42-3607) 703(46-3298)

Число ридов на контиг, среднее(мин-макс) 8,2(2-224) 7,5(2-295)

Аннотация собранных транскриптомов. Результаты первого этапа работы программного комплекса были использованы для проведения аннотации. Белковые последовательности, соответствующие контигам были выравнены с неизбыточной белковой базой данных (пг) с порогом на E-value 10"6. две трети из них имели существенное совпадение. Наиболее значительное совпадение наблюдалось с Vitis vinifera [Jaillon О. et al., 2007], Populus trichocarpa [Tuskan G.A. et al., 2006], Ricinus communis

[http://gsc.jcvi.org/projects/msc/ricinus_communis/].

Был проведен автоматический поиск открытых рамок чтения (ORF - open read frame) с помощью The ORF Predictor [Min X.J. et al., 2005]. Предсказано, что в 98% контигов в обоих видах гречихи были найдены открытые рамки считывания длиной более 90 п.н.

Для проведения функциональной аннотации использовалась BLAST2GO. Для обоих видов было аннотировано 60% контигов. Контиги, не имеющие значительного количества BLASTX хитов, но имеющие ORF длиной более 90 п.н., были выравнены с последовательностями из базы данных Pfam. Значительное совпадение было найдено для 1795 последовательностей F.esculentum и 1775 последовательностей F.talaricum.

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

В качестве предполагаемых дифференциально экспрессируемых генов (ПДЭГ) были взяты контиги из первого и второго наборов данных, являющихся результатами выполнения рассматриваемого в данном разделе программного комплекса. Всего было найдено 4245 ПДЭГ для Кезси1еп1ит и 4255 ПДЭГ для КШ1апсит из них только для 1132 контигов Г.ехси1еп1шп и 1588 контигов /■'. шкгпсчт не было найдено совпадений в

GenBank[http://www.ncbi.nlm.nih.gov/genbank/] и

GeneOntologies[http://www.geneontology.org/] аннотации. Распределение вО категорий в ПДЭГ множествах, соответствующих обоим видам, сильно похоже и только небольшое их количество уникально для двоих видов. Дальнейший анализ показал, что среди уникальных генов присутствуют гены ретротранспозонов и гены, участвующие в биосинтезе Сахаров.

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

Глава 3. Разработка методов подготовки первнчных данных для последующего анализа результатов ChIP-Seq экспериментов для выявления участков ДНК, специфически связывающих белки -регуляторы транскрипции.

Большое значение для анализа экспресии генов имеет определение участков ДНК, специфически связывающих белки - регуляторы транскрипции. Знание этих участков позволяет более точно понять каким образом производится регуляция экспрессии генов. Оценка особенностей соответствующих областей ДНК позволяет более точно выявить гены-мишени регуляторных белков на уровне транскрипции.

9

связанный изучаемый белок

геномная

ДНК

3' секвестрование концов

<• иммуноп реабилитированного ' ДНК фрагмента

Картирование

ридов на референсньЛ геном

Обнаружение сайтов транскрипционных факторов

Рисунок 2 Структура СЫР-8ец эксперимента

Процесс обработки данных СЫР-Бея эксперимента состоит из следующих основных этапов:

1) Картирование чтений на референсный геном.

2) Построений профилей покрытия.

3) Нахождение областей связывания транскрипционных факторов. Второй и третий этап обработки данных достаточно хорошо проработаны

и разработано достаточно большое количество программных продуктов решающих эти задачи [ гатЬеШ, Р й а!., 2012]. Первый же этап достаточно сильно зависим от типа секвенирующей установки и вследствие постоянных изменений и обновлений вносимых в секвенирующее оборудование на данном этапе возникает потребность в разработке дополнительных алгоритмов предобработки данных и анализа качества картирований.

Был разработан набор алгоритмов и программных средств для предобработки первичных данных СЫР-Бец эксперимента. Разработанное программное обеспечение можно разделить на две категории:

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

2) Программное обеспечение для анализа качества и проведения классификации результатов выполнения парного выравнивания. Кроме того, разработан модуль для запуска программ для парного

выравнивания ридов В\¥А [1л Н. е1 а1., 2009] и Во\УЙе [Ьа^теас! В. Е1 а1.,

2010], полученных с использованием секвенирующих установок фирмы Illumina.

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

1) Ы50(взвешинная медианная длина чтений);

2) Максимальная длина чтения;

3) Средняя и медианная длины чтения;

4) Полное число чтений;

5) Среднее качество набора чтений;

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

[http://www.girinst.org/repbase/], результаты предсказания тандемных повторов программой TandemSWAN [Valentina Boeva et al., 2006], а также существующая аннотация референсной последовательности. Данный программный модуль использовался при выполнении работ [2,3].

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

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

1) Доля ридов, для которых удалось найти парное выравнивание с референсом.

2) Среднее число замен, делеций и вставок.

3) Максимальное число замен, делеций и вставок в одном выравниваний.

4) Минимальное число замен, делеций и вставок в одном выравнивании.

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

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

Глава 4. Разработка алгоритма выделения паралогичных генов при сборке диплоидных геномов растений из данных секвенирования транскриптома de novo

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

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

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

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

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

Введем ряд определений. Обозначим длину строки а, как 1(a). Две строки а и b считаются сильно (т,¡^-эквивалентными, если m+i+d « min(l(a),l(b)). Паралогичными последовательностями будем считать строки которые сильно (т,¡^-эквивалентны. Множество кортежей, состоящих из строк из множества А, которые являются попарно паралогичными последовательностями, обозначим как АР.

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

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

Для приближенного решения задачи «Определения н разделения последовательностей транскриптов паралогичных генов для видов для которых неизвестны полногеномные последовательности» мы предложили алгоритм de novo сборки транскриптомных последовательностей, который позволяет разделить гаплоидные транскрипты после проведения сборки с использованием программ-сборщиков. Данный алгоритм был опробован при сборке и анализе результатов секвенирования транскриптома тетраплоида Capsella bursa past oris [5,6].

Для секвенирования было взяты образцы из третьего поколения потомков одного самоопыляемого растения. Было подготовлено две библиотеки кДНК. Первая библиотека получена из цветков и соцветий и была севенирована с

использованием Roche/454 GS FLX и Illumina Hiseq 2000. Вторая библиотека была получена из растений подвергавшимся различным стрессовым воздействиям (холод, сильное освещение и т.д.). Всего было получено около 50 миллионов чтений, полученных с помощью секвенирующей установки фирмы Illumina, и I миллион чтений, полученных с помощью секвенирующей установки фирмы Roche. Была проведена сборка транскриптомных последовательностей на основе этих чтений с использованием трех сборщиков MIRA, velvet и clc genomics workbench

[http://www.clcbio.com/index.php?id=1240]. Было получено 26 сборок с числом контигов от 27463 до 243232. Ни в одной из сборок не удалось найти достаточно удачного разделения паралогичных генов на гаплоиды. При анализе сборок была обнаружена следующая закономерность (рис.5).

Картирование ридов на сборку

...gctgcactgtactggctgggcttgacgtctctgtggcatctgcttgcatctgcaattcca.....

...gctgcactgtactggctgggcttgacgtctctgtggcatctgcttgcatctg

...gctgcactgtactggctgggcttgacgtctctgtggcatctgcttgcatct

...gctgcactgtactggctgggcttgacgtctctgtggcatctgcttgcatc

...gctgcactgtactggctgggcttgacgtctctgtggcatctgcttgcat

...gctgcactgtactggctgggcttgacgtctctgtggcatctgcttgca

...gctgcactgtactggctgggcttgacgtctctgtggcatctg

...gctgcactgtactggctgggcttgacgtctctgttgcatc

...gctgcactgtactggccgggcttgacgtctctgttgca

...gctgcactgtactggccgggcttgacgtctctgttgc

...gctgcactgtactggccgggcttgacgtctctgttg

actgtactggccgggcttgacgtctctgttgcatctgcttgcatctgcaattcca...

gtactggccgggcttgacgtctctgttgcatctgcttgcatctgcaattcca...

actggccgggcttgacgtctctgttgcatctgcttgcatctgcaattcca...

ctggccgggcttgacgtctctgttgcatctgcttgcatctgcaattcca...

Рис. 5. Участок выравнивания ридов с контигом из сборки.

Можно заметить, что контиги содержат набор позиций, при картировании на которые чтений наблюдается однонуклеотидный полиморфизм (SNP, single nucleotide polymorphism), причем данные позиции можно связать с помощью, соответствующих им ридов. Для этой цели был разработан алгоритм (рис.6) и на основе него была создана программа для выделения паралогичных вариантов. В результате работы разработанного программного обеспечения на выходе получаются три набора последовательностей: последовательности, для которых не найдено паралогичного варианта, последовательности для которых невозможно однозначно определить паралогичные варианты и последовательности для которых удается однозначно определить паралогичные

варианты. На базе этого алгоритма был разработан программный комплекс для выделения паралогичных вариантов генов. Схема разработанного программного комплекса приведена на рисунке 7. Первый этап, не приведенный на схеме 6, представляет из себя получение референсной сборки из тех же ридов, далее проводится выравнивание ридов с полученной «первичной» сборкой. На базе полученных на предыдущем этапе выравниваний проводится поиск SNP позиций. На следующем этапе, производится попытка соединить полученные позиции с помощью помощью парных ридов Illumina и ридов 454. В результате получаем три набора данных. Для набора для которого удается однозначно провести выделение паралогов производится дополнительная досборка.

Первичной сборкой для Capsella bursa-pastoris была выбрана сборка, содержащая 27463 контигов. Данная сборка была получена путем установки параметров сборщика таким образом, чтобы паралогичные варианты объединялись (устанавливался максимально возможный размер областей де Брейн графа, которые представляют собой два альтернативных пути, исходящих из одной вершины и входящих в одну вершину, для которых не применяется их разрешение). Результаты обработки данных с использованием, разработанного алгоритма приведены в таблице 3.

На следующем этапе было проведено предсказание ORF с помощью ORF Finder. Только для трех пар паралогичных вариантов не было найдено ORF. Средняя длина предсказанных ORF 580 п.н.. Далее была оценена идентичность паралогичных вариантов внутри каждой пары, как в нуклеотидном пространстве, так и в белковом. Идентичность нуклеотидных последовательностей варьировалась от 79% до 99%. Идентичность белковых последовательностей составила больше 70%.

I

1) Построение графа паралогичных вариантов. Для каждой БЫР позиции и для каждого варианта добавляется вершина.

2) Ребра добавляются если две соседние £ЫР позиции покрываются одним рядом, причем ребру задается вес в зависимости от покрытия,

3) Упрощение графа.

4)Добавление информации о парности ридов в граф перекрытий.

5) Упрощение графа.

6) В результат« получаем три вида результатов,

II аналогичные варианты не найдены.

Паралогичные Паралогичные варианты варианты

выделены нс удается однозначно. выделить

однозначно.

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

Рис. 7. Программный комплекс для выделения паралогичных вариантов генов при сборке de novo транскриптомных последовательностей.

Таблица 3. Результат обработки данных секвенирования транскриптома Capsella bursa-pasloris

Тип набора Количество элементов в наборе

Последовательности для которых не обнаружены паралогичные варианты 4428

Последовательности для которых могут быть выделены паралогичные варианты однозначно 6281

Последовательности для которых не могут однозначно быть выделены паралогичные варианты 12157

выводы

1. Предложен метод анализа дифференциальной экспрессии генов, по данным секвенирования транскриптомов близких видов, последовательности полных геномов которых Неизвестны. Метод применен для анализа транскриптомов двух видов гречихи F.esculenium и F.tataricum. Было найдено больше 4200 генов, с потенциально дифференциальной экспрессией, для F.esculenium и более 4200 генов, потенциально имеющих дифференциальную экспрессию для F. íaíaricum.

2.Разработан набор средств для предварительной обработки первичных данных при анализе результатов ChIP-Seq экспериментов. Были разработаны средства для подготовки данных, полученных с секвенирующей установки к проведению парного выравнивания с референсной последовательностью, запуска алгоритма парного выравнивания и анализа качества, выполненного выравнивания. Разработано программное обеспечение для маскирования областей геномной последовательности, соответствующей повторам и экзонам. Разработан набор средств для выделения областей покрытых ридами и определения покрытия таких областей.

3. Разработан оригинальный алгоритм для выделения паралогичных вариантов генов при сборке de novo транскриптомов полиплоидных растений. Было проведено севенирование de novo транскриптома тетераплоидного растения Capsella bursa-pastoris. В результате однозначно удалось выделить более 6000 пар паралогичных вариантов.

Список публикаций.

Статьи в рецензируемых журналах.

1. Maria D Logacheva, Artem S Kasianov, Dmitriy V Vinogradov, Tagir H Samigullin, Mikhail S Gelfand, Vsevolod J Makeev and Aleksey A Penin De novo sequencing and characterization of floral transcriptome in two species of buckwheat (Fagopyrum)., BMC Genomics 2011, Vol. 12, N30.

2. A.A. Белостоцкий, И.В. Кулаковский, А.С. Касьянов, И.А. Елисеева, В.Ю. Макеев, Характерные предпочтительные расстояния между сайтами

связывания белковых факторов, регулирующих транскрипцию. Биофизика

2011, Т.56, N1, с136-139.

3. I. V. Kulakovskiy, A. A. Belostotsky, A. S. Kasianov, N. G. Esipova, Y. А. Medvedeva, I. A. Eliseeva, and V. J. Makeev A deeper look into transcription regulatory code by preferred pair distance templates for transcription factor binding sites. Bioinformatics 2011, Vol. 27, N19, pp. 2621-2624.

Тезисы конференций.

4. Kulakovskiy I, Medvedeva Y, Kasianov A, Vorontsov I, Schaefer U, Bajic V, Makeev V. Comprehensive collection of human transcription factor binding sites models (HOCOMOCO). ECCB' 12, 2012.

5. A.S. Kasianov, M.D. Logacheva, N.J. Oparina, and A.A. Penin De novo sequencing, assembly and characterization of transcriptome in the tetraploid plant Capsella bursa-pastoris. Advances and Challenges of RNA-Seq Analysis, Halle/Saale

2012, Germany.

6. Kasianov A.S., Logacheva M.D., Oparina N.J., Penin A.A. De novo sequencing, assembly and characterization of transcriptome in tetraploid plant Capsella bursapastoris. BGRS\SB'2012, 2012.

Подписано в печать 18.11.12. Формат А5 Бумага офсетная. Печать цифровая. Тираж ЮОэкз. Заказ № 2230 Типография ООО "Ай-клуб" (Печатный салон МДМ) 119146, г. Москва, Комсомольский пр-т, д.28 Тел. 8(495)782-88-39

Содержание диссертации, кандидата физико-математических наук, Касьянов, Артем Сергеевич

Содержание.

Определения, обозначения и сокращения.

Введение.

1. Обзор литературы.

1.1 Технологические платформы высокопроизводительного секвенирования и характеристики получаемых данных.

1.2. Основные характеристики "сырых" данных получаемых с секвенаторов.

1.3 Общие характеристики алгоритмов сборки de novo нуклеотидных последовательностей.

1.4. «Жадные» алгоритмы сборки (Greedy).

1.5. Алгоритмы сборки на основе (Overlap/Layout/Consensus) подхода.

1.6. Алгоритмы сборки на основе графа деБруина(БВО).

1.7. Методы сборки de novo, основанные на гибридных и проприентарных подходах.

1.8. Сравнение алгоритмов сборки de novo.

1.9. Обзор алгоритмов коррекции ошибок секвенирования.

1.10. Актуальность проблемы разработки новых методов для обработки данных de novo секвенирования.

1.11 Обзор методов сборки гаплотипов.

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

2.1 Программный комплекс для анализа дифференциальной экспрессии генов двух видов.

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

2.1.2 Подбор алгоритмов сборки.

2.1.2 Разработка алгоритма сравнения результатов сборки.

2.1.2 Программный комплекс для анализа дифференциальной экспрессии двух видов.

2.1.2 Использование разработанного программного комплекса для анализа дифференциальной экспрессии двух видов гречихи F.esculentum и F.tataricum.

3. Разработка методов анализа нуклеотидных последовательностей участков ДНК, связывающих белки, полученных с помощью ChlP-seq.

4. Разработка алгоритма выделения паралогичных генов при сборке диплоидных геномов растений из данных секвенирования транскриптома de novo.

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

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

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

4.4 Сборка de novo транскриптома тетраплоида Capsella bursa - pastoris.

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

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

Технологии секвенирования нового поколения наряду со своей основной задачей, т.е. получением последовательностей генома, позволяют решать задачи, связанные с анализом экспрессии генов (RNA-Seq), специфического ДНК-белкового взаимодействия и структуры хроматина (ChlP-Seq), метилирования ДНК (Methyl-Seq). В результате получается, что задачи анализа биологических макромолекул, которые до сих пор решались различными методами (микрочипы, футпринтинг и т.д.) можно решить с помощью технологий секвенирования нового поколения, что является значительным преимуществом, так как оборудование для секвенирования стремительно дешевеет. Специфика применения секвенаторов нового поколения для решения различных биологических задач заключается в методах подготовки образцов и последующей обработке данных с помощью методов биоинформатики. При разработке алгоритмов обработки данных секвенирования нового поколения (next-generation sequencing, NGS) имеют место как чисто алгоритмические сложности, связанные с огромным объемом данных, так и специфические сложности связанные с характером биологической задачи. Хотя методы секвенирования нового поколения возникли совсем недавно, было разработано огромное количество специфичных для них алгоритмов обработки данных; однако вследствие быстро растущих объемов данных и непрерывного развития технологий эффективность существующих алгоритмов недостаточна. Более того, многие существующие алгоритмы были разработаны под решение конкретных задач и неприменимы в других условиях. Таким образом, обработка данных является лимитирующим фактором, ограничивающим использование технологий секвенирования. В результате разработка новых алгоритмов остается насущной необходимостью, и прогресс в этой области приведет к расширению области применения технологий секвенирования.

В отличии от секвенаторов, построенных на основе классического метода Сенгера, технологии секвенирования нового поколения дают большое количество сравнительно коротких нуклеотидных последовательностей. На данный момент наиболее распространенными технологиями высокопроизводительного секвенирования являются: секвенирование путем синтеза с обратимой терминацией (Illumina), пиросеквенирование (Roche), секвенирование путем лигирования (SOLiD), полупроводниковое секвенирование (Ion torrent). Длина чтений (последовательностей, полученных в результате секвенирования), выдаваемых секвенаторами, построенными на основе этих технологий, варьируется от 30 п.н. до 700 п.н., а классический метод Сенгера дает чтения длиной 1000 п.н. Вследствие этого программное обеспечение, предназначенное для обработки данных, полученных с секвентаров по Сэнгеру, не эффективно при работе с данными нового поколения. Кроме того, вследствие постоянного роста производительности секвенаторов, объем обрабатываемых данных постоянно растет. Данная ситуация осложняется постоянной доработкой существующих технологий, а также появлением абсолютно новых технологических платформ, что, в частности, приводит к изменению шумовых характеристик получаемых данных. Данные трудности постоянно стимулируют создание новых методов обработки NGS данных, потребность в которых на данный момент полностью не удолетворена.

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

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

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

2. Аппробация программного обеспечения, разработанного на основе предложенных методов, на базе проекта de novo секвенирования транскриптомов двух видов гречихи F.esculentum и F.tataricum.

3. Разработка методов и алгоритмов для de novo сборки транскриптомов полиплоидных организмов. 9

4. Аппробация программного обеспечения, разработанного на основе предложенных методов, на базе проекта de novo секвенирования транскриптома тетраплоида Capsella bursa-pastoris.

5. Разработка методов подготовки первичных данных для последующего анализа результатов ChlP-Seq экспериментов для выявления участков ДНК, специфически связывающих белки - регуляторы транскрипции.

Содержание работы. В первой главе приведен обзор основных методов секвенирования нового поколения и методов обработки данных. Во второй главе приведены результаты разработки алгоритма для анализа дифференциальной экспрессии генов, по данным транскриптомов видов, последовательность полного генома которых неизвестна. Третья глава посвящена разработке методов подготовки первичных данных для последующего анализа результатов ChlP-Seq экспериментов для выявления участков ДНК, специфически связывающих белки - регуляторы транскрипции. В тексте четвертой главы приводятся результаты разработки алгоритма выделения паралогичных генов при сборке диплоидных геномов растений из данных секвенирования транскриптома de novo.

1. Обзор литературы

Заключение Диссертация по теме "Молекулярная биология", Касьянов, Артем Сергеевич

Результаты работы были представлены на конференции «Meeting on Advances and Challenges of RNA-Seq Analysis» в городе Халле, Германия в июне 2012 года, на конференции «Bioinformatics of Genome Regulation and Structure\Systems Biology — BGRS\SB-2012» в г. Новосибирске в июле 2012, на конференции «11th European Conference on Computational Biology» в г. Базель, Швейцария в сентябре 2012, Материалы диссертационной работы отражены в 5 публикациях, из них 3 статьи в рецензируемых журналах и 3 публикации в рецензируемых трудах конференций.

Заключение

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

2.Разработан набор средств для предварительной обработки первичных данных при анализе результатов ChlP-Seq экспериментов. Были разработаны средства для подготовки данных, полученных с секвенирующей установки к проведению парного выравнивания с референсной последовательностью, запуска алгоритма парного выравнивания и анализа качества, выполненного выравнивания. Разработано программное обеспечение для маскирования областей геномной последовательности, соответствующей повторам и экзонам. Разработан набор средств для выделения областей покрытых ридами и определения покрытия таких областей.

3. Разработан оригинальный алгоритм для выделения паралогичных вариантов генов при сборке de novo транскриптомов полиплоидных растений. Было проведено севенирование de novo транскриптома тетераплоидного растения Capsella bursa-pastoris. В результате однозначно удалось выделить более 6000 пар паралогичных вариантов.

Библиография Диссертация по биологии, кандидата физико-математических наук, Касьянов, Артем Сергеевич, Москва

1. Pop M. Genome assembly reborn: recent computational challenges. Brief Bioinform 2009;10:354-66.

2. Harismendy O, Ng PC, Strausberg RL, Wang X, Stockwell TB, Beeson KY, Schork NJ, Murray SS, Topol EJ, Levy S, Frazer KA. Evaluation ofnext generation sequencing platforms for population targeted sequencing studies. Genome Biol 2009;10:R32.

3. Phillippy AM, Schatz MC, Pop M. Genome assembly forensics: finding the elusive mis-assembly. Genome Biol 2008;9:R55.

4. Kececioglu, J.; Ju, J. Separating repeats in DNA sequence assembly. Annual Conference on Research in Computational Molecular Biology; 2001. p. 176-183.

5. Myers EW. Toward simplifying and accurately formulating fragment assembly. J ComputBiol 1995;2:275-90.lö.Idury RM, Waterman MS. A new algorithm for DNA sequence assembly. J ComputBiol 1995;2:291-306.

6. Zerbino DR, Birney E. Velvet: algorithms for de novo short read assembly using de Bruijn graphs. Genome Res 2008;18:821-9.

7. Pevzner PA, Tang H, Tesler G. De novo repeat classification and fragment assembly. Genome Res 2004;14:1786-96.

8. Zhi D, Raphael BJ, Price AL, Tang H, Pevzner PA. Identifying repeat domains in large genomes. Genome Biol 2006;7:R7.

9. FasuIo D, Halpern A, Dew I, Mobarry C. Efficiently detecting polymorphisms during the fragment assembly process. Bioinformatics 2002;18(Suppl l):S294-302.

10. Pop M, Salzberg SL. Bioinformatics challenges of new sequencing technology. Trends Genet 2008;24:142-9.

11. Pop M. Genome assembly reborn: recent computational challenges. Brief Bioinform 2009;10:354-66.

12. Warren RL, Sutton GG, Jones SJ, Holt RA. Assembling millions of short DNA sequences using SSAKE. Bioinformatics 2007;23:500-1.

13. Warren, RL.; Holt, RA. SSAKE 3.0: Improved speed, accuracy and contiguity. Pacific Symposium on Biocomputing; 2008.

14. Dohm JC, Lottaz C, Borodina T, Himmelbauer H. SHARCGS, a fast and highly accurate short-read assembly algorithm for de novo genomic sequencing. Genome Res 2007;17:1697-706.

15. Jeck WR, Reinhardt JA, Baltrus DA, Hickenbotham MT, Magrini V, Mardis ER, Dangl JL, Jones CD. Extending assembly of short DNA sequences to handle error. Bioinformatics 2007;23:2942-4.

16. Reinhardt JA, Baltrus DA, Nishimura MT, Jeck WR, Jones CD, Dangl JL. De novo assembly using low-coverage short read sequence data from the rice pathogen Pseudomonas syringae pv. oryzae. Genome Res 2009;19:294-305.

17. Huang X, Yang SP. Generating a genome assembly with PCAP. Curr Pro toe Bioinformatics Chapter 2005; 11 (Unit 11):3.

18. Batzoglou, S. Algorithmic Challenges in Mammalian Genome Sequence Assembly. In: Dunn, M.; Jorde, L.; Little, P.; Subramaniam, S., editors. Encyclopedia of genomics, proteomics and bioinformatics. John Wiley and Sons; Hoboken (New Jersey): 2005.

19. Pop, M. McGraw-Hill. McGraw-Hill 2006 Yearbook of Science and Technology. McGraw-Hill; New York: 2005. DNA sequence assembly algorithms.

20. Sutton, G.; Dew, I. Shotgun Fragment Assembly. In: Rigoutsos, I.; Stephanopoulos, G., editors. Systems Biology: Genomics. Oxford University Press; New York: 2007. p. 79-117.

21. Miller et al. Page 19 Genomics. Author manuscript; available in PMC 2011 June 1. NIH-PA Author Manuscript

22. Wang L, Jiang T. On the complexity of multiple sequence alignment. J ComputBiol 1994;1:337-48.

23. Hernandez D, Francois P, Farinelli L, Osteras M, Schrenzel J. De novo bacterial genome sequencing: millions of very short reads assembled on a desktop computer. Genome Res 2008;18:802-9.

24. Miller JR, Deicher AL, Koren S, Venter E, Walenz BP, Brownley A, Johnson J, Li K, Mobarry C, Sutton G. Aggressive assembly of pyrosequencing reads with mates. Bioinformatics 2008;24:2818-24.

25. Hossain MS, Azimi N, Skiena S. Crystallizing short-read assemblies around seeds. BMC Bioinformatics 2009;10(Suppl 1):S16.

26. Pevzner PA. 1-Tuple DNA sequencing: computer analysis. J Biomol Struct Dyn 1989;7:63-73.

27. Pevzner PA, Tang H, Waterman MS. An Eulerian path approach to DNA fragment assembly. Proc Natl Acad Sei U S A 2001;98:9748-53

28. Simpson, JT.; Wong, K.; Jackman, SD.; Schein, JE.; Jones, SJ.; Birol, I. Genome Res. 2009. ABySS: A parallel assembler for short read sequence data. Epub ahead of print

29. Pevzner PA, Tang H. Fragment assembly with double-barreled data. Bioinformatics 2001 ;17(Suppl l):S225-33.

30. Chaisson M, Pevzner P, Tang H. Fragment assembly with short reads. Bioinformatics 2004;20:2067-74.

31. Chaisson MJ, Pevzner PA. Short read fragment assembly of bacterial genomes. Genome Res 2008;18:324-30.

32. Chaisson MJ, Brinza D, Pevzner PA. De novo fragment assembly with short mate-paired reads: Does the read length matter? Genome Res 2009;19:336-46.

33. Butler J, MacCallum I, Kleber M, Shlyakhter IA, Belmonte MK, Lander ES, Nusbaum C, Jaffe DB. ALLPATHS: de novo assembly of whole-genome shotgun microreads. Genome Res 2008;18:810-20.

34. Li R, Zhu H, Ruan J, Qian W, Fang X, Shi Z, Li Y, Li S, Shan G, Kristiansen K, Yang H, Wang J. De novo assembly of human genomes with massively parallel short read sequencing. Genome Res. 2009

35. Sundquist A, Ronaghi M, Tang H, Pevzner P, Batzoglou S. Whole-genome sequencing and assembly with high-throughput, short-read technologies. PLoS ONE 2007;2:e484.

36. Bryant DW Jr, Wong WK, Mockler TC. QSRA: a quality-value guided de novo short read assembler. BMC Bioinformatics. 2009 Feb 24; 10:69.

37. Ariyaratne PN, Sung WK. PE-Assembler: de novo assembler using short paired-end reads. Bioinformatics. 2011 Jan 15;27(2):167-74. Epub 2010 Dec 12.

38. Schmidt B, Sinha R, Beresford-Smith B, Puglisi SJ. A fast hybrid short read fragment assembly algorithm. Bioinformatics. 2009 Sep l;25(17):2279-80. Epub 2009 Jun 17.

39. Myers EW. The fragment assembly string graph. Bioinformatics 2005;21(Suppl 2):ii79-85.

40. Zhang W, Chen J, Yang Y, Tang Y, Shang J, et al. (2011) A Practical Comparison of De Novo Genome Assembly Software Tools for Next-Generation Sequencing Technologies. PLoS ONE 6(3): el7915. doi:10.1371/journal.pone.0017915

41. Young AL, Abaan HO, Zerbino D, Mullikin JC, Birney E, Margulies EH. A new strategy for genome assembly using short sequence reads and reduced representation libraries. Genome Res. 2010 Feb;20(2):249-56.

42. Zhao X, Palmer LE, Bolanos R, Mircean C, Fasulo D, Wittenberg GM. EDAR: an efficient error detection and removal algorithm for next generation sequencing data. J Comput Biol. 2010 Nov;17(l 1): 1549-60. Epub 2010 Oct 25.

43. Yang X, Dorman KS, Aluru S. Reptile: representative tiling for short read error correction. Bioinformatics. 2010 Oct 15;26(20):2526-33. Epub 2010 Aug 16.

44. Shi H, Schmidt B, Liu W, Müller-Wittig W. A parallel algorithm for error correction in high-throughput short-read data on CUDA-enabled graphics hardware. J Comput Biol. 2010 Apr;17(4):603-15.

45. SaImela L. Correction of sequencing errors in a mixed set of reads. Bioinformatics. 2010 May 15;26(10): 1284-90. Epub 2010 Apr 8.

46. Schröder J, Schröder H, Puglisi SJ, Sinha R, Schmidt B. SHREC: a short-read error correction method. Bioinformatics. 2009 Sep 1;25(17):2157-63. Epub 2009 Jun 19.

47. Kelley DR, Schatz MC, Salzberg SL. Quake: quality-aware detection and correction of sequencing errors. Genome Biol. 2010;11(11):R116. Epub 2010 Nov 29.

48. Wong TK, Lam TW, Chan PY, Yiu SM. Correcting short reads with high error rates for improved sequencing result. Int J Bioinform Res Appl. 2009;5(2):224-37.

49. Chin FY, Leung HC, Li WL, Yiu SM. Finding optimal threshold for correction error reads in DNA assembling. BMC Bioinformatics. 2009 Jan 30; 10 Suppl 1:S15.

50. Boetzer M, Henkel CV, Jansen HJ, Butler D, Pirovano W. Scaffolding pre-assembled contigs using SSPACE. Bioinformatics. 2011 Feb 15;27(4):578-9. Epub 2010 Dec 12.

51. Assefa S, Keane TM, Otto TD, Newbold C, Berriman M. ABACAS: algorithm-based automatic contiguation of assembled sequences. Bioinformatics. 2009 Aug 1;25( 15): 1968-9. Epub 2009 Jun 3.

52. Nijkamp J, Winterbach W, van den Broek M, Daran JM, Reinders M, de Ridder D. Integrating genome assemblies with MAIA. Bioinformatics. 2010 Sep 15;26(18):i433-9.

53. Lancia,G. et al. SNPs problems, complexity, and algorithms. In Proceedings of the 9th Annual European Symposium on Algorithms. Lecture Notes in Computer(2001).

54. Lippert,R. et al. Algorithmic strategies for the single nucleotide polymorphism haplotype assembly problem. Brief. Bioinform. (2002), 3, 23.

55. Levy,S. et al. The diploid genome sequence of an individual human. PLoS Biol. (2007), 5, e254.

56. Aguiar D, Istrail S HapCompass: a fast cycle basis algorithm for accurate haplotype assembly of sequence data. J Comput Biol. 2012 Jun;19(6):577-90.

57. Kent, W James (2002)."BLAT~the BLAST-like alignment tool". Genome Research 12 (4): 656-664.

58. Yi-An Chen, Chang-Chun Lin, Chin-Di Wang, Huan-Bin Wu and Pei-Ing Hwang. An optimized procedure greatly improves EST vector contamination removal. BMC Genomics 2007, 8:416

59. Chevreux B., Wetter T., Suhai S.: Genome sequence assembly using trace signals and additional sequence information. Computer Science and Biology: Proceedings of the German Conference on Bioinformatics 1999, 99:45-56.

60. Altschul, S; Gish, W; Miller, W; Myers, E; Lipman, D (October 1990). "Basic local alignment search tool". Journal of Molecular Biology 215 (3): 403-410.

61. De novo sequencing and characterization of floral transcriptome in two species of buckwheat (Fagopyrum). Maria D Logacheva, Artem S

62. Kasianov, Dmitriy V Vinogradov, Tagir H Samigullin, Mikhail S Gelfand, Vsevolod J Makeev and Aleksey A Penin, BMC Genomics 2011, 12:30.

63. Ricinus communis genome project. http://gsc.jcvi.org/projects/msc/ricinuscommunis/.

64. Min XJ, Butler G, Storms R, Tsang A: OrfPredictor: predicting proteincoding regions in EST-derived sequences. Nucleic Acids Research 2005, W677-W680.

65. Zambelli, F., Pesole, G., and Pavesi, G. (2012). Motif discovery and transcription factor binding sites before and after the next-generation sequencing era. Brief. Bioinformatics, bbs016.

66. Li H. and Durbin R. (2009) Fast and accurate short read alignment with Burrows-Wheeler Transfonn. Bioinformatics, 25:1754-60.

67. Langmead B, Trapnell C, Pop M, Salzberg SL. Ultrafast and memory-efficient alignment of short DNA sequences to the human genome. Genome Biol 10:R25.98. http://www.girinst.org/repbase/.

68. Boeva,V. et al. (2006) Short fuzzy tandem repeats in genomic sequences, identification, and possible role in regulation of gene expression. Bioinformatics, 22, 676-684.