czwarty_beamer.pdf
(
289 KB
)
Pobierz
Bioinformatyka Wyklad IV
Bioinformatyka
IV. Dopasowania (alignment’y) sekwencji.
dr Marcin Goł¦biewski
Zakład Biotechnologii,
Wydział Biologii i Nauk o Ziemi,
Uniwersytet Mikołaja Kopernika,
Toru«
MarcinGoł¦biewskiPh.D. BioinformatykaWykładIV
Wst¦p
Przeszukiwanie baz sekwencji w celu znalezienia sekwencji
podobnej do sekwencji kwerendowej jest obecnie jednym z
najwa»niejszych zada« bioinformatyki.
MarcinGoł¦biewskiPh.D. BioinformatykaWykładIV
Algorytm DP z afinicznym modelem kar za przerwy
Wynaleziono algorytm DP pozwalaj¡cy na stosowanie afinicznych
kar za przerwy (Gotoh, 1982) nale»¡cy do klasy
O
(
n
2
)
. Jest on
blisko spokrewniony z algorytmem Smith-Waterman’a (SW) i jest
obecnie najcz¦±ciej stosowanym algorytmem konstruuj¡cym
alignment’y dwóch sekwencji.
Wymaga on nieco wi¦cej pami¦ci i jest ok. 2
×
bardziej zło»ony
obliczeniowo.
Równania rekurencji maj¡ w nim posta¢:
8
>
<
>
:
T
(
i
,
j
)
=
max
T
(
i
−
1
,
j
−
1
)
+
W
(
x
i
,
y
j
)
Ix
(
i
−
1
,
j
−
1
)
+
W
(
x
i
,
y
j
)
Iy
(
i
−
1
,
j
−
1
)
+
W
(
x
i
,
y
j
)
(
T
(
i
−
1
,
j
)
−
d
Ix
(
i
−
1
,
j
)
−
e
Ix
(
i
,
j
)
=
max
(
T
(
i
,
j
−
1
)
−
d
Iy
(
i
,
j
−
1
)
−
e
Iy
(
i
,
j
)
=
max
MarcinGoł¦biewskiPh.D. BioinformatykaWykładIV
Algorytm DP z afinicznym modelem kar za przerwy
P C A W H E A E
-
0
-
0
-
0
-
0
-
0
-
0
-
0
-
0
-
0
00 00 00 00 00 00 00 00 00
H
-
0
"
-1
"
-1
"
-1
"
-1
-
-1
-1
"
-1
-
-1
00 -10 -20 -30 -40 -510 00 -10 -20
E
-
0
-2
"
-2
-
-2
"
-2
"
0
-
-2
-2
-
-2
00 -10 -20 -30 -40 -50 -616 65 511
A
-
0
-3
-
-3
-
-3
"
-3
"
-1
"
6
-
-3
1
00 -10 -20 -35 -40 -50 -65 -521 1110
G
-
0
-4
-4
-
-4
-
-4
"
-2
"
5
"
11
-
0
00 -10 -20 -30 -42 -50 -62 -711 118
C
-
0
-5
-
-5
-5
-5
-3
"
4
"
10
"
8
00 -10 -213 32 20 10 01 -19 -18
A
-
0
-6
"
3
-
-6
-6
-4
3
"
9
-
7
00 -10 -22 -318 85 75 65 514 48
W
-
0
-7
"
2
"
8
-
-5
-5
2
8
6
00 -10 -20 -35 -433 2320 2219 2118 2017
G
-
0
-8
"
1
"
7
"
23
-
10
9
8
7
00 -10 -20 -37 -320 1031 2118 2020 1916
H
-
0
-9
"
0
"
6
"
22
-
21
-
8
10
6
00 -10 -20 -34 -419 931 2131 2119 2020
E
-
0
-10
"
-1
"
5
"
21
"
21
-
21
-
9
10
00 -10 -20 -34 -418 821 1137 2730 2632
E
-
0
-10
"
-2
"
4
"
20
"
20
"
27
-
20
-
22
00 -10 -20 -33 -417 720 1033 2336 2636
Macierze
T
,
I
x
i
I
y
,orazwarto±ci“wska¹nika”dlasekwencjiX=PCAWHEAE,Y=HEAGCAWGHEE,macierz
wagowaBLOSUM62,
d
=
10,
e
=
1.
MarcinGoł¦biewskiPh.D. BioinformatykaWykładIV
Algorytm DP z afinicznym modelem kar za przerwy
P C A W H E A E
-
0
-
0
-
0
-
0
-
0
-
0
-
0
-
0
-
0
00 00 00 00 00 00 00 00 00
H
-
0
"
-1
"
-1
"
-1
"
-1
-
-1
-1
"
-1
-
-1
00 -10 -20 -30 -40 -510 00 -10 -20
E
-
0
-2
"
-2
-
-2
"
-2
"
0
-
-2
-2
-
-2
00 -10 -20 -30 -40 -50 -616 65 511
A
-
0
-3
-
-3
-
-3
"
-3
"
-1
"
6
-
-3
1
00 -10 -20 -35 -40 -50 -65 -521 1110
G
-
0
-4
-4
-
-4
-
-4
"
-2
"
5
"
11
-
0
00 -10 -20 -30 -42 -50 -62 -711 118
C
-
0
-5
-
-5
-5
-5
-3
"
4
"
10
"
8
00 -10 -2
13
32 20 10 01 -19 -18
A
-
0
-6
"
3
-
-6
-6
-4
3
"
9
-
7
00 -10 -22 -3
18
85 75 65 514 48
W
-
0
-7
"
2
"
8
-
-5
-5
2
8
6
00 -10 -20 -35 -4
33
2320 2219 2118 2017
G
-
0
-8
"
1
"
7
"
23
-
10
9
8
7
00 -10 -20 -37 -320 1031 2118 2020 1916
H
-
0
-9
"
0
"
6
"
22
-
21
-
8
10
6
00 -10 -20 -34 -419 9
31
2131 2119 2020
E
-
0
-10
"
-1
"
5
"
21
"
21
-
21
-
9
10
00 -10 -20 -34 -418 821 11
37
2730 2632
E
-
0
-10
"
-2
"
4
"
20
"
20
"
27
-
20
-
22
00 -10 -20 -33 -417 720 1033 2336 2636
Macierze
T
,
I
x
i
I
y
,orazwarto±ci“wska¹nika”dlasekwencjiX=PCAWHEAE,Y=HEAGCAWGHEE,macierz
wagowaBLOSUM62,
d
=
10,
e
=
1.
MarcinGoł¦biewskiPh.D. BioinformatykaWykładIV
Plik z chomika:
xyzgeo
Inne pliki z tego folderu:
pierwszy_beamer.pdf
(591 KB)
drugi_beamer.pdf
(669 KB)
trzeci_beamer.pdf
(299 KB)
czwarty_beamer.pdf
(289 KB)
Inne foldery tego chomika:
0
algorytmika
artykuly
Bioinformatyka (patryska89)
bIOINFORMATYKA (waldiguzek)
Zgłoś jeśli
naruszono regulamin