Т ЕОРИЯ ГЕНОМНОЙ СБОРКИ. Г РАФЫ. И СТОЧНИКИ АРТЕФАКТОВ ПРИ СБОРКЕ Касьянов Артем 01.10.2014. - презентация

1 Т ЕОРИЯ ГЕНОМНОЙ СБОРКИ. Г РАФЫ. И СТОЧНИКИ АРТЕФАКТОВ ПРИ СБОРКЕ Касьянов Артем

2 Что такое геном? Полный набор ДНК, содержащийся в организме: – Хромосомы – Органеллы(митохондрии, хлоропласты и т.д.) – Плазмиды – ДНК-вирусы – Бактериофаги Без потери общности можно представить в виде набора строк из четырехбуквенного алфавита(A,G,C,T). 2

3 Размеры геномов 3 Вирусы, плазмиды – От 1 т.п.н. до 100 т.п.н. …HIV 9181 п.н. Бактерии, археи – От 1 м.п.н. до 10 м.п.н. …E.coli 4.6 м.п.н. Простейшие эукариоты – От 10 м.п.н. до 100 м.п.н. …Malaria 23 м.п.н. Животные, растения – От 100 м.п.н. до 150 млрд.п.н. …Human 3.2 млрд. п.н.

4 WGS секвенирование 4 Несколько копий ДНК молекул Фрагменты длиной ,000 п.н. Не остается информации из какой части генома взят тот или иной фрагмент

5 WGS секвенирование: фрагменты 5 Секвенатор считывает по п.н. с конца/концов фрагмента. Размеры фрагментов известны с точностью ± 10-20%. CAAGCTGAT... Пары чтений Неизвестная последовательность …GTTTGGAAC

6 Геномные чтения Короткие поддпоследовательности генома – Неизвестно из какого места генома они получены. – Неизвестно с какой нити они взяты Перекрываются друг с другом Содержат ошибки 6

7 Сборка генома 7 [

8 Что такое граф Граф G это упорядоченная пара G := (V, E), где V это непустое множество вершин или узлов, а E множество пар (в случае неориентированного графа неупорядоченных) вершин, называемых рёбрами. Путем в графе называют конечную последовательность вершин, в которой каждая вершина (кроме последней) соединена со следующей в последовательности вершиной ребром. 8 [

9 Алгоритмы сборки OLC(overlap-layout-consensus) алгоритмы Алгоритмы, основанные на de Bruijn графах «Жадные» алгоритмы 9

10 OLC алгоритмы 10 1)Вычисление перекрытий 2) Построение графа перекрытий и нахождение гамильтонового пути 3)Вычисление множественного выравнивания 4)Построение консенсус последовательности

11 Гамильтонов путь 11 Гамильтонов путь путь, содержащий каждую вершину графа ровно один раз. Нахождение такого пути NP- полная задача Уильям Гамильтон, 1856

12

13 OLC алгоритмы Staden, R. A new computer method for the storage and manipulation of DNA gel reading data(1982) Nucleic Acids Research 10, – Построен на основе жадного подхода – Предложен термин контиг 1984 – SEQAID – Peltola, H., Söderlund, H., and Ukkonen, E SEQAID: A DNA sequence assembly program based on a mathematical model. Nucleic Acids Res. 12, – Первый OLC сборщик 1992 – CAP – Huang, X A contig assembly program based on sensitive detection of fragment overlaps. Genomics 14,

14 OLC алгоритмы Название ТехнологииАвторыPresented EdenaIllumina D. Hernandez et al Celera WGA Assembler / CABOG Sanger, 454, Illumina Myers, G. et al.; Miller G. et al MIRA Sanger, 454, Illumina, SOLiD, IonTor, PacBio Chevreux, B1998 PCAPSanger, 454Huang et al

15 De Bruijn граф 15 AGCTATCGTGACG AGCTATGCTATCCTATCG TATCGT ATCGTG TCGTGACGTGAC GTGACG AGCTATC GCTATCG CTATCGTTATCGTG ATCGTGATCGTGACCGTGACG ATCGTGAGCTAT GCTATC AGCTATC CTATCG GCTATCG TATCGT CTATCGT TATCGTG TCGTGACGTGACGTGACG ATCGTGA TCGTGAC CGTGACG

16 De Bruijn граф 16 AGCTATCGTGACG AGCTATC GCTATCG CTATCGT TATCGTG ATCGTGA TCGTGAC CGTGACG

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

