11/13/2014
Praca domowa nr 4
Rozwiązać problem częściowego trawienia PartialDigest(L)
korzystając z praktycznego algorytmu Place(L,X) dla
poniższego zbioru odległości
L={ 1, 1, 1, 2, 2, 3, 3, 3, 4, 4, 5, 5, 6, 6, 6, 9, 9, 10, 11, 12, 15}
1
2014-11-06
Baranowska Agnieszka
Barlikowski Mateusz
Bianek Marcin
Burkiewicz Aleksandra
Chomik Aleksandra
Dybowski Krzysztof
Goździk Maria
Habecki Piotr
Jackiewicz Łukasz
Kajzer Paulina
Kaszyński Milosz
Kisieliński Marcin
Kowalski Daniel
Kratochwil Anna
Murat Katarzyna
Nazim Aleksandra
Nowakowski Łukasz
Oktawiec Jacek
Piastowski Radosław
Puchalski Aleksander
Romanik Monika
Śleszyńska Aleksandra
Smardzewski Remigiusz
Sobolewski Bartosz
Stolarska Milena
Szczypior Hanna
Wszeborowska Karolina
Zawacka Dominika
źle
ok*
źle
OK
brak
brak
ok*
ok*
ok*
brak
brak
ok*
ok*
ok*
ok*
ok*
źle
źle
brak
źle
OK
ok*
ok*
brak
ok*
źle
źle
ok*
źle
źle
źle
źle
ok.*
źle
źle
źle
źle
ok.*
brak
ok.*
źle
źle
źle
ok.*
źle
źle
źle
źle
OK
źle
źle
źle
źle
źle
źle
źle
ndst
brak
ndst
ndst
brak
ndst
źle
ndst
OK
brak
źle
brak
źle
źle*
źle
OK
ndst
brak
brak
brak
OK
brak
brak
brak
ndst
ndst
brak
brak
Praca domowa nr 5
2
2014-11-06
Zaproponuj algorytm, napisz jego pseudokod, który ma mniej linii niż algorytm
przez nas stosowany.
1
11/13/2014
Wykład dla BIOINFORMATYKI
rok 2014/2015
Motywy regulacyjne w
sekwencjach DNA
I.
II.
III.
IV.
Problem znalezienia motywu regulacyjnego
Pojęcia użyteczne dla wyznaczania motywu
Problem łańcucha medianowego
Algorytm z wykorzystaniem drzewa binarnego
Prof. Danuta Makowiec
Instytut Fizyki Teoretycznej i Astrofizyki
p.353, tel.: 58 523 2466
[email protected]
Przypomnienie
4
2014-11-06
Motywy regulacyjne to krótkie sekwencje nukleotydów,
ułożone zwykle przed początkiem genu, które kontrolują
włączanie/wyłączanie 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.
•
•
•
•
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, ilustruje
część zachowaną i obszar zmian motywu
Poniżej przykład logo innego motywu (wysokości
liter odpowiadają częstościom mutacji)
T
T
T
T
T
G
G
G
G
G
GGGGA
AGAGA
GGGGA
AGAGA
AGGGA
2
11/13/2014
Pojęcia używane w opisie jakości motywu
5
Szukamy jednego motywu o długości l (u nas 8) w t (u nas 7) sekwencjach DNA
2014-11-06
1. Liczba rozważanych sekwencji DNA: t ( u nas 7) o zadanej długości: n ( u nas 40)
2. Wektor pozycji startowych
wstawek w łańcuchach DNA :
s=(s1,s2,…,st)
( u nas (8,19,3,5,31,27,15)
Zmienność
macierzy
dopasowania
3. Macierz dopasowania dla danego s:
Zestaw
nukleotydów
najczęściej
występują-
4. Macierz profilu P(s) dla danego s:
5. Uzgodniony łańcuch profilu dla s
cych
Pojęcia używane w opisie jakości motywu
6
2014-11-06
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)
Score( s, DNA) 
M
j 1,...,l
Ocena
Score
lt
lt
4
P(s)
( j)
najlepsze dopasowanie
najgorsze dopasowanie
Max dla nasz ego
problemu to
8*7 =56
min to:
8*7/4=28
3
11/13/2014
7
Problem wyznaczenia motywu regulacyjnego
2014-11-06
Złożoność obliczeniowa
(n  l  1)t  (nt )
Problem łańcucha medianowego
8
2014-11-06
Problem 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 l-meru 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
w*  min TotalDist ( w, DNA)
w
4
11/13/2014
Problem łańcucha medianowego
9
2014-11-06
4l * tn  ( 4l tn)
równoważność
10
2014-11-06
ł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 )  14
Score( s, DNA)  42
Jeśli w to łańcuch konsensusu , to
A w drugą stronę?
5
11/13/2014
Podsumowanie wydajności
11
2014-11-06
problem
znalezienia motywu
Ilość możliwości:
problem wyznaczenia
łańcucha mediany
(n-l+1)t
4l n t
Algorytm z wykorzystaniem drzewa binarnego
12
2014-11-06
Kolejność
Kolejność
odwiedzanych
odwiedzanych
wierzchołków
wierzchołków
Zadać pytanie
?
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
6
11/13/2014
13
Przeszukiwanie w zupełnym drzewie binarnym
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?
2014-11-06
i - poziom drzewa
Kolejno
przesuwamy
się w głąb
drzewa
Odwiedzamy
liście
Startując ze słowa
a=(1,…,1)
wyliczamy
wszystkie kolejne
słowa
7
Download

motywy regulacyjne DNA