Wykład

Transcript

ALEKSANDRA ŚWIERCZ Plan wykładów  Wprowadzenie do różnych metod sekwencjonowania  Resekwencjonowanie – mapowanie do genomu referencyjnego  Sekwencjonowanie de novo – asemblacja  Różnica w ekspresji genów, alternatywny splicing  Różnice między genomami – CNV, SNP  Analiza krótkich miRNA  Wizualizacja danych, Short Read Archive A. Świercz ANALIZA DANYCH WYSOKOPRZEPUSTOWYCH 2 Sposoby zaliczenia Wykład: ◦ Kolokwium zaliczeniowe – max 5 punktów ◦ Prezentacja – max 2 punkty ◦ Obecność na wykładach – max 1 punkt Zaliczenie od 3 punktów (ocena 3.0) Laboratoria: ◦ Kilka zadań zaliczeniowych, do oddawania razem ze sprawozdaniem A. Świercz ANALIZA DANYCH WYSOKOPRZEPUSTOWYCH 3 Sekwencjonowanie DNA/RNA BLACK BOX A. Świercz AAATGCCTGCCCTGAAGGCCTGCGTA GTTTTGGGAGAAGACCCACGGATA AAGGTGTAGCCCCGTAGC GGGGGGTATTATTTATTTTATACCCAC ………….. ACAGGAUCGUUGGAUGGTGGGA …………. Sekwencjonowanie polega na odczytaniu sekwencji liter DNA/RNA badanego fragmentu genomu ANALIZA DANYCH WYSOKOPRZEPUSTOWYCH 4 Sekwencjonowanie DNA/RNA Sanger SBH BLACK BOX A. Świercz AAATGCCTGCCCTGAAGGCCTGCGTA GTTTTGGGAGAAGACCCACGGATA AAGGTGTAGCCCCGTAGC GGGGGGTATTATTTATTTTATACCCAC ………….. ACAGGAUCGUUGGAUGGTGGGA …………. ANALIZA DANYCH WYSOKOPRZEPUSTOWYCH 5 Sekwencjonowanie DNA/RNA Sanger SBH Roche/454 BLACK BOX AAATGCCTGCCCTGAAGGCCTGCGTA GTTTTGGGAGAAGACCCACGGATA AAGGTGTAGCCCCGTAGC GGGGGGTATTATTTATTTTATACCCAC ………….. ACAGGAUCGUUGGAUGGTGGGA …………. Illumina Applied Biosystems SOLID Ion Torrent Complete Genomics Pacific Biosystems Heilcos Heliscope A. Świercz ANALIZA DANYCH WYSOKOPRZEPUSTOWYCH 6 Pacific Biosystems Długie odczyty 20 000 bp Sanger Ion Torrent Roche/454 SBH Pojedyncza sekwencja Illumina Dużo powtórzeń DNA Applied Biosystems SOLID Complete Genomics Heilcos Heliscope Krótkie odczyty 20 bp A. Świercz ANALIZA DANYCH WYSOKOPRZEPUSTOWYCH 7 Metoda Sangera – elektroforeza żelu A. Świercz ANALIZA DANYCH WYSOKOPRZEPUSTOWYCH 8 Sekwencjonowanie przez hybrydyzację (SBH) 1. Część eksperymentalna - przeprowadzenie eksperymentu biochemicznego, w czasie którego znalezione zostaną wszystkie fragmenty badanego łańcucha DNA o określonej z góry długości 2. Część obliczeniowa – odtworzenie badanej sekwencji DNA poprzez poskładanie krótkich fragmentów w dłuższy łańcuch. A. Świercz ANALIZA DANYCH WYSOKOPRZEPUSTOWYCH 9 SBH – część eksperymentalna 1. Przygotowanie sekwencji DNA: ◦ ◦ ◦ ◦ 2. Cięcie sekwencji metodą shotgun Tylko jedna nić Namnażanie wielu kopii Nałożenie koloru fluorescencyjnego Przygotowanie chipu/mikromacierzy –płytki na której znajdują się różne oligonukleotydy, np. wszystkie oligonukleotydy o długości 8 A. Świercz ANALIZA DANYCH WYSOKOPRZEPUSTOWYCH 10 SBH – eksperyment hybrydyzacji 1. Przygotowanie chipu DNA A AC ACG ACGT Round 1 ACGT ACGT A Round 2 A. Świercz ACGT A C ANALIZA DANYCH WYSOKOPRZEPUSTOWYCH ACGT A C G A C G T 11 A CGT Round 3 A C G T ... and so on ... DNA chip AAAA 0,4mm Full library of tetranucleotides 0,4mm 25m site per probe 44 – 0.0016 cm2 48 – 0.4096 cm2 410 – 6.5536 cm2 AAAA AACA AAGA AAAC AACC AAGC AAAT AACG AAGG AAAT AACT AAGT ACAA ACCA A. Świercz ANALIZA DANYCH WYSOKOPRZEPUSTOWYCH 12 2. Reakcja hybrydyzacji DNA chip A. Świercz TCCACTG... Wiele znakowanych kopii badanej sekwencji DNA ANALIZA DANYCH WYSOKOPRZEPUSTOWYCH 13 A. Świercz ANALIZA DANYCH WYSOKOPRZEPUSTOWYCH 14 A. Świercz ANALIZA DANYCH WYSOKOPRZEPUSTOWYCH 15 A. Świercz ANALIZA DANYCH WYSOKOPRZEPUSTOWYCH 16 2. Reakcja hybrydyzacji DNA chip TCCACTG... Wiele znakowanych kopii badanej sekwencji DNA 3. Wynik odczytu Fluorescencyjny chip DNA . . . . . . . spectrum Spektrum – zbiór oligonukleotydów komplementarnych do fragmentu badanej sekwencji DNA A. Świercz ANALIZA DANYCH WYSOKOPRZEPUSTOWYCH 17 Reakcja hybrydyzacji pomiędzy sondą o znanej sekwencji (l-mer) i nieznaną sekwencją o długości n (n-mer): n-mer - . . . A A C T A G A C C T . . . l-mer - GAT CTA Sekwencja komplementarna do sondy istnieje w targecie A. Świercz ANALIZA DANYCH WYSOKOPRZEPUSTOWYCH 18 Sekwencjonowanie DNA bez błędów Sekwencja oryginalna: AACTAGACCT Spektrum = {AAC,ACT,CTA,TAG,AGA,GAC,ACC,CCT} (Dwa możliwe rozwiązania : AACTAGACCT, AACCTAGACT)  Lysov (1988) Graf oparty o l-mery (graph H) AAC ACT CTA CCT TAG ACC GAC AGA Znalezienie ścieżki Hamiltona – NP-trudne A. Świercz ANALIZA DANYCH WYSOKOPRZEPUSTOWYCH 20 Pevzner (1989) AAC AA AC Graf oparty na (l-1)-merach (graf G): AA AC CT TA CC AG GA Znalezienie ścieżki Eulera – rozwiązywalne w czasie wielomianowym o Problem równoważności o Problem unikalności A. Świercz ANALIZA DANYCH WYSOKOPRZEPUSTOWYCH 21 Błędy w eksperymencie SBH 1. Błędy pozytywne – nadmiar w spektrum a. W czasie eksperymentu hybrydyzacji niekomplementarne oligonukleotydy (mające nie wszystkie zasady komplementarne) przyłączają się do badanego łańcucha DNA. W konsekwencji odczytu obrazu fluorescencyjnego, błędny oligonukleotyd zostaje włączony do spektrum. b. Obraz fluorescencyjny chipu może być zanieczyszczony i omyłkowo oligonukleotyd może zostać włączony do spektrum A. Świercz ANALIZA DANYCH WYSOKOPRZEPUSTOWYCH 23 Błędy w eksperymencie SBH 2. Błędy negatywne – braki w spektrum a. Oligonukleotyd pojawia się w sekwencji oryginalnej więcej niż jeden raz. Ponieważ spektrum nie jest multizbiorem, tylko jedno wystąpienie każdego elementu jest możliwe b. Nie wszystkie zasady z komplementarnego oligonukleotydu przyłączyły się do świecącego łańcucha DNA, stąd też sygnał na chipie jest słabo widoczny i oligonukleotyd nie zostanie odczytany. A. Świercz ANALIZA DANYCH WYSOKOPRZEPUSTOWYCH 24 J. Błażewicz, P. Formanowicz, M. Kasprzak, W.T. Markiewicz, J. Węglarz DNA Sequencing with positive and negative errors, Journal of Computational Biology 6, No. 1, 1999. A. Świercz ANALIZA DANYCH WYSOKOPRZEPUSTOWYCH 25 Sekwencjonowanie DNA w przypadku błędów pozytywnych i negatywnych Sformułowanie jako wariant problemu komiwojażera z nagrodami: Mając pełny graf G=(V,A), V=spektrum, z nagrodą za odwiedzenie każdego wierzchołka równą 1 oraz łukami z kosztami równymi liczbie nakładających się etykiet wierzchołków (oligonukleotydów), znajdź ścieżkę z maksymalnym zyskiem i kosztem nie większym niż n-l. [J.Błażewicz, P.Formanowicz, M.Kasprzak, W.T.Markiewicz, J.Węglarz,1999] A. Świercz ANALIZA DANYCH WYSOKOPRZEPUSTOWYCH 26 Przykład CTTACTACG – sekwencja oryginalna spektrum – {CTT, TAC, ACT, CTA, ACG, GCG} Długość sekwencji n=9 Długość oligonukleotydów =3 GCG – błędy pozytywne TTA, TAC – błędy negatywne CTT – początkowy oligonukleotyd A. Świercz ANALIZA DANYCH WYSOKOPRZEPUSTOWYCH 27 CTT CTT TAC GCG ACG ACT TAC GCG ACG ACT CTA CTA koszt= 1, np. T(AC)T Dwa rozwiązania optymalne koszt= 2, np. AC(T)AC A. Świercz ANALIZA DANYCH WYSOKOPRZEPUSTOWYCH 28 Złożoność problemu SBH Problem sekwencjonowania SBH w przypadku gdy nie ma błędów w spektrum jest problemem łatwym obliczeniowo (należy do klasy P). Problem SBH w przypadku z błędami pozytywnymi albo negatywnymi, albo błędami obu typów jest problemem trudnym obliczeniowo (należy do klasy silnie NP-trudnej) A. Świercz ANALIZA DANYCH WYSOKOPRZEPUSTOWYCH 29 Przykłady modyfikacji klasycznego podejścia o Biblioteki izotermiczne – w celu zmniejszenia liczby błędów eksperymentalnych zamiast bibliotek oligonukleotydów o równej długości wprowadzono pojęcie bibliotek izotermicznych, czyli oligonukleotydów o zbliżonej temperaturze topnienia dupleksów. A,T- mniej stabilne, mają niższą temperaturę niż G,C ex. t(ACGTC) = 2+4+4+2+4 = 16 o „Sondy z dziurami” – tzw. gapped probes. Wprowadzono pojęcie uniwersalnych nukleotydów, które przyłączają się do dowolnego nukleotydu w łańcuchu DNA. Sondy na chipie są kombinacją zwykłych i uniwersalnych nukleotydów, dzięki czemu można wydłużyć długość oligonukleotydów nie zwiększając liczności biblioteki A. Świercz ANALIZA DANYCH WYSOKOPRZEPUSTOWYCH 30 Wybrana literatura dla problemu SBH J.Błażewicz, P.Formanowicz, M.Kasprzak, W.T.Markiewicz, J.Węglarz, „DNA sequencing with positive and negative errors”, Journal of Computational Biology 6, 1999, pp.113-123. F.P. Preparata, A.M. Frieze, and E. Upfal. On the power of universal bases in sequencing by hybridization. In Proc. 3rd Ann. Int. Conf. Comput. Mol. Biol., pages 295–301, 1999. J.Błażewicz, P.Formanowicz, M.Kasprzak, W.T.Markiewicz, J.Węglarz, „Tabu search for DNA sequencing with false negatives and false positivies”, European Journal of Operational Research 125, 2000, pp. 257-265. V.T. Phan and S. Skiena. Dealing with errors in interactive sequencing by hybridization. Bioinformatics, 17:862–870, 2001. J. Błażewicz, P. Formanowicz, F. Guinand, M. Kasprzak, "A heuristic managing errors for DNA sequencing„, Bioinformatics 18, 2002, pp. 652-660. J-H. Zhang, L-Y. Wu, and X-S. Zhang. Reconstruction of DNA sequencing by hybridization. Bioinformatics, 19:14–21, 2003. S.A. Heath, F.P. Preparata, and J. Young. Sequencing by hybridization by cooperating direct and reverse spectra. J. Comput. Biol., 10:499–508, 2003. E. Halperin, S. Halperin, T. Hartman, and R. Shamir. Handling long targets and errors in sequencing by hybridization. J. Comput. Biol., 10:483–497, 2003 J. Błażewicz, F. Glover, M. Kasprzak, "DNA sequencing - tabu and scatter search combined„ INFORMS Journal on Computing 16, 2004, pp. 232-240 F.P. Preparata and J.S. Oliver. DNA sequencing by hybridization using semi-degenerate bases. J. Comput. Biol., 11(4):753–765, 2004. J. Błażewicz, P. Formanowicz, M. Kasprzak, W. T. Markiewicz, A. Świercz, ”Tabu search algorithm for DNA sequencing by hybridization with isothermic libraries” Computational Biology and Chemistry 28, 2004, pp. 11-19. T.A. Endo. Probabilistic nucleotide assembling method for sequencing by hybridization. Bioinformatics, 20:2181–2188, 2004. J. Błażewicz, C. Oğuz, A. Świercz, J. Węglarz, "DNA sequencing by hybridization via genetic search”, Operations Research 54, 2006, pp.1185-1192. J. Błażewicz, F. Glover, M. Kasprzak, W.T. Markiewicz, C. Oğuz, D. Rebholz-Schuhmann, A. Świercz "Dealing with repetitions in sequencing by hybridization”, Computational Biology and Chemistry 30, 2006, pp 313-320. A. Świercz ANALIZA DANYCH WYSOKOPRZEPUSTOWYCH 31 Illumina A. Świercz ANALIZA DANYCH WYSOKOPRZEPUSTOWYCH 32 Illumina Flow cell A. Świercz ANALIZA DANYCH WYSOKOPRZEPUSTOWYCH 33 A. Świercz ANALIZA DANYCH WYSOKOPRZEPUSTOWYCH 34 A. Świercz ANALIZA DANYCH WYSOKOPRZEPUSTOWYCH 35 A. Świercz ANALIZA DANYCH WYSOKOPRZEPUSTOWYCH 36 A. Świercz ANALIZA DANYCH WYSOKOPRZEPUSTOWYCH 37 Podział flowcell A. Świercz ANALIZA DANYCH WYSOKOPRZEPUSTOWYCH 38 Whiteford N et al. Bioinformatics 2009;25:2194-2199 A. Świercz ANALIZA DANYCH WYSOKOPRZEPUSTOWYCH 39 A. Świercz ANALIZA DANYCH WYSOKOPRZEPUSTOWYCH 40 A. Świercz ANALIZA DANYCH WYSOKOPRZEPUSTOWYCH 41 W których klastrach odczyty przechodzą filtr jakości? A. Świercz ANALIZA DANYCH WYSOKOPRZEPUSTOWYCH 42 Wiele próbek na jednej linii - multiplexing A. Świercz ANALIZA DANYCH WYSOKOPRZEPUSTOWYCH 43 Odczyty sparowane A. Świercz ANALIZA DANYCH WYSOKOPRZEPUSTOWYCH 44 Porównanie sekwenatorów Illuminy A. Świercz ANALIZA DANYCH WYSOKOPRZEPUSTOWYCH 45 Pyrosequencing 454 Life Sciences A. Świercz ANALIZA DANYCH WYSOKOPRZEPUSTOWYCH 46 Przygotowanie biblioteki DNA A. Świercz ANALIZA DANYCH WYSOKOPRZEPUSTOWYCH 47 Sekwencjonowanie ... A. Świercz ANALIZA DANYCH WYSOKOPRZEPUSTOWYCH 48 Flowgram – wyjście dla każdej studzienki A. Świercz ANALIZA DANYCH WYSOKOPRZEPUSTOWYCH 49 Format danych z sekwenatora A. Świercz ANALIZA DANYCH WYSOKOPRZEPUSTOWYCH 50 Tabela kodów ASCII A. Świercz ANALIZA DANYCH WYSOKOPRZEPUSTOWYCH 51 Jakość – Phred quality score 2 -> ASCII code 50 qual = ASCII code – 33 = 17 A. Świercz Phred quality score Prawdopodobieńst wo błędu Perror 3 1 na 2 50% 5 1 na 3 32% 10 1 na 10 10% 20 1 na 100 1% 30 1 na 1000 0.1% 40 1 na 10000 0.01% ANALIZA DANYCH WYSOKOPRZEPUSTOWYCH 52 Rozkład jakości dla każdego nukleotydu A. Świercz ANALIZA DANYCH WYSOKOPRZEPUSTOWYCH 53 A. Świercz ANALIZA DANYCH WYSOKOPRZEPUSTOWYCH 54 Obrazki, slajdy… www.illumina.com www.454.com I inne strony związane z sekwenatorami Informatics on High Throughput Sequencing Data (2013) @ www.bioinformatics.ca A. Świercz ANALIZA DANYCH WYSOKOPRZEPUSTOWYCH 55