Transcript
12/28/2016
F: PROBLEM: SEKWENCJONOWANIE DNA METODA: ALGORYTMY GRAFOWE
I. II. III. IV. V.
Grafy i genetyka Sekwencjonowanie DNA Macierze DNA Sekwencjonowanie przez hybrydyzacje DNA Sekwencjonowanie i identyfikacja białka
Grafy
D. Makowiec: F: sekwencjonowanie DNA
2
Dwie konfiguracje z czterema konikami szachowymi na szachownicy 3x3. Czy można, korzystając z dozwolonych ruchów dla konika szachowego, konfigurację (a) przekształcić na konfigurację (b)?
odpowiedź jest NIE
Grafy reprezentujące sytuację z szachownicy. Dowolny konik może poruszać się jedynie zgodnie z zaznaczonymi krawędziami.
1
12/28/2016
Grafy
D. Makowiec: F: sekwencjonowanie DNA
3
Inna szachownica:
2 6
4 7
9 11
Dostępne ruchy to za mało, by ocenić czy konie mogą tu przeskoczyć przez siebie, zmienić kolejność
„Inteligentna” reprezentacja możliwych operacji pozwala to ocenić- tak tu konie mogą zmienić względem siebie kolejność.
Grafy
Obsesja Eulera (1735r) : Problem mostów Królewca: czy można tak zaplanować spacer po mieście, aby przejść po każdym moście i to tylko raz?
D. Makowiec: F: sekwencjonowanie DNA
4
1
4
22
3 Mapa miasta graf G(V, E ): wierzchołki V: „suchy” ląd, krawędzie E: mosty
1
2
4
3
2
12/28/2016
Grafy
5
D. Makowiec: F: sekwencjonowanie DNA
Cykl Eulera
Czy ten graf ma cykl Eulera?
4
1
2
3
Odpowiedzi Eulera:
9 Tw 1: Skończony graf spójny, w którym każdy wierzchołek ma stopień parzysty, ma cykl Eulera
8 7
11
10
Tw 2: Skończony graf spójny, mający dokładnie dwa wierzchołki stopnia nieparzystego, ma drogę Eulera
12
Grafy Algorytm Fleury’ego : Input zbiór wierzchołków V (G)
5 6
D. Makowiec: F: sekwencjonowanie DNA
6
O(|E|)
i krawędzi skierowanych E(G) grafu G Output cykl (droga) S Eulera
1
Wybierz dowolny wierzchołek nieparzystego stopnia, jeśli istnieje. W przeciwnym wypadku wybierz dowolny v. S=v.
2
Jeśli z v nie wychodzi żadna krawędź, zatrzymaj się.
3
Jeśli z v wychodzi dokładnie jedna krawędź e do w, to dołącz w do drogi S= S+w, popraw V= V-{v}, E= E-{e} i przejdź do 5. Jeśli została więcej niż jedna krawędź, to wybierz taką e z v do w, po usunięciu której graf pozostaje spójny. Dołącz w do drogi, S= S+w, popraw E= E-{e} przyjmij v = w
4
5
Cykl Eulera w powyższym grafie: 1,2,3,4,5,6,3,7,2,9,11,8,7,12,11,10, 9,1
Wróć do 2.
3
12/28/2016
Grafy
D. Makowiec: F: sekwencjonowanie DNA
7
Graf skierowany spójny ma cykl Eulera wtedy i tylko wtedy , gdy in_deg(v)= out_deg(v) dla każdego wierzchołka v grafu. Graf skierowany spójny ma drogę Eulera wtedy i tylko wtedy, gdy • tylko jeden wierzchołek ma własność out_deg(v) - in_deg (v) =1 ; • tylko jeden wierzchołek ma własność in_deg(v) - out_deg (v) =1 ; • pozostałe wierzchołki mają stopnie in_ i out_ równe.
Grafy
D. Makowiec: F: sekwencjonowanie DNA
8
Artur Cayley ( ok.1850)
Cn H 2 n 2 Struktura połączeń w tych związkach to drzewo – graf spójny i acykliczny
drzewo swobodne
4
12/28/2016
Grafy
D. Makowiec: F: sekwencjonowanie DNA
9
D. Makowiec: F: sekwencjonowanie DNA
10
Propozycja gry Sir Williama Hamiltona (1857r.)
Grafy Propozycja gry Sir Williama Hamiltona
Problem NP-zupełny
5
12/28/2016
Grafy
D. Makowiec: F: sekwencjonowanie DNA
11
Cykl Eulera Dla danego grafu G=(V(G) , E(G) ) skonstruować cykl zbudowany ze wszystkich krawędzi, przy czym każda krawędź jest wykorzystana dokładnie raz. Cykl Hamiltona
Dla danego grafu G=(V(G) , E(G) ) skonstruować cykl , który odwiedza wszystkie wierzchołki dokładnie raz
Mamy efektywny algorytm Fleury ‘ego konstrukcji cyklu/drogi
Problem NP-zupełny
Jeśli w grafie G=G(V,E) bez pętli i krawędzi wielokrotnych jest odpowiednio dużo krawędzi, na przykład jeden z poniższych warunków jest spełniony : (1) |E| ≥ ½ (n-1) *(n-2) +2 , gdzie n=|V| (2) deg(v) ≥ n/2 , gdzie n=|V| (3) deg(v) + deg(w) ≥ n dla każdej pary niepołączonych krawędzią wierzchołków, to graf ma cykl Hamiltona
Grafy
D. Makowiec: F: sekwencjonowanie DNA
12
Graf z wagami G=G(V,E, w)
Rozwiązanie, w miarę efektywne, algorytmem Dijkstry.
6
12/28/2016
Grafy i genetyka
D. Makowiec: F: sekwencjonowanie DNA
Genialna obserwacja Seymoura Benzera (1950) dowodząca, że struktura genu jest liniowa
13
Watson i Crick odkryli strukturę podwójnej helisy DNA w 1953
• Normalny wirus T4 zabija pewną bakterię • Ale, jeśli T4 jest zmutowane (ważna część genu jest skasowana), to wirus traci moc zabijania bakterii. • Przypuśćmy, że bakteria jest zarażona dwoma takimi różnymi mutantami . • Czy taki atak bakteria przeżyje czy nie? • Dziwne- para różnych zmutowanych wirusów może zabić bakterie mimo, że każdy mutant z osobna nie zabija. Jak to można wytłumaczyć? https://www.dnalc.org/view/15881-Defining-the-gene.html
D. Makowiec: F: sekwencjonowanie DNA
14
7
12/28/2016
Grafy i genetyka
D. Makowiec: F: sekwencjonowanie DNA
15
Jeśli geny są liniowa strukturą , czyli
to
Grafy i genetyka
tak powinien wyglądać graf przeżywania
D. Makowiec: F: sekwencjonowanie DNA
16
Jeśli geny mają rozgałęzienie czyli :
to
tak powinien wyglądać graf przeżywania
8
12/28/2016
Grafy i genetyka
D. Makowiec: F: sekwencjonowanie DNA
17
Dwie hipotetyczne struktury organizacyjne genu: a) organizacja liniowa b) organizacja z rozgałęzieniami
Która prawdziwa? Rozstrzyga eksperyment
Grafy i genetyka
W
M1
M2
M3
D. Makowiec: F: sekwencjonowanie DNA
18
Mutacje M1 i M2 pokrywają się
9
12/28/2016
Grafy i genetyka Graf interwałowy
D. Makowiec: F: sekwencjonowanie DNA
19
Delecje i ich interwały
Przykład grafu interwałowego
Przykład grafu nieinterwałowego
Graf interwałowy
Niemożliwe jest ułożenie delecji tak, aby spełnione były relacje grafu.
D. Makowiec: F: sekwencjonowanie DNA
20
• Graf uporządkowania w czasie zestawu czynności. • Węzły grafu to czynności. • Krawędzie określają która operacja z którą jest realizowana równolegle. • Kolorowanie grafu– każde dwa sąsiadujące wierzchołki mają różne kolory, przy czym ilość użytych kolorów jest minimalna.
10
12/28/2016
Sekwencjonowanie DNA
D. Makowiec: F: sekwencjonowanie DNA
21
D. Makowiec: F: sekwencjonowanie DNA
22
Masz wiele egzemplarzy tej samej gazety pociętych na miliony części. Każdy egzemplarz jest pocięty inaczej. Znaczna część kawałków się pogubiła. Znaczna część jest pochlapana atramentem. Potrafisz odczytać oryginalną zawartość?
Eksperyment Sangera: Czytaj kawałki 500-700 nukleotydów jednocześnie
http://www.cs.unc.edu/~prins/Classes/555/
11
12/28/2016
Metoda Sangera: czytanie DNA
D. Makowiec: F: sekwencjonowanie DNA
23
Sekwencjonowanie DNA
D. Makowiec: F: sekwencjonowanie DNA
24
II etap: poskładać zsekwencjonowane fragmenty DNA
start Graf zupełny skierowany z wagami wyznaczonymi przez POKRYCIE etykiet wierzchołków: w(i,j) = rozmiar wspólnego przyrostka (suffix) i oraz przedrostka (prefix) j
Problem najkrótszego wspólnego łańcucha staje się problemem komiwojażera w tym grafie
12
12/28/2016
Sekwencjonowanie DNA
D. Makowiec: F: sekwencjonowanie DNA
25
POKRYCIE etykiet wierzchołków k oraz j to rozmiar najdłuższego wspólnego przyrostka (suffix) k , który jest zgodny z przedrostkiem (prefix) j Przykład: etykieta wierzchołka k: etykieta wierzchołka j:
ggcatcaaa aaaggcatc
pokrycie (k,j) =3
Przykład: Dane S = { ATC, CCA, CAG, TCC, AGT }
SSP
TSP AGT CCA ATC ATCCAGT TCC CAG
ATC 2
0
1
1
AGT
1 2
CCA
1
CAG
2 1
2 TCC
Powszechnie stosuje się strategie zachłanną. Uważa się, że strategia zachłanna ma tu gwarancję 2. Zatem możemy oczekiwać , że rzeczywista długość superłańcucha w* jest ½ w ≤ w*≤w
Macierze DNA
D. Makowiec: F: sekwencjonowanie DNA
26
SequencingByHybridization : SBH
• 1988: pierwsze pomysły dla macierzy DNA. Mało kto wierzy w powodzenie • 1991: technika syntezy polimerów sterowana światłem (light directed polymer synthesis) • 1994: pierwsza 64-kb micromacierz DNA
First microarray prototype (1989) First commercial DNA microarray prototype w/16,000 features (1994)
500,000 features per chip (2002)
Chip DNA: zestaw wszystkich sekwencji nukleotydowych o zadanej długości
13
12/28/2016
Sekwencjonowanie przez hybrydyzacje DNA
D. Makowiec: F: sekwencjonowanie DNA
27
SBH - jak to pracuje? •
Umieść wszystkie możliwe próbki DNA o zadanej długości (lmery) na płaskiej powierzchni tak, aby każda próbka była w innym , ale znanym miejscu. To nazywamy macierzą DNA
•
Zastosuj roztwór zawierający fluorescencyjnie oznaczone nieznane DNA na przygotowana macierz.
•
Fragmenty DNA hybrydyzują z tymi próbkami, które są komplementarne to jego podłańcuchów.
•
Korzystając ze detektora spektroskopowego, określ, do których próbek DNA hybrydyzowało. Uzyskujesz l-merowe widmo badanego DNA
•
Zastosuj algorytm kombinatoryczny aby zrekonstruować sekwencje nukleotydów w nieznanym DNA.
Sekwencjonowanie przez hybrydyzacje DNA
D. Makowiec: F: sekwencjonowanie DNA
28
Sekwencjonowane DNA przykleiło się do:
ATAG
AGGC TAGG
SuperŁańcuch:
GGCA GCAA
Sekwencjonowane DNA to ciąg komplementarny:
CAAA
Przykład uniwersalnej macierzy dla l-merów o długości l=4
14
12/28/2016
Sekwencjonowanie DNA przez hybrydyzacje Def: spectrum(s,l) - widmo ujawnionych l-merów w
D. Makowiec: F: sekwencjonowanie DNA
sekwencji DNA s w reprezentacji l-merów, to eksperymencie sekwencjonowania DNA
29
zbiór
UWAGA: Różne sekwencje DNA mogą produkować to samo widmo!! Spectrum( GTATCT ,2) = Spectrum( GTCTAT ,2) = {AT, CT, GT, TA, TC}
Sekwencjonowanie DNA przez hybrydyzacje
D. Makowiec: F: sekwencjonowanie DNA
30
Rozwiązanie problemu SBH jako ścieżki Hamiltona w grafie pokrywania się l-merów
Graf skierowany H • o wierzchołkach etykietowanych l-merami • o krawędziach jedynie wtedy, gdy pokrywanie wynosi l-1
Przykład: S = { ATG AGG TGC TCC GTC GGT GCA CAG }
H
ATG
AGG
ATGC A G G T C C
TGC
TCC
GTC
GGT
GCA
CAG
Ścieżka odwiedziła każdy wierzchołek tylko RAZ
15
12/28/2016
Sekwencjonowanie DNA przez hybrydyzacje
D. Makowiec: F: sekwencjonowanie DNA
31
Problem niejednoznaczności wyniku
S = { ATG TGG
TGC
GTG
GGC
GCA
GCG
CGT }
Graf pokryć:
H
Możliwość I: H
Możliwość II:
ATGCGTGGCA
H
ATGGCGTGCA
Sekwencjonowanie DNA przez hybrydyzacje
D. Makowiec: F: sekwencjonowanie DNA
32
Rozwiązanie problemu SBH jako ścieżki Eulera w grafie „(l-1) merów”
Graf skierowany o wierzchołkach etykietowanych l-1 merami o krawędziach jedynie wtedy, gdy odpowiedni l mer występuje w zbiorze widma
Przykład:
S = { ATG, TGG, TGC, GTG, GGC, GCA, GCG, CGT }
Wierzchołki: V = { AT, TG, GC, GG, GT, CA, CG } GT
AT
Krawędzie:
E=S
CG
TG
GC
GG
CA
ścieżka przechodząca przez każdą krawędź i to tylko raz
16
12/28/2016
Znajdź superłańcuch dla następujących 3-merów
D. Makowiec: F: sekwencjonowanie DNA
33
S1={ACA , ATC, ATG, CAT, GAT, TAC, TCT, TGA} S2={GAT, ACC, TGA, TCT, ATC, ATG, CTA, TAC}
Sekwencjonowanie białka, identyfikacja białka
insulina Algorytmika, wykład XIII
D. Makowiec: F: sekwencjonowanie DNA
34
[34]
17
12/28/2016
Sekwencjonowanie białka, identyfikacja białka
D. Makowiec: F: sekwencjonowanie DNA
35
Białka zbudowane są z 20 rodzajów aminokwasów. Aminokwasy poprzez złącza peptydowe łącza się w długie łańcuchy o długościach od 100 do 1000 aminokwasów. Białko może składać się z kilku łańcuchów peptydowych.
Algorytmika, wykład XIII
[35]
Sekwencjonowanie białka, identyfikacja białka
D. Makowiec: F: sekwencjonowanie DNA
36
1.Reakcje degradacji Edmana: metoda chemicznego odcinania pojedynczych aminokwasów od końca łańcucha
2.Techniki spektrometrii mas: poprzez fragmentacje peptydów , a następnie pomiar masy uzyskanych jonowych fragmentów
insulina
Algorytmika, wykład XIII
[36]
18
12/28/2016
Sekwencjonowanie białka identyfikacja białka
D. Makowiec: F: sekwencjonowanie DNA
37
A Fragmenty peptydowe, które otrzymał Sanger z insuliny bydlęcej za pomocą różnych metod. Białko jest dzielone na dwie części: łańcuch A i łańcuch B w wyniku procesu trawienia enzymatycznego.
B
Wyjaśnienie roli mostków dwusiarczkowych łączących różne cysteiny było wynikiem wieloletnich żmudnych prac laboratoryjnych Sangera.
Algorytmika, wykład XIII
[37]
Sekwencjonowanie białka, identyfikacja białka
D. Makowiec: F: sekwencjonowanie DNA
38
2015-01-15
Algorytmika, wykład XIII
[38]
19
12/28/2016
Sekwencjonowanie białka, identyfikacja białka
Peptyd i jego sekwencja aminokwasowa P= p1p2…… pn
39
jest rozrywany.
fragment N-terminalowy: Pi= p1p2…… pi
• • •
D. Makowiec: F: sekwencjonowanie DNA
fragment C-terminalowy: P-i= pi+1…… pn
Peptydy rozrywają się wzdłuż wiązań peptydowych Fragmenty zazwyczaj gubią chemiczne molekuły takie jak NH3 czy H2O Oznaczenie: bi to jony powstałe z Pi, yi to jony powstałe z P-i
2015-01-15
Algorytmika, wykład XIII
[39]
Sekwencjonowanie białka, identyfikacja białka
D. Makowiec: F: sekwencjonowanie DNA
40
Peptyd GPFNA i jego: N-terminalowe fragmenty: G, GP, GPF, GPFN C-terminalowe fragmenty: PFNA, FNA, NA, A
Algorytmika, wykład XIII
[40]
20
12/28/2016
Sekwencjonowanie białka, identyfikacja białka
D. Makowiec: F: sekwencjonowanie DNA
41
Rozerwane fragmenty są jonami. Ich masa może być pomniejszona o masę wody lub amoniaku
Problem sekwencjonowania białka: Zrekonstruować peptyd w oparciu o zestaw uzyskanych mas dla fragmentów jonowych. Algorytmika, wykład XIII
[41]
Sekwencjonowanie białka, identyfikacja białka
D. Makowiec: F: sekwencjonowanie DNA
42
Zliczanie pików wspólnych dla teorii ∆={…} i eksperymentu S
Zestaw mas wszystkich możliwych jonów
{1 , 2 ,...., k }
Algorytmika, wykład XIII
[42]
21
12/28/2016
Sekwencjonowanie białka, identyfikacja białka
D. Makowiec: F: sekwencjonowanie DNA
43
2015-01-15
Algorytmika, wykład XIII
[43]
22