18 De Bruijn граф 18 TGTACTATGTCCTA TGTGTATACACTCTA TAT ATGTGTGTCTCCCCTCTA TGTAGTACTACT ACTA CTAT TATG ATGTTGTCGTCC TCCTCCTA TGT GTA TAC ACT GTC TCC CCT CTA ATG TAT TGTA GTAC TACT ACTA CTAT TATG ATGT TGTC GTCC TCCT CCTA

19 De Bruijn граф 19 TGTA GTAC TACT CTAT TATG ATGT TGTC GTCC TCCT CCTA ACTA TGTACTATGTCCTA TGTC GTCC TCCT CTAT TATG ATGT TGTA GTAC TACT ACTA CCTA TGTCCTATGTACTA

20 De Bruijn graph algorithms 1)Построение хэша и deBruijn граф 2)Упрощение линейных участков 3)Удаление «пузырей» и «хвостиков» 20 [Daniel R. Zerbino and Ewan Birney, Velvet: Algorithms for de novo short read assembly using de Bruijn graphs. Genome Res. May 2008; 18(5): 821–829. ]

21 De Bruijn graph 21 K low K mid K high

22 De Bruijn граф 22 1)Сильная зависимость от выбора параметра k. Не существует формальной методики позволяющей выбрать этот параметр оптимальным образом. 2)Сильная зависимость от наличия ошибок в чтениях.

23 Алгоритмы, основанные на De Bruijn графах Наименование ТехнологииАвторы Разработан ABySSIllumina, SOLiDSimpson, J. et al.2008 CLC Genomics Workbench Sanger, 454, Illumina, SOLiD CLC bio2008 EulerSanger, 454Pevzner, P. et al2001 Euler-sr454, IlluminaChaisson, MJ. et al.2008 IDBA (Iterative De Bruijn graph short read Assembler) Illumina,454,Solex a Yu Peng, Henry C. M. Leung, Siu-Ming Yiu, Francis Y. L. Chin 2010 VelvetSanger, 454, Illumina, SOLiD Zerbino, D. et al2007 SPAdesIllumina, Ion Torrent, PacBio Bankevich, A et al

24 String graph 24

25 Алгоритмы, основанные на String graph методологии Наименование ТехнологииАвторы Разработан SGAIllumina, Ion Torrent Simpson, J. et al.2011 NewblerSanger, 454, Illumina, Ion Torrent 454/Roche

26 Более реалистичный пример графа 26 [ FullPresentations/Torsten-Seemann_2013-Winter-School-presentation.pdf]

27 Что усложняет графы Ошибки в чтениях – Приводят к появлению в графе ошибочных ребер и вершин. Диплоидные и полиплоидные организмы – Приводит к появлению дополнительных путей в графе Повторы 27

28 Что такое повтор? Участок ДНК, который встречается более одного раза в геномной последовательности. Наиболее частые – Транспозоны – Сателлитные повторы – Дуплицированные гены(паралоги) 28

29 Как повторы влияют на сборку 29 Повторяющиеся элементы сливаются в один контиг. [ FullPresentations/Torsten-Seemann_2013-Winter-School-presentation.pdf]

30 Как повторы влияют на сборку 30 Слияние тандемных повторов Исключение участка между повторами Перестановка [ FullPresentations/Torsten-Seemann_2013-Winter-School-presentation.pdf]

31 OLC vs DBG DBG – Очень чувствителен к повторам и ошибкам в чтениях – Одна ошибка в чтении создает k ошибочных узлов – Ключевой параметр: размер k. OLC – Менее чувствительны к повторам и ошибкам в чтениях – Построение графа требует больше вычислительных ресурсов – Плохо масштабируется при увеличении числа чтений – Ключевой параметр: minOverlapLen, %. 31

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

33 Скаффолдинг Парные чтения – известно расстояние между парными чтениями – неизвестна последовательность между парными чтениями Большинство пар чтений будет в одном контиге – если длина большинства контигов больше длины чтений Часть парных чтений будет в разных контигах – эти контиги возможно связаны 33

34 От контигов к скаффолдам 34 Парные чтения Контиги Скаффолд Гэпы [ FullPresentations/Torsten-Seemann_2013-Winter-School-presentation.pdf]

35 Параметры набора данных Длина рида Покрытие Качество Тип библиотеки: SE,PE,MP. 35

