Wykład Bioinformatyka
Wykład 6, 2008
1
1
Bioinformatyka
Wykład 6.
E. Banachowicz
Zakład Biofizyki Molekularnej
IF UAM
http://www.amu.edu.pl/~ewas
2
• Ćwiczenia do wykładu 5
• Macierze substytucji
• Jakość dopasowania
• Programowanie dynamiczne – algorytm
Alignment = uliniowienie
, zestawienie, porównanie sekwencji
Wykład 6
Wykład Bioinformatyka
Wykład 6, 2008
2
Punktacja zestawienia
• schemat wartościowania I:
– (match) dopasowany: +1
– (mismatch) niedopasowany: -1
– (gap) przerwa: -1
(nie-afiniczne kary za przerwy –każda przerwa traktowana jest tak samo)
3
• schemat wartościowania II:
– dopasowany: +1
– niedopasowany: -1
– otwarcie przerwy: G
– przedłużenie przerwy: L
(afiniczne kary za przerwy –kara za otwarcie, kary za przedłużenie )
S – punktacja za dopasowanie
Score = Max(S)
S =
(dopasowania) -
(niedopasowania) -
(przerwy)
Macierze Substytucji - PAM, BLOSUM
4
Wykład Bioinformatyka
Wykład 6, 2008
3
5
Macierz PAM
• Schemat punktacji bardziej złożony: macierze
substytucji
– PAM: macierze oparte na modelu ewolucyjnym
akceptowanych mutacji punktowych
(
1 jednostka PAM- stopień zróznicowania ewolucyjnego, w którym
zmienił się 1% aminokwasów
)
– częstość zmian „przypadkowych” – częstość tła
– częstość substytucji – częstość docelowa –zmiany
pojawiające się w białkach spokrewnionych
6
Macierz PAM250
• wartości w macierzy są proporcjonalne do
logarytmu z (cz. docelowej/cz.tła)
• zbudowana na podstawie analizy par
blisko spokrewnionych (1PAM) i
ekstrapolowana do 250PAM
• ekstrapolacje można przeprowadzić dla
różnych odległości ewolucyjnych PAM
• „duże” PAM stosuje się do
porównywania sekwencji o dużym
stopniu dywergencji ewolucyjnej
• „małe”PAM do badania sekwencji
podobnych
Wykład Bioinformatyka
Wykład 6, 2008
4
7
Macierze BLOSUM
• Powstały w oparciu o bazę BLOCKS –
dopasowanie sekwencji daleko
spokrewnionych
(oszacowanie częstotliwości
docelowych, bez modelu ewolucyjnego)
• Rodzina macierzy: różnice (indeksu)
związane są z maksymalnym stopniem
identyczności sekwencji wziętych do
obliczeń
()
8
BLOSUM62
BLOSUM90
– do analizy sekwencji blisko spokrewnionych
BOLSUM30 do analizy odległych ewolucyjnie
sekwencji
Wykład Bioinformatyka
Wykład 6, 2008
5
P
1
0
-1
-1
-3
0
-1
-1
0
-2
-3
-1
-2
-5
6
1
0
-6
-5
-1
-1
0
0
S
1
0
1
0
0
-1
0
1
-1
-1
-3
0
-2
-3
1
2
1
-2
-3
-1
0
0
0
T
1
-1
0
0
-2
-1
0
0
-1
0
-2
0
-1
-3
0
1
3
-5
-3
0
0
-1
0
W
-6
2
-4
-7
-8
-5
-7
-7
-3
-5
-2
-3
-4
0
-6
-2
-5
17
0
-6
-5
-6
0
Y
-3
-4
-2
-4
0
-4
-4
-5
0
-1
-1
-4
2
7
-5
-3
-3
0
10
-2
-3
-4
0
V
0
-2
-2
-2
-2
-2
-2
-1
-2
4
2
-2
2
-1
-1
-1
0
-6
-2
4
-2
-2
0
B
0
-1
2
3
-4
1
2
0
1
-2
-3
1
-2
-5
-1
0
0
-5
-3
-2
2
2
0
Z
0
0
1
3
-5
3
3
-1
2
-2
-3
0
-2
-5
0
0
-1
-6
-4
-2
2
3
0
X
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
A
R
N
D
C
Q
E
G
H
I
L
K
M
F
P
S
T
W
V
B
Z
X
Y
A
2
-2
0
0
-2
0
0
1
-1
-1
-2
-1
-1
-4
1
1
1
-6
0
0
0
0
-3
N
0
0
2
2
-4
1
1
0
2
-2
-3
1
-2
-4
-1
1
0
-4
-2
2
1
0
-2
D
0
-1
2
4
-5
2
3
1
1
-2
-4
0
-3
-6
-1
0
0
-7
-2
3
3
0
-4
C
-2
-4
-4
-5
12
-5
-5
-3
-3
-2
-6
-5
-5
-4
-3
0
-2
-8
-2
-4
-5
0
0
Q
0
1
1
2
-5
4
2
-1
3
-2
-2
1
-1
-5
0
-1
-2
-5
-2
1
3
0
-4
E
0
-1
1
3
-5
2
4
0
1
-2
-3
0
-2
-5
-1
1
0
-7
-2
2
3
0
-4
G
1
-3
0
1
-3
-1
0
5
-2
-3
-4
-2
-3
-5
-1
1
0
-7
-1
0
-1
0
-5
H
-1
2
2
1
-3
3
1
-2
6
-2
-2
0
-2
-2
0
-1
-1
-3
-2
1
2
0
0
I
-1
-2
-2
-2
-2
-2
-2
-3
-2
5
-2
-2
2
1
-2
-1
0
-5
4
-2
-2
0
-1
L
-2
-3
-3
-4
-6
-2
-3
-4
-2
2
6
4
2
2
-3
-3
-2
-2
2
-3
-3
0
-1
K
-1
3
1
0
-5
1
0
-2
0
-2
-3
5
0
-5
-1
0
0
-3
-2
1
0
0
-4
M
-1
0
-2
-3
-5
-1
-2
-3
-2
2
4
0
6
0
-2
-2
-1
-4
2
-2
-2
0
-2
-1
-5
-5
0
F
-4
-4
-4
-6
-4
-5
-5
-5
-2
1
2
-5
0
9
-5
-3
-3
0
7
Dayhoff PAM 250 Matrix
R
-2
6
0
-1
-4
1
-1
-3
2
-2
-3
3
0
-4
0
0
-1
2
-2
-1
0
0
-4
F
F
F
F
F
F
F
F
F
F
Y
Y
Y
Y
Y
F
Y
Y
Y
Y
F
F
Y
Y
Y
Y
F
Y
F
Y
Y
Y
F
F
Y
F
F
Y
zestawienie białek
wysoka punktacja
F Y
oznacza:
F -> Y
podstawienia są częste
+
Y -> F
podstawienia są częste
tam gdzie
F
jest utrwalone
tam gdzie
Y
jest utrwalone
Wykład Bioinformatyka
Wykład 6, 2008
6
P
1
0
-1
-1
-3
0
-1
-1
0
-2
-3
-1
-2
-5
6
1
0
-6
-5
-1
-1
0
0
S
1
0
1
0
0
-1
0
1
-1
-1
-3
0
-2
-3
1
2
1
-2
-3
-1
0
0
0
T
1
-1
0
0
-2
-1
0
0
-1
0
-2
0
-1
-3
0
1
3
-5
-3
0
0
-1
0
W
-6
2
-4
-7
-8
-5
-7
-7
-3
-5
-2
-3
-4
0
-6
-2
-5
17
0
-6
-5
-6
0
Y
-3
-4
-2
-4
0
-4
-4
-5
0
-1
-1
-4
2
7
-5
-3
-3
0
10
-2
-3
-4
0
V
0
-2
-2
-2
-2
-2
-2
-1
-2
4
2
-2
2
-1
-1
-1
0
-6
-2
4
-2
-2
0
B
0
-1
2
3
-4
1
2
0
1
-2
-3
1
-2
-5
-1
0
0
-5
-3
-2
2
2
0
Z
0
0
1
3
-5
3
3
-1
2
-2
-3
0
-2
-5
0
0
-1
-6
-4
-2
2
3
0
X
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
A
R
N
D
C
Q
E
G
H
I
L
K
M
F
P
S
T
W
V
B
Z
X
Y
A
2
-2
0
0
-2
0
0
1
-1
-1
-2
-1
-1
-4
1
1
1
-6
0
0
0
0
-3
N
0
0
2
2
-4
1
1
0
2
-2
-3
1
-2
-4
-1
1
0
-4
-2
2
1
0
-2
D
0
-1
2
4
-5
2
3
1
1
-2
-4
0
-3
-6
-1
0
0
-7
-2
3
3
0
-4
C
-2
-4
-4
-5
12
-5
-5
-3
-3
-2
-6
-5
-5
-4
-3
0
-2
-8
-2
-4
-5
0
0
Q
0
1
1
2
-5
4
2
-1
3
-2
-2
1
-1
-5
0
-1
-2
-5
-2
1
3
0
-4
E
0
-1
1
3
-5
2
4
0
1
-2
-3
0
-2
-5
-1
1
0
-7
-2
2
3
0
-4
G
1
-3
0
1
-3
-1
0
5
-2
-3
-4
-2
-3
-5
-1
1
0
-7
-1
0
-1
0
-5
H
-1
2
2
1
-3
3
1
-2
6
-2
-2
0
-2
-2
0
-1
-1
-3
-2
1
2
0
0
I
-1
-2
-2
-2
-2
-2
-2
-3
-2
5
-2
-2
2
1
-2
-1
0
-5
4
-2
-2
0
-1
L
-2
-3
-3
-4
-6
-2
-3
-4
-2
2
6
4
2
2
-3
-3
-2
-2
2
-3
-3
0
-1
K
-1
3
1
0
-5
1
0
-2
0
-2
-3
5
0
-5
-1
0
0
-3
-2
1
0
0
-4
M
-1
0
-2
-3
-5
-1
-2
-3
-2
2
4
0
6
0
-2
-2
-1
-4
2
-2
-2
0
-2
-1
-5
-5
0
F
-4
-4
-4
-6
-4
-5
-5
-5
-2
1
2
-5
0
9
-5
-3
-3
0
7
R
-2
6
0
-1
-4
1
-1
-3
2
-2
-3
3
0
-4
0
0
-1
2
-2
-1
0
0
-4
Dayhoff PAM 250 Matrix
F
F
F
F
F
F
F
F
F
F
Y
Y
Y
Y
Y
F
Y
Y
Y
Y
F
F
Y
Y
Y
Y
F
Y
F
Y
Y
Y
F
F
Y
F
F
Y
Pierwotne białko
zestawieni sekwencji
wysoka punktacja
W W
oznacza
:
inne podstawienia nie są możliwe
tam gdzie
W
jest utrwalone
W
W
W
W
W
W
W
W
W
W
W
W
W
W
W
W
W
W
W
Wykład Bioinformatyka
Wykład 6, 2008
7
P
1
0
-1
-1
-3
0
-1
-1
0
-2
-3
-1
-2
-5
6
1
0
-6
-5
-1
-1
0
0
S
1
0
1
0
0
-1
0
1
-1
-1
-3
0
-2
-3
1
2
1
-2
-3
-1
0
0
0
T
1
-1
0
0
-2
-1
0
0
-1
0
-2
0
-1
-3
0
1
3
-5
-3
0
0
-1
0
W
-6
2
-4
-7
-8
-5
-7
-7
-3
-5
-2
-3
-4
0
-6
-2
-5
17
0
-6
-5
-6
0
Y
-3
-4
-2
-4
0
-4
-4
-5
0
-1
-1
-4
2
7
-5
-3
-3
0
10
-2
-3
-4
0
V
0
-2
-2
-2
-2
-2
-2
-1
-2
4
2
-2
2
-1
-1
-1
0
-6
-2
4
-2
-2
0
B
0
-1
2
3
-4
1
2
0
1
-2
-3
1
-2
-5
-1
0
0
-5
-3
-2
2
2
0
Z
0
0
1
3
-5
3
3
-1
2
-2
-3
0
-2
-5
0
0
-1
-6
-4
-2
2
3
0
X
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
A
R
N
D
C
Q
E
G
H
I
L
K
M
F
P
S
T
W
V
B
Z
X
Y
A
2
-2
0
0
-2
0
0
1
-1
-1
-2
-1
-1
-4
1
1
1
-6
0
0
0
0
-3
N
0
0
2
2
-4
1
1
0
2
-2
-3
1
-2
-4
-1
1
0
-4
-2
2
1
0
-2
D
0
-1
2
4
-5
2
3
1
1
-2
-4
0
-3
-6
-1
0
0
-7
-2
3
3
0
-4
C
-2
-4
-4
-5
12
-5
-5
-3
-3
-2
-6
-5
-5
-4
-3
0
-2
-8
-2
-4
-5
0
0
Q
0
1
1
2
-5
4
2
-1
3
-2
-2
1
-1
-5
0
-1
-2
-5
-2
1
3
0
-4
E
0
-1
1
3
-5
2
4
0
1
-2
-3
0
-2
-5
-1
1
0
-7
-2
2
3
0
-4
G
1
-3
0
1
-3
-1
0
5
-2
-3
-4
-2
-3
-5
-1
1
0
-7
-1
0
-1
0
-5
H
-1
2
2
1
-3
3
1
-2
6
-2
-2
0
-2
-2
0
-1
-1
-3
-2
1
2
0
0
I
-1
-2
-2
-2
-2
-2
-2
-3
-2
5
-2
-2
2
1
-2
-1
0
-5
4
-2
-2
0
-1
L
-2
-3
-3
-4
-6
-2
-3
-4
-2
2
6
4
2
2
-3
-3
-2
-2
2
-3
-3
0
-1
K
-1
3
1
0
-5
1
0
-2
0
-2
-3
5
0
-5
-1
0
0
-3
-2
1
0
0
-4
M
-1
0
-2
-3
-5
-1
-2
-3
-2
2
4
0
6
0
-2
-2
-1
-4
2
-2
-2
0
-2
-1
-5
-5
0
F
-4
-4
-4
-6
-4
-5
-5
-5
-2
1
2
-5
0
9
-5
-3
-3
0
7
R
-2
6
0
-1
-4
1
-1
-3
2
-2
-3
3
0
-4
0
0
-1
2
-2
-1
0
0
-4
Dayhoff PAM 250 Matrix
Aminokwasy
%
Alanina
jest bardzo pospolita
skład aminokwasowy białek
{
Argos and McCaldon}
A
8.3
C
1.7
D
5.3
E
6.2
F
3.9
G
7.2
H
2.2
I
5.2
K
5.7
L
9.0
M
2.4
N
4.4
P
5.1
Q
4.0
R
5.7
S
6.9
T
5.8
V
6.6
W
1.3
Y
3.2
Tryptofan jest bardzo
rzadki
Wykład Bioinformatyka
Wykład 6, 2008
8
15
S, Ser
T, Thr
V,Val
I,Ile
K, Lys
R, Arg
Macierz PAM250
Małe, polarne
Małe, hydrofobowe
Duże, nałądowane
Statystyczne znaczenie dopasowań
• jaka jest wartość/ istotność dopasowania?
• Jaka jest wartość świadczy o homologii, a
jaka o przypadkowym podobieństwie?
Wykład Bioinformatyka
Wykład 6, 2008
9
Punktacja
17
S – punktacja za dopasowanie
Score = Max(S)
GGTCAGACATGA-CTGACAAGGGTATCGCCA
ATTGTCAAAGACTTGAGCTGATGTGCAAATT
obszar dopasowania
dopasowanie
niedopasowanie
przerwa
S =
(dopasowania) -
(niedopasowania) -
(przerwy)
Jakość dopasowania globalnego
Dla dopasowań globalnych:
porównanie obliczonej wartości dla danego dopasowania z
wartościami obliczonymi dla wielu dopasowań
przypadkowych sekwencji o podobnym składzie i długości
przykład:
dopasowanie sekwencji α hemoglobiny ludzkiej
i mioglobiny ludzkiej
Wykład Bioinformatyka
Wykład 6, 2008
10
dopasowanie
licz
b
a
ide
n
ty
c
z
n
y
c
h
am
ino
kw
asó
w
22 identyczne aminokwasy
23 identyczne aminokwasy
wszystkie możliwe
zestawienia sekwencji,
zliczanie identycznych
Jakość dopasowań
25.9% identycznych aminokwasów.
Czy jest to znaczące podobieństwo?
zestawienia sekwencji z przerwami,
zliczanie identycznych
38 identyczne aminokwasy
we fragmencie o długości 148
Wykład Bioinformatyka
Wykład 6, 2008
11
Jakość dopasowań
Dla dopasowań globalnych:
- porównanie obliczonej wartości dla danego dopasowania z
wartościami obliczonymi dla wielu dopasowań
przypadkowych sekwencji o podobnym składzie i długości
przypadkowe sekwencje o podobnym składzie:
sekwencja jednego z białek zostaje wielokrotnie „potasowna”
Jakość dopasowań
lic
zb
a
p
rz
yr
ó
w
n
ań
punktacja przyrównania
punktacja przyrównania
hemoglobina
α i mioglobiny
punktacja:
tożsamość: +10
przerwa: -25
szansa uzyskania takiego
odchylenia w przypadkowej
sekwencji wynosi 1: 10
20
Wykład Bioinformatyka
Wykład 6, 2008
12
Jakość dopasowań
punktacja:
BLOSUM62
otwarcie przerwy: -12
wydłużenie przerwy: -2
z macierzami substytucji
identyczne
podobne
= substytucje konserwatywne
Jakość dopasowań
punktacja:
BLOSUM62
otwarcie przerwy: -12
wydłużenie przerwy: -2
z macierzami substytucji
pozwala wykryć homologię białek
pokrewnych w mniejszym stopniu
Mioglobina ludzka
–
Leghemoglobina z łubinu
identyczność: 23%
Wykład Bioinformatyka
Wykład 6, 2008
13
Jakość dopasowań
punktacja przyrównania
(tylko identyczne)
punktacja przyrównania
(BLOSUM62)
li
c
zba
prz
yrów
na
ń
li
c
zba
prz
yrów
na
ń
(A) punktacja oparta o identyczność -szansa dopasowanie tylko na
zasadzie przypadku 1:20
(B) punktacja oparta o konserwatywne substytucje - szansa
dopasowanie tylko na zasadzie przypadku 1:300
Mioglobina ludzka – Leghemoglobina z łubinu
Jakość dopasowania
Dla sekwencji dłuższych niż 100 aminokwasów
• identyczność wyższa niż 25% prawie na pewno
nie jest przypadkowa – prawdopodobieństwo
homologii
• identyczność niższa niż 15% mało
prawdopodobne, żeby podobieństwo było
statystycznie istotne
Brak statystycznej istotności nie wyklucza homologii
Wykład Bioinformatyka
Wykład 6, 2008
14
hemoglobina, mioglobina i
leghemoglobina
Zachowawczość struktury przestrzennej
α hemoglobina (homo sapiens)
(
)
mioglobina (homo sapiens)
EMBOSS
http://www.ebi.ac.uk/emboss/align/index.html?
Wykład Bioinformatyka
Wykład 6, 2008
15
Global alignment
http://www.expasy.ch/tools/sim-prot.html
Wykład Bioinformatyka
Wykład 6, 2008
16
PRSS3 - evaluates the significance of a
protein sequence alignment
http://www.ch.embnet.org/software/PRSS_form.html
Jakość dopasowania lokalnego
Dla dopasowań lokalnych:
podstawą jest rozkład wartości granicznej,
scharakteryzowanej paramerami K i λ
(A) Funkcja gęstości prawdopodobieństwa = rozkład wartości granicznej
E(S) rozkład
spodziewanych dopasowań,
które mają wartość
przynajmniej równą S
Wykład Bioinformatyka
Wykład 6, 2008
17
Jakość dopasowania lokalnego
(A) Funkcja gęstości prawdopodobieństwa = rozkład wartości granicznej
E(S) rozkład
spodziewanych dopasowań,
które mają wartość
przynajmniej równą S
E (S) = K m n exp(-λS)
34
Statystyczne znaczenie dopasowań
• jaka jest wartość/ istotność dopasowania?
Dla dopasowań globalnych:
porównanie obliczonej wartości dla danego dopasowania z
wartościami obliczonymi dla wielu dopasowań
przypadkowych sekwencji o podobnym składzie i długości
Dla dopasowań lokalnych:
podstawą jest rozkład wartości granicznej,
scharakteryzowanej paramerami K i λ
Wykład Bioinformatyka
Wykład 6, 2008
18
35
E (S) = K m n exp
-
λS
Expected value, wartość oczekiwana sekwencji
mających wartość conajmniej S
S
– bit score, punktacja podobieństwa
m
– range of alignment, długość porównywanego segmentu
n
– wielkość bazy
λ
- określa wpływ systemu punktowania
K
– liczba powtarzających się segmentów w przeszukiwanej sekwencji
Bit Score – „unormowany”score, watość uniezależniona od
długości sekwencji
Podsumowanie
• Algorytmy porównywania sekwencji oparte
na programowaniu dynamicznym
gwarantują znalezienie optymalnego
(najlepszego) zestawienia dwóch sekwencji
• wymagają dużych rezerw pamięci i czasu
Wykład Bioinformatyka
Wykład 6, 2008
19
37
Programowanie dynamiczne
• Metody dynamiczne dobre są do zestawienia
(porównania) dwóch sekwencji
Jeśli celem jest znalezienie sekwencji homologicznych przeszukać
trzeba bazę sekwencji.
Przeszukać = porównać każdą sekwencję w bazie z zadaną sekwencją
(query)
to może być trudne…..
• Metody dynamiczne są raczej powolne i
wymagają pamięci (na np. zapamiętanie
macierzy F(nm) = O(nm))
38
Programowanie dynamiczne
• Rozmiar baz danych (rośnie ekspotencjalnie)
– białkowa: ok. 3 000 000 000 reszt aminokwasowych
– nukleotydowa: 200 000 000 000 nukleotydów
• Czas pracy komputera z mocą obliczeniową 10
7
komórek macierzy/sekundę
• (pełne zestawienie metodami dynamicznymi)
– białko 300 aminokwasów: 25 godzin dla bazy
białkowej
– DNA 1000 nukleotydów: 5555 godzin (323 dni) w
GenBanku
(wg. W. Makałowskiego)
Wykład Bioinformatyka
Wykład 6, 2008
20
Algorytm Needleman -Wunsh’a
A
G
A
C
T
A
G
C
G
A
G
A
C
G
T
znaleźć zestawienie z max score !
macierz F
elementy F
ij
sekwencja B
sekwencja A
F
00
= 0
0
F
0j
= 0
0
0
0
0
0
0
0
F
i0
= 0
0
0
0
0
0
0
0
0
powtarzaj F
ij
= max(F
i-1,j-1
+ S(A
i
,B
j
), F
i,j-1
+ d, F
i-1,j
+ d)
Algorytm Needleman -Wunsh’a
pseudo-code (tworzenie macierzy F):
for i=0 to lengh(A)-1
F(i,0) <- 0
for j=0 to lengh(B)-1
F(0,j) <- 0
for i=1 to lengh(A)
for j=1 to lengh(B)
{
choice1 <- F(i-1,j-1 + S(A(i),B(j))
choice2 <- F(i-1,j) + d
choice3 <- F(i,j-1) + d
F(i,j) <- max(choice1,choice2,choice3)
}
F
0j
= 0
F
i0
= 0
Wykład Bioinformatyka
Wykład 6, 2008
21
Algorytm Needleman -Wunsh’a
ten element macierzy F
ma zawsze, dla każdego
zestawienia najwyższą wartość
Odtworzenie zestawienia sekwencji, dającego najwyższą punktację, polega na
sprawdzaniu źródeł (3 możliwości), z których można dotrzeć do danego punktu i,j:
•jeśli choice1 to zestawienie A(i) z B(j)
•jeśli choice2 to zestawinie A(i) z przerwą
•jeśli choise3 to zestawienia B(j) z przerwą
Algorytm Needleman -Wunsh’a
pseudo-code (budowania zestawienia):
AlignmentA <- „”
AlignmentB <- „”
i <- length(A)-1
j <- length(B)-1
while (i>0 AND j>0)
{
Score <- F(i,j)
ScoreDiag <- F(i-1,j-1)
ScoreUp <- F(i, j-1)
ScoreLeft <- F(i-1,j)
if (Score – S(A(i),B(j))==ScoreDiag
{
AlignmentA <- A(i)+ AlignmentA
AlignmentB <- B(j)+ AlignmentB
i <- i-1
j <- j-1
} …
Wykład Bioinformatyka
Wykład 6, 2008
22
Algorytm Needleman -Wunsh’a
Score <- F(i,j)
ScoreDiag <- F(i-1,j-1)
ScoreUp <- F(i, j-1)
ScoreLeft <- F(i-1,j)
if (Score – S(A(i),B(j))==ScoreDiag
{
AlignmentA <- A(i)+ AlignmentA
AlignmentB <- B(j)+ AlignmentB
i <- i-1
j <- j-1
}
else if (Score == ScoreLeft – d)
{
AlignmentA <- A(i)+ AlignmentA
AlignmentB <- „-” + AlignmentB
i <- i-1
}……
Algorytm Needleman -Wunsh’a
else if (Score == ScoreLeft – d)
{
AlignmentA <- A(i)+ AlignmentA
AlignmentB <- „-” + AlignmentB
i <- i-1
}
otherwise (Score == ScoreUp – d)
{
AlignmentA <- „-” + AlignmentA
AlignmentB <- B(j)+ AlignmentB
j <- j-1
}
}
while (i>=0)
{…….
Wykład Bioinformatyka
Wykład 6, 2008
23
Algorytm Needleman -Wunsh’a
while (i>=0)
{
AlignmentA <- A(i) + AligmentA
AlignmentB <- „-” + AligmentB
i <- i-1
}
while (j>=0)
{
AlignmentA <- „-” + AligmentA
AlignmentB <- B(j) + AligmentB
j <- j-1
}
}
46
Następny wykład
• porównanie wielosekwencyjne
• BLAST, FASTA
• w poszukiwanie wspólnego przodka
KONIEC
Wykład Bioinformatyka
Wykład 6, 2008
24
ćwiczenia
47
Dopasowanie Globalne
-cząsteczki jednodomenowe
• Adresy:
– Expasy:
– NCBI:
• Narzędzia:
– Bl2seq (NCBI)
– SIM + LALNVIEW (ExPasy)
– LALIGN (EMBNet)
– Align (EMBOSS)
– SMART:
http://smart.embl-heidelberg.de/
48
Wykład Bioinformatyka
Wykład 6, 2008
25
Dopasowanie globalne
• Trypsyna: (mysz) P07146, (langusta)
P00765
• Zeta-krystalina (soczewka oka kręgowców)
Q08257, oksydoreduktaza chininowa
(E.Coli) P28304
49
50
Wykład Bioinformatyka
Wykład 6, 2008
26
51
52
Wykład Bioinformatyka
Wykład 6, 2008
27
53
S-S
S-S
S-S
Składowa centrum aktywnego, odpowiedzialna za specyficzność substratową
Układ przeniesienia ładunku
Porównaj z:
http://www.expasy.org/uniprot/P07146
http://www.expasy.org/uniprot/P00765
54
Wykład Bioinformatyka
Wykład 6, 2008
28
55
Bl2seq:
http://www.ncbi.nlm.nih.gov/blast/bl2seq/wblast2.cgi
56
Wykład Bioinformatyka
Wykład 6, 2008
29
57
DotPlot- Dotter
• Dotter:
http://sonnhammer.sbc.su.se/Dotter.html
• wykrywają fragmenty powtarzalne i rearanżacje
• opierają się na ocenie wizualnej – czasami skuteczniejszej niż
alignment
• idealny do szukania lokalnego podobieństwa
58
Przykład:
•czynnik krzepnięcia XII (F12): P00748
•aktywator tkankowo specyficznego plazminogenu (PLAT): P00750
(Bioinformatyka. Podręcznik do analizy genów i białek. A.D. Baxevanis, B.F.F. Quellette,
PWN, 2005 )
Wykład Bioinformatyka
Wykład 6, 2008
30
Dotter - sekwencje
59
Dotter - sekwencje
60
Wykład Bioinformatyka
Wykład 6, 2008
31
Dotter
61
SMART (
http://smart.embl-heidelberg.de/)
62
>gi|33877196|gb|AAH02795.2| PLAT protein [Homo sapiens]
>gi|180359|gb|AAA51986.1| coagulation factor XII
FN1
fibrynonektyna typ I, powtarzalna jednostka
FN2
fibrynonektyna typ II, powtarzalna jednostka
EGF
moduł nabłonkowego czynnika wzrostu
KR
domena typu kringle
Tryp SPc
domena katalityczna zapewniająca aktywność
proteinazy serynowej
Wykład Bioinformatyka
Wykład 6, 2008
32
63
czynnik krzepnięcia krwi
ak
ty
w
ato
r
tk
an
k
o
w
o
s
p
ec
y
ficzn
eg
o
p
lazm
in
o
g
en
u
64
czynnik krzepnięcia krwi
ak
ty
w
ato
r
tk
an
k
o
w
o
s
p
ec
y
ficzn
eg
o
p
lazm
in
o
g
en
u
Wykład Bioinformatyka
Wykład 6, 2008
33
65
czynnik krzepnięcia krwi
ak
ty
w
ato
r
tk
an
k
o
w
o
s
p
ec
y
ficzn
eg
o
p
lazm
in
o
g
en
u
66
PYSVGFREADAATSFLRAARSGNLDKALDHLRNGVDINTCNQNGLNGLHLASKEGHVKMV
VELLHKEIILETTTKKGNTALHIAALAGQDEVVRELVNYGANVNAQSQKGFTPLYMAAQE
NHLEVVKFLLENGANQNVATEDGFTPLAVALQQGHENVVAHLINYGTKGKVRLPALHIAA
RNDDTRTAAVLLQNDPNPDVLSKTGFTPLHIAAHYENLNVAQLLLNRGASVNFTPQNGIT
PLHIASRRGNVIMVRLLLDRGAQIETKTKDELTPLHCAARNGHVRISEILLDHGAPIQAK
TKNGLSPIHMAAQGDHLDCVRLLLQYDAEIDDITLDHLTPLHVAAHCGHHRVAKVLLDKG
AKPNSRALNGFTPLHIACKKNHVRVMELLLKTGASIDAVTESGLTPLHVASFMGHLPIVK
NLLQRGASPNVSNVKVETPLHMAARAGHTEVAKYLLQNKAKVNAKAKDDQTPLHCAARIG
HTNMVKLLLENNANPNLATTAGHTPLHIAAREGHVETVLALLEKEASQACMTKKGFTPLH
VAAKYGKVRVAELLLERDAHPNAAGKNGLTPLHVAVHHNNLDIVKLLLPRGGSPHSPAWN
GYTPLHIAAKQNQVEVARSLLQYGGSANAESVQGVTPLHLAAQEGHAEMVALLLSKQANG
NLGNKSGLTPLHLVAQEGHVPVADVLIKHGVMVDATTRMGYTPLHVASHYGNIKLVKFLL
QHQADVNAKTKLGYSPLHQAAQQGHTDIVTLLLKNGASPNEVSSDGTTPLAIAKRLGYIS
VTDVLKVVTDETSFVLVSDKHRMSFPETVDEILDVSEDEGEELISFKAERRDSRDVDEEK
ELLDFVPKLDQVVESPAIPRIPCAMPETVVIRSEEQEQASKEYDEDSLIPSSPATETSDN
ISPVASPVHTGFLVSFMVDARGGSMRGSRHNGLRVVIPPRTCAAPTRITCRLVKPQKLST
PPPLAEEEGLASRIIALGPTGAQFLSPVIVEIPHFASHGRGDRELVVLRSENGSVWKEHR
SRYGESYLDQILNGMDEELGSLEELEKKRVCRIITTDFPLYFVIMSRLCQDYDIIGPEGG
SLKSKLVPLVQATFPENAVTKRVKLALQAQPVPDELVTKLLGNQATFSPIVTVEPRRRKF
HRPIGLRIPLPPSWTDNPRDSGEGDTTSLRLLCSVIGGTDQAQWEDITGTTKLVYANECA
NFTTNVSARFWLSDCPRTAEAVNFATLLYKELTAVPYMAKFVIFAKMNDPREGRLRCYCM
TDDKVDKTLEQHENFVEVARSRDIEVLEGMSLFAELSGNLVPVKKAAQQRSFHFQSFREN
RLAMPVKVRDSSREPGGSLSFLRKAMKYEDTQHILCHLNITMPPCAKGSGAEDRRRTPTP
LALRYSILSESTPGSLSGTEQAEMKMAVISEHLGLSWAELARELQFSVEDINRIRVENPN
SLLEQSVALLNLWVIREGQNANMENLYTALQSIDRGEIVNMLEGSGRQSRNLKPDRRHTD
RDYSLSPSQMNGYSSLQDELLSPASLGCALSSPLRADQYWNEVAVLDAIPLAATEHDTML
EMSDMQVWSAGLTPSLVTAEDSSLECSKAEDSDATGHEWKLEGALSEEPRGPELGSLELV
EDDTVDSDATNGLIDLLEQEEGQRSEEKLPGSKRQDDATGAGQDSENEVSLVSGHQRGQA
RITHSPTVSQVTERSQDRLQDWDADGSIVSYLQDAAQGSWQEEVTQGPHSFQGTSTMTEG
LEPGGSQEYEKVLVSVSEHTWTEQPEAESSQADRDRRQQGQEEQVQEAKNTFTQVVQGNE
FQNIPGEQVTEEQFTDEQGNIVTKKIIRKVVRQIDLSSADAAQEHEEVTVEGPLEDPSEL
EVDIDYFMKHSKDHTSTPNP
Wykład Bioinformatyka
Wykład 6, 2008
34
67
68
Wykład Bioinformatyka
Wykład 6, 2008
35
69
http://myhits.isb-sib.ch/cgi-bin/dotlet