Motywy regulacyjne w sekwencjach DNA

11/1/2016

1

C: PROBLEM: MOTYWY REGULACYJNE W SEKWENCJACH DNA METODA: ALGORYTMY PRZESZUKIWANIA WYCZERPUJĄCE I Z OGRANICZENIAMI

Łańcuch konsensusu a łańcuch mediany

Wprowadzenie biologiczne

2

D. Makowiec: C: motywy regulacyjne DNA

Geny to relatywnie rzadkie sekwencje: -mamy O(1 000 000 000) par nukleotydów w genomie -mamy O(10 000) genów w genomie - jest O(1000) par nukleotydów w genie Zatem w przybliżeniu jedynie 1% kodu DNA zawiera sekwencje kodujące geny (bo: 10^3 * 10^4/10^9)

3’ • Obszary regulacyjne ( promocji) są ulokowane 100-1000 bp przed sekwencją kodującą. • Specjalne białka ( Transciption Factors, TF, enzymy transkrypcyjne) przyklejają się do odpowiadających im sekwencji DNA, znajdujących się w danym obszarze regulacyjnym genu (Transcription Factor Binding Sites, TFBS) • Przyklejenie tego specjalnego białka powoduje odseparowanie nici DNA , co umożliwia rozpoczęcie procesu transkrypcji przez polimerazę RNA • Sekwencje DNA tworzące TFBS nazywamy MOTYWAMI.

1

11/1/2016

Wprowadzenie biologiczne

D. Makowiec: C: motywy regulacyjne DNA

3

Przykład:

TCGGGGATTTCC : motyw regulacyjny genów odpornościowych muszki owocówki. •

Pewne białka są wytwarzane przez organizm jedynie w określonych warunkach, na przykład przy infekcji. •

Sekwencja TCGGGGATTTCC (zwana NK-B binding site) to miejsce przywiązywania się białka (enzym transkrypcyjny NF- B), które to aktywuje lub zwalnia polimerazę RNA do transkrypcji genu, który za motywem się rozpoczyna.

Motywy regulacyjne to krótkie sekwencje nukleotydów, ułożone zwykle przed początkiem genu, które kontrolują ekspresję genów. Szukanie motywu ( nieformalnie) to problem odnalezienia sekwencji regulujących, gdy nie ma bez wiedzy wstępnej, jak sekwencja wygląda. Ale przypuszczamy, że te sekwencje powinny występować stosunkowo często.

Jak odróżnić motyw od losowego bałaganu?

D. Makowiec: C: motywy regulacyjne DNA

4

Umiesz odszukać wstawione motywy do każdej losowo wygenerowanej sekwencji?

atgaccgggatactgatagaagaaaggttgggggcgtacacattagataaacgtatgaagtacgttagactcggcgccgccg acccctattttttgagcagatttagtgacctggaaaaaaaatttgagtacaaaacttttccgaatacaataaaacggcggga tgagtatccctgggatgacttaaaataatggagtggtgctctcccgatttttgaatatgtaggatcattcgccagggtccga gctgagaattggatgcaaaaaaagggattgtccacgcaatcgcgaaccaacgcggacccaaaggcaagaccgataaaggaga tcccttttgcggtaatgtgccgggaggctggttacgtagggaagccctaacggacttaatataataaaggaagggcttatag gtcaatcatgttcttgtgaatggatttaacaataagggctgggaccgcttggcgcacccaaattcagtgtgggcgagcgcaa cggttttggcccttgttagaggcccccgtataaacaaggagggccaattatgagagagctaatctatcgcgtgcgtgttcat aacttgagttaaaaaatagggagccctggggcacatacaagaggagtcttccttatcagttaatgctgtatgacactatgta ttggcccattggctaaaagcccaacttgacaaatggaagatagaatccttgcatactaaaaaggagcggaccgaaagggaag ctggtgagcaacgacagattcttacgtgcattagctcgcttccggggatctaatagcacgaagcttactaaaaaggagcgga

2

11/1/2016

Jak odróżnić motyw od losowego bałaganu?

5

D. Makowiec: C: motywy regulacyjne DNA

W drugą stronę : dane mamy losowe sekwencje nukleotydów

atgaccgggatactgataccgtatttggcctaggcgtacacattagataaacgtatgaagtacgttagactcggcgccgccg acccctattttttgagcagatttagtgacctggaaaaaaaatttgagtacaaaacttttccgaatactgggcataaggtaca tgagtatccctgggatgacttttgggaacactatagtgctctcccgatttttgaatatgtaggatcattcgccagggtccga gctgagaattggatgaccttgtaagtgttttccacgcaatcgcgaaccaacgcggacccaaaggcaagaccgataaaggaga tcccttttgcggtaatgtgccgggaggctggttacgtagggaagccctaacggacttaatggcccacttagtccacttatag gtcaatcatgttcttgtgaatggatttttaactgagggcatagaccgcttggcgcacccaaattcagtgtgggcgagcgcaa cggttttggcccttgttagaggcccccgtactgatggaaactttcaattatgagagagctaatctatcgcgtgcgtgttcat aacttgagttggtttcgaaaatgctctggggcacatacaagaggagtcttccttatcagttaatgctgtatgacactatgta ttggcccattggctaaaagcccaacttgacaaatggaagatagaatccttgcatttcaacgtatgccgaaccgaaagggaag ctggtgagcaacgacagattcttacgtgcattagctcgcttccggggatctaatagcacgaagcttctgggtactgatagca

Jak odróżnić motyw od losowego bałaganu?

D. Makowiec: C: motywy regulacyjne DNA

6

Wstawmy w nie motyw AAAAAAAAGGGGGGG

atgaccgggatactgatAAAAAAAAGGGGGGGggcgtacacattagataaacgtatgaagtacgttagactcggcgccgccg acccctattttttgagcagatttagtgacctggaaaaaaaatttgagtacaaaacttttccgaataAAAAAAAAGGGGGGGa tgagtatccctgggatgacttAAAAAAAAGGGGGGGtgctctcccgatttttgaatatgtaggatcattcgccagggtccga gctgagaattggatgAAAAAAAAGGGGGGGtccacgcaatcgcgaaccaacgcggacccaaaggcaagaccgataaaggaga tcccttttgcggtaatgtgccgggaggctggttacgtagggaagccctaacggacttaatAAAAAAAAGGGGGGGcttatag gtcaatcatgttcttgtgaatggatttAAAAAAAAGGGGGGGgaccgcttggcgcacccaaattcagtgtgggcgagcgcaa cggttttggcccttgttagaggcccccgtAAAAAAAAGGGGGGGcaattatgagagagctaatctatcgcgtgcgtgttcat aacttgagttAAAAAAAAGGGGGGGctggggcacatacaagaggagtcttccttatcagttaatgctgtatgacactatgta ttggcccattggctaaaagcccaacttgacaaatggaagatagaatccttgcatAAAAAAAAGGGGGGGaccgaaagggaag ctggtgagcaacgacagattcttacgtgcattagctcgcttccggggatctaatagcacgaagcttAAAAAAAAGGGGGGGa

3

11/1/2016

Jak odróżnić motyw od losowego bałaganu?

D. Makowiec: C: motywy regulacyjne DNA

7

A jeśli każdy motyw ma 4 mutacje?

atgaccgggatactgatAgAAgAAAGGttGGGggcgtacacattagataaacgtatgaagtacgttagactcggcgccgccg acccctattttttgagcagatttagtgacctggaaaaaaaatttgagtacaaaacttttccgaatacAAtAAAAcGGcGGGa tgagtatccctgggatgacttAAAAtAAtGGaGtGGtgctctcccgatttttgaatatgtaggatcattcgccagggtccga gctgagaattggatgcAAAAAAAGGGattGtccacgcaatcgcgaaccaacgcggacccaaaggcaagaccgataaaggaga tcccttttgcggtaatgtgccgggaggctggttacgtagggaagccctaacggacttaatAtAAtAAAGGaaGGGcttatag gtcaatcatgttcttgtgaatggatttAAcAAtAAGGGctGGgaccgcttggcgcacccaaattcagtgtgggcgagcgcaa cggttttggcccttgttagaggcccccgtAtAAAcAAGGaGGGccaattatgagagagctaatctatcgcgtgcgtgttcat aacttgagttAAAAAAtAGGGaGccctggggcacatacaagaggagtcttccttatcagttaatgctgtatgacactatgta ttggcccattggctaaaagcccaacttgacaaatggaagatagaatccttgcatActAAAAAGGaGcGGaccgaaagggaag ctggtgagcaacgacagattcttacgtgcattagctcgcttccggggatctaatagcacgaagcttActAAAAAGGaGcGGa

Jak odróżnić motyw od losowego bałaganu?

D. Makowiec: C: motywy regulacyjne DNA

8

Dlaczego odnalezienie motywu jest trudne?

atgaccgggatactgatAgAAgAAAGGttGGGggcgtacacattagataaacgtatgaagtacgttagactcggcgccgccg acccctattttttgagcagatttagtgacctggaaaaaaaatttgagtacaaaacttttccgaatacAAtAAAAcGGcGGGa tgagtatccctgggatgacttAAAAtAAtGGaGtGGtgctctcccgatttttgaatatgtaggatcattcgccagggtccga gctgagaattggatgcAAAAAAAGGGattGtccacgcaatcgcgaaccaacgcggacccaaaggcaagaccgataaaggaga tcccttttgcggtaatgtgccgggaggctggttacgtagggaagccctaacggacttaatAtAAtAAAGGaaGGGcttatag gtcaatcatgttcttgtgaatggatttAAcAAtAAGGGctGGgaccgcttggcgcacccaaattcagtgtgggcgagcgcaa cggttttggcccttgttagaggcccccgtAtAAAcAAGGaGGGccaattatgagagagctaatctatcgcgtgcgtgttcat aacttgagttAAAAAAtAGGGaGccctggggcacatacaagaggagtcttccttatcagttaatgctgtatgacactatgta ttggcccattggctaaaagcccaacttgacaaatggaagatagaatccttgcatActAAAAAGGaGcGGaccgaaagggaag ctggtgagcaacgacagattcttacgtgcattagctcgcttccggggatctaatagcacgaagcttActAAAAAGGaGcGGa AgAAgAAAGGttGGG ..|..|||.|..||| cAAtAAAAcGGcGGG

4

11/1/2016

Jak odróżnić motyw od losowego bałaganu?

D. Makowiec: C: motywy regulacyjne DNA

9

Dlaczego odnalezienie motywu jest trudne? • rozważany motyw składa się z 15-tu nukleotydów ( 15-merów) czyli motyw jest jednym z 4^15 możliwych 15-merów. • rozważamy 10 sekwencji DNA , każda składa się z 83 nukleotydów.

Zatem mamy do rozważenie 10 *(83 -15 +1) = 640 możliwych 15-merów.

Ale prawdopodobieństwo wystąpienia danego 15-meru jest 640 /4^15 640/1 073 741 824 = 5.960 10^-7. A więc powtórzenie 15-meru jest nieprawdopodobne i dlatego możemy spodziewać się sukcesu. Szukać będziemy l-merów , sekwencji o ustalonej długości l, które w danym zestawie sekwencji DNA występują stosunkowo często.

Jak odróżnić motyw od losowego bałaganu?

• • •

•

Motyw może mutować na mniej znaczących pozycjach Przedstawione tutaj 5 motywów ma mutacje w pozycji 3 i 5 Taka reprezentacja to tzw. logo motywu (sekwencja nukleotydów wraz z ich mutacjami) , ilustruje część zachowaną i obszar zmian motywu Poniżej przykład logo innego motywu (wysokości liter odpowiadają częstościom mutacji)

D. Makowiec: C: motywy regulacyjne DNA

T T T T T

G G G G G

10

GGGGA AGAGA GGGGA AGAGA AGGGA

5

11/1/2016

Pojęcia niezbędne do zdefiniowania problemu motywu

D. Makowiec: C: motywy regulacyjne DNA

11

Szukamy jednego motywu o długości l (u nas 8) w zestawie t (u nas 7) sekwencji DNA

Przestrzenią poszukiwań dla zestawu t sekwencji nukleotydowych o długości n jest tablica ( t wierszy x n kolumn )

Wektor pozycji startowych rozważanych l-merów 1. Aktualnie rozważany wektor pozycji startowych wstawek w łańcuchach (8,19,3,5,31,27,15)

Pojęcia niezbędne do zdefiniowania problemu motywu

D. Makowiec: C: motywy regulacyjne DNA

12

2. Macierz dopasowania dla danego s: Zmienność macierzy dopasowania

3. Macierz profilu P(s) dla danego s:

4. Uzgodniony łańcuch profilu dla s

Zestaw nukleotydów najczęściej występujących

6

11/1/2016

Pojęcia niezbędne do zdefiniowania problemu motywu

D. Makowiec: C: motywy regulacyjne DNA

13

Jak ocenić jakość uzyskanego łańcucha konsensusu?

P( s) M P(s) ( j)

5 5 6 4

5 5

6 6

Nasz zestaw DNA dla s daje : Score(s,DNA)=5 +5+ 6+ 4 +5 + 5+6+ 6 =42

największa wartość w j-tej kolumnie P(s) 5. Wynik dla łańcucha konsensu z punktu startowego s dla zadanego zestawu DNA

Score( s, DNA) 

M

j 1,...,l

Ocena Score

Problem znalezienia motywu: definicja

lt lt 4

P(s)

( j)

najlepsze dopasowanie najgorsze dopasowanie

Max dla naszego problemu to 8*7 =56 min to: 8*7/4=28

D. Makowiec: C: motywy regulacyjne DNA

14

Złożoność obliczeniowa

(n  l  1)t  (nt )

7

11/1/2016

Problem łańcucha medianowego

D. Makowiec: C: motywy regulacyjne DNA

15

Problem potraktowany INACZEJ 6. Odległość Hamminga pomiędzy l –merami w i v to ilość pozycji, w których l-mery w i v się różnią

7 Odległość pomiędzy w i l-merami zestawu DNA z pozycji s=(s1, s2,…, st)

8. Odległość pomiędzy w i l-merami zestawu DNA to minimalna odległość zaobserwowana w analizowanym zbiorze DNA od zadanego lmeru w

d H ( w, v) d H ( w, s ) 

d

j 1,..,t

H

( w, s j )

TotalDist ( w, DNA)  min d H ( w, s ) s Proste!

9. Łańcuch mediany to taki l-mer w* , dla którego TotalDistance(w,DNA) dla danego zestawu DNA jest najmniejszy

Problem łańcucha medianowego

w*  min TotalDist ( w, DNA) w

D. Makowiec: C: motywy regulacyjne DNA

16

4l * tn  ( 4l tn)

8

11/1/2016

Problem łańcucha medianowego

D. Makowiec: C: motywy regulacyjne DNA

17

równoważność łańcuch konsensusu

max Score( s, DNA)  s

a

M

j 1,...,l

P(s)

( j)

łańcuch medianowy

≡

w*  min TotalDist ( w, DNA) w

d H (( ATGCAACT ), s )  1  1  1  1  1  3  2  1  1  1  1  14 Score( s, DNA)  5  5  6  4  5  5  6  6  42

Jeśli w to łańcuch konsensusu , to

A w drugą stronę?

Podsumowanie:

D. Makowiec: C: motywy regulacyjne DNA

problem znalezienia motywu

Ilość możliwości:

(n-l+1)t

18

problem wyznaczenia łańcucha mediany

4l n t

9

11/1/2016

Przeszukiwanie w zupełnym drzewie binarnym

D. Makowiec: C: motywy regulacyjne DNA

19

’-’ Informacja pusta Kolejność Kolejność odwiedzanych odwiedzanych Poziom drzewa wierzchołków wierzchołków

Pierwsze litery rozdzielone

Drugie litery rozdzielone

Trzecie litery rozdzielone

Czwarte litery rozdzielone

Liście to zestaw wszystkich możliwych słów czteroliterowych zbudowanych z liter ’1’ i ’2’ Powiększamy zestaw przeszukiwanej informacji (liści) o informacje o wszystkich przodkach. Całe drzewo będzie przeglądane. Czy to się opłaci? Tak, pod warunkiem, że będziemy umieli właściwie oszacować wartość przodków.

Przeszukiwanie w zupełnym drzewie binarnym

D. Makowiec: C: motywy regulacyjne DNA

Kolejność Kolejność Kolejność odwiedzanych odwiedzanych odwiedzanych wierzchołków wierzchołków wierzchołków

20

Zadać pytanie ojcu takie, by było wiadomo czy warto interesować się jego synami

?

Pokażemy, jak wykorzystać tą obserwację, aby OGRANICZYĆ ZNACZĄCO przeszukiwaną przestrzeń

Porządek z prawej kolumny jest identyczny z kolejnością odwiedzania wierzchołków w pełnym drzewie binarnym przy zastosowaniu algorytmu PREORDER: najpierw ojciec, potem dzieci

10

11/1/2016

Przeszukiwanie w zupełnym drzewie binarnym

D. Makowiec: C: motywy regulacyjne DNA

21

Rozwiązanie iteracyjne dla PREORDER: Mamy alfabet k - literowy Budujemy kolejne L literowe słowa

Przy zadanym słowie a=(a1,..aL) , jakie słowo (liść) będzie następne Jeśli drzewo przyglądamy w porządku preorder ?

i - poziom drzewa

Kolejno przesuwamy się w głąb drzewa

lepiej

Odwiedzamy liście

Startując ze słowa a=(1,…,1) wyliczamy wszystkie kolejne słowa

NextVertex(a,i,L,k)

Przeszukiwanie w zupełnym drzewie binarnym

D. Makowiec: C: motywy regulacyjne DNA

22

Wszystkie możliwe sekwencje startowe

Mamy alfabet k = n-l+1 literowy odwiedzamy wierzchołki drzewa słów o długości L = t

11

11/1/2016

Przeszukiwanie w zupełnym drzewie binarnym

Pomysł: optymistyczne Score dla węzła wewnetrznego

D. Makowiec: C: motywy regulacyjne DNA

23

Dane są t= 3 DNA, o długości n=1 2 Szukamy motywu o długości l=10

Drzewo o nieinteresujących poddrzewach: ignorujemy poddrzewa każdego węzła, którego liście nie ma szansy, aby dostać wyższe Score niż najlepszy liść wierzchołków już odwiedzonych.

Przeszukiwanie w zupełnym drzewie binarnym

D. Makowiec: C: motywy regulacyjne DNA

24

12

11/1/2016

Praca domowa D

D. Makowiec: C: motywy regulacyjne DNA

25

1. Wyznacz macierz dopasowania (aligment), macierz profilu (profile) i łańcuch konsensusu (consensus) dla 5-merów o początkach w s= ( 1, 6, 4, 2, 4, 3,5) dla poniższych sekwencji DNA: CGGGGCTATGCAA TTTGAGGGTGCCC GGATGCAACTGGG AAGGATGCAAGCA AATTTTCTAAAAAG CTGGCAACTGGGA TACATGATCTGCAA • Podaj wynik Score(s) dla opisanego przypadku. • Oblicz TotalDistance dla następujących słów: CTAT i ATGA

2. Niech słowo a=242, o długości L=3, jest zbudowane z liter k=4-literowego alfabetu. Uzyskaj sześć kolejnych słów zgodnie z konstrukcją NextVertex(a,i,L,k)

13