36 Технологии секвенирования Компания ПлатформаТехнология Длина рида, п.н. ABI/Life technologies 3130xL-3730xLCE-Sanger BeckmanGeXP Genetic Analysis System CE-Sanger Roche/454Genome Sequencer FLX System Pyrosequencing IlluminaHiSeq 2000/miSeqReversible terminator sequencing by synthesis 2 x 150 ABI/SOLiD5500xl SOLiD System Sequencing by ligation HelicosHeliScopeSingle-molecule sequencing by synthesis Pacific Biosciences PacBio RSSingle Molecule Real Time 964 ABI/Life technologies Ion PGM SequencerSemiconductor Sequencing

37 Что такое длина вставки? 37

38 Если вы подписались на длинный геном 38 Требуйте набор библиотек с разной длиной вставки Геном мухоловки Gb Библиотеки: 1)~200 4)~5007)~5100 2)~3005)~24008)~ )~4006)~41009)~21000 [Ellegren H et al., The genomic landscape of species divergence in Ficedula flycatchers. Nature 2012, 491.]

39 Что такое покрытие? 39 Это сколько раз в среднем нуклеотид генома покрыт ридами [

40 Необходимое покрытие для de Novo сборки Длина чтения Необходимое покрытие 400 п.н.(454,PacBio)20x-40x 40

41 Форматы файлов FASTA формат >SEQ_ID GATTTGGGGTTCAAAGCAGTATCGATCAAATAGTAAATCCATTTGTTCAACTCACAGTT T FASTQ GATTTGGGGTTCAAAGCAGTATCGATCAAATAGTAAATCCATTTGTTCAACTCACAGTT T + !''*((((***+))%%++)(%%).1***-+*''))**55CCF>>>>>>CCCCCCC65

42 De novo сборка генома Предобработка FASTQC, prinseq, trimmomatic, kmc2,kmernator2… Сборка Newbler, Spades, Velvet… Оценка качества сборки QUAST, BLAST, Prinseq, Bowtie… 42

43 Предобработка Оценка качества набора чтений.(FASTQC) Триммирование ридов.(trimmomatic…) 43

44 Предобработка Фильтрация по кмерам. (kmernator2…) 44

45 Как оценить качество сборки? Число контигов – Чем меньше тем лучше. Размер контигов – Средняя длина, максимальная длина, медиана, N50 Суммарная длина – Должна быть близка к ожидаемой Число N – Чем меньше, тем лучше 45

46 Что такое N50? N50 показывает качество сборки Скаффолды располагают по убыванию длины Суммируют длину, начиная с самого большого скаффолда. На каком скаффолде покроем половину генома? Длина этого скаффолда называется N [

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

48 Верификация сборки ALE(Assembly Likelihood Evaluation)[Clark et al.,2013] FRC(Feature Response Curve)[Vezzi et al. 2012] Amosvalidate[Phillippy et al., 2008] 48

49 Почему тяжело собирать геномы? Биологические причины – Высокая плоидность, гетерозиготность, повторы Трудности, свзяанные с секвенированием – Очень большие геномы, неточное секвенирование Вычислительные трудности – Очень большие геномы, сложность структуры Оценка качества – Очень трудно оценивать качество 49

50 Что нужно для хорошей сборки 50 Длина чтений Покрытие Качество Длина чтений или хотя бы длины вставок должны быть больше чем длина повторов Требуется высокий уровень покрытия Ошибки могут скрывать перекрытия [Current challenges in de novo plant genome sequencing and assembly Schatz MC., Witkowski, McCombie, WR(2012) Genome biology,12:243]

51 Виды сборок 51 [Chain at el. Genome Project Standards in a New Era of Sequencing. Science ]

52 Виды сборок Standard draft – просто запустили ассемблер High-Quality Draft – покрывает 90% целевого генома, удалялись загрязнения. Годится для аннотации. Improved High-Quality Draft – поиск ошибок сборки, закрытие гэпов в скаффолдах. Годится для сравнительной геномики. Annotation-Directed Improvement – проделана аннотация, ошибки в белок кодирующих последовательностях сведены к минимуму. Noncontigous finished – предприняты усилия для закрытия большинства гэпов, ошибок сборки и областей с повторами(досеквенирование). Finished – менее 1 ошибки на нуклеотидов. 52

53 ВОПРОСЫ? При подготовке презентации использовались материалы лекции Сергея Науменко в рамках курса «Обработка данных NGS» в ФББ МГУ, материалы с сайтов 53

54 De novo секвенирование транскриптома vs de novo секвенирование генома Геномы не модельных организмов могут быть достаточно сложными для восстановления(большое число повторов, полиплоидность, большой размер). Секвенирование транскриптома позволяет быстро получить доступ к информации о генах и белках, использующихся для функционирования организма. В большинстве случаев для более точной аннотации генома все равно потребуются транскриптомные данные. Секвенирование траснкриптома дешевле полногеномного секвенирования. Вследствие развития технологий секвенирования растет длина рида. На данный момент «слитые» риды Illumina Miseq достигают трети средней длины транскрипта, что значительно упрощает сборку и позволяет использовать OLC сборщики. 54

55 De novo секвенирование транскриптома vs de novo секвенирование генома Транскриптомы различных тканей взятые в разные промежутки времени могут очень сильно отличаться. 20% генов дают 80% ридов. 55 [O'Neil et al. BMC Genomics 2010, 11:310]

56 De novo секвенирование транскриптома vs de novo секвенирование генома Неравномерность покрытия транскриптов. 56 [Zhong Wang et al. Nat. Rev. Gen. 2009, Vol.10]

57 Программы для сборки геномов ожидают более-менее равномерное распределение покрытия. Собранные регионы для которых наблюдается возрастание покрытия принимаются за повторы. Но индивидуальные гены внутри транскриптома могут иметь очень разное покрытие. Сборка транскриптомов vs сборка геномов 57 [ _downloads/MB_RNASeq_Trans_Assembly_SC_2013.pdf]

58 Splicing graph 58 [

59 Общая схема de novo сборки транскриптома 59 [Martin & Wang (2011) Nat. Rev. Gen. 12,671]

60 Общая схема de novo сборки транскриптома 60 [Martin & Wang (2011) Nat. Rev. Gen. 12,671]

61 Общая схема de novo сборки транскриптома 61 [Martin & Wang (2011) Nat. Rev. Gen. 12,671]

62 Транскриптомные сборщики 62 Сборщики, основанные на DeBruijn графах. (Illumina,SOLiD,IonTorrent ) Сборщики, основанные на OLC подходе(454, Sanger, PacBio) Trinity(Broad) Velevet(Oases) TransAbyss SOAPtrans Mira3 Est2assembly GS/Newbler(Roche) SMRT Pipe(PacBio)

63 Оценка качества сборки Картирование чтений обратно на сборку. – >60% ридов картируется - норма. – >80% ридов картируется - очень хороший результат. Оценка числа контигов. – Должно быть в пределах размера транскриптома.( A.Thaliana ~ генов, H.sapiens ~ генов) Оценка среднего покрытия контигов. Оценка числа уникальных п.н.. – чем больше тем лучше. Оценка N50 контигов. Должно соответствовать N50 транскриптома. (A. Thaliana ~1900 п.н., H.sapiens ~2500 п.н.) Оценка числа контигов >1 т.п.н.. – Чем больше тем лучше. 63

64 Постобработка транскриптомной сборки Многие транскриптомные сборщики(в частности Trinity) дают большое количество контигов(>100K) Возникает вопрос, как уменьшить число контигов. Можно сформулировать следующее правило: Не нужно кластеризовать, нужно фильтровать. Кластеризация приведет к схлопыванию паралогов, альтернативных изоформ и семейств генов. Кластеризация приводит к возникновению химер. Фильтруйте по % изоформ, покрытию, ORF, бластовым хитам и т. д. Оценивать насколько велики потери данных в результате фильтрации можно картируя риды на контиги. 64 «У меня слишком много контигов, что делать дальше?»

65 Velvet Автор: Zerbino, D. Представлен: 2007 Поддерживаемые технологии: Sanger, 454, Solexa, SOLiD Текущая версия:

66 Velvet velveth - обрабатывает файлы с последовательностями и конструирует хэштаблицу, на основании этого создает два файла, Sequences и Roadmaps, которые необходимы для velvetg. velvetg – ядро Velvetа, создает de Bruijn граф и на основании него конструирует контиги. Поддерживаемые форматы: fasta(по умолчанию); fastq; fasta.gz; fastq.gz; sam; bam; eland; gerald 66

67 velveth./velveth [[- ][- ] ] read_type – short(по умолчанию); shortPaired; short2; shortPaired2; long; longPaired 67

68 velvetg(одиночные чтения)./velvetg [ ] -cov_cutoff -min_contig_lgth -max_coverage -exp_cov 68

69 velvetg(парные чтения)./velvetg [ ]./shuffleSequences_fasta.pl forward_reads.fa reverse_reads.fa output.fa -ins_length -ins_length_sd -ins_length2 -ins_length2_sd -ins_length_long -ins_length_long_sd 69

70 Velvet файлы с результатами сборки contigs.fa stats.txt LastGraph Final graph has nodes and n50 of 7, max 99, total , using 0/ reads 70