Bioinformatyka
Wykład III
Marcin Gołębiewski Ph.D.
Zakład Biotechnologii
Wydział Biologii i Nauk o Ziemi
Uniwersytet Mikołaja Kopernika
8 marca 2010
Marcin Gołębiewski Ph.D. Bioinformatyka Wykład III
Wstęp
Po co przeszukiwać bazy sekwencji?
Jak to robić?
Marcin Gołębiewski Ph.D. Bioinformatyka Wykład III
Alignment - dopasowanie sekwencji
Niech A będzie alfabetem (np. A = {A, T, G, C} dla sekwencji
nukleotydowej) z którego pochodzą symbole w dwóch zbiorach X i
Y o licznościach odpowiednio n i m (i = 0, 1 . . . n, xi " A i
j = 0, 1 . . . m, yj " A).
Zbiory te nazywamy sekwencjami.
Alignment em sekwencji X i Y nazywamy uporządkowany
zbiór par Pl = (xil , yjl ), takich, że "l il > il-1 '" jl > jl-1.
i = 0 1 2 3 4 g 5 (g=2)
x = A T G C A - - A
y = A - G C A T T A
j = 0 g 1 2 3 4 5 6 (g=1)
Pl = (x0, y0), (x2, y1), (x3, y2), (x4, y3), (x5, y6)
Marcin Gołębiewski Ph.D. Bioinformatyka Wykład III
Rodzaje alignmentów
Alignmenty dzielimy na dwie klasy:
1
globalne - dopasowane są całe sekwencje, niezależnie od
różnicy długości,
2
lokalne - dopasowane są najlepiej pasujące segmenty sekwencji.
Z przyczyn  obliczeniowych wyróżniamy:
alignmenty dwóch sekwencji (krótko: alignmenty),
alignmenty wielu sekwencji (multiple alignments - więcej niż
trzech).
Marcin Gołębiewski Ph.D. Bioinformatyka Wykład III
Ocena (score) alignmentu
Odróżnianie alignmentów  lepszych od  gorszych wymaga
jakiejś mierzalnej wartości.
Liczbę, która mówi o  dobroci alignmentu nazywamy score -
oceną.
Score zależy od:
1
Liczby par dopasowanych (np. AA),
2
liczby par niedopasowanych (np. AG),
3
wartości liczbowych przypisanych różnym parom w macierzy
wagowej,
4
liczby i długości przerw,
5
przyjętego sposobu liczenia kar za przerwy i ich wartości.
Matematycznie score jest sumą score wszystkich par symboli
w alignmencie i kar za przerwy.
Aligment o najwyższym możliwym score (dla danych
sekwencji, macierzy wagowej i kar za przerwy) nazywamy
alignmentem optymalnym.
Marcin Gołębiewski Ph.D. Bioinformatyka Wykład III
Macierz wagowa
Macierz wagowa to tablica w której wszystkim możliwym
parom symboli z danego alfabetu przypisano jakieś wartości
liczbowe.
Macierze wagowe mają prostą interpretację probabilistyczną -
im większy jest score przypisany danej parze symboli, tym
większe prawdopodobieństwo napotkania takiej pary w
 dobrych alignment ach i odwrotnie, im score jest mniejszy,
tym częściej parę można napotkać w przypadkowych
alignment ach.
Marcin Gołębiewski Ph.D. Bioinformatyka Wykład III
Kary za przerwy
Najczęściej stosuje się dwa rodzaje funkcji ważącej przerwy:
1
liniowe - GP(g) = dg
2
afiniczne - GP(g) = d + (g - 1)e
W modelu afinicznym d oznacza karę za otwarcie przerwy,
natomiast e karę za jej przedłużenie.
Ponieważ prawdopodobieństwo powstania przerwy o długości

n nie jest na ogół równe pg (insercje bądz
delecje mogą
n
zachodzić blokami), bardziej realistyczny jest model
afiniczny, który wprowadza mniejszą karę za przedłużenie już
otwartej przerwy.
Z tego powodu jest on szerzej stosowany, niż model liniowy.
Marcin Gołębiewski Ph.D. Bioinformatyka Wykład III
Macierze wagowa - przykład
Macierz wagowa BLOSUM62 (Henikoff i Henikoff, 1992),
skonstruowana na podstawie częstości par w bazie BLOCKS
(Henikoff i Henikoff 1991).
A R N D CQ E G H I L KM F P S TW Y V
A 5-2-1-2 -1-1-1 0 -2-1-2-1-1-3 -1 1 0 -3-2 0
R-2 7-1-2 -4 1 0-3 0-4-3 3-2-3 -3-1-1 -3-1-3
N-1-1 7 2 -2 0 0 0 1-3-4 0-2-4 -2 1 0 -4-2-3
D-2-2 2 8 -4 0 2-1 -1-4-4-1-4-5 -1 0-1 -5-3-4
C-1-4-2-413-3-3-3 -3-2-2-3-2-2 -4-1-1 -5-3-1
Q-1 1 0 0 -3 7 2-2 1-3-2 2 0-4 -1 0-1 -1-1-3
E-1 0 0 2 -3 2 6-3 0-4-3 1-2-3 -1-1-1 -3-2-3
G 0-3 0-1 -3-2-3 8 -2-4-4-2-3-4 -2 0-2 -3-3-4
H-2 0 1-1 -3 1 0-210-4-3 0-1-1 -2-1-2 -3 2-4
I-1-4-3-4 -2-3-4-4 -4 5 2-3 2 0 -3-3-1 -3-1 4
L-2-3-4-4 -2-2-3-4 -3 2 5-3 3 1 -4-3-1 -2-1 1
K-1 3 0-1 -3 2 1-2 0-3-3 6-2-4 -1 0-1 -3-2-3
M-1-2-2-4 -2 0-2-3 -1 2 3-2 7 0 -3-2-1 -1 0 1
F-3-3-4-5 -2-4-3-4 -1 0 1-4 0 8 -4-3-2 1 4-1
P-1-3-2-1 -4-1-1-2 -2-3-4-1-3-410-1-1 -4-3-3
S 1-1 1 0 -1 0-1 0 -1-3-3 0-2-3 -1 5 2 -4-2-2
T 0-1 0-1 -1-1-1-2 -2-1-1-1-1-2 -1 2 5 -3-2 0
W-3-3-4-5 -5-1-3-3 -3-3-2-3-1 1 -4-4-315 2-3
Y-2-1-2-3 -3-1-2-3 2-1-1-2 0 4 -3-2-2 2 8-1
V 0-3-3-4 -1-3-3-4 -4 4 1-3 1-1 -3-2 0 -3-1 5
Marcin Gołębiewski Ph.D. Bioinformatyka Wykład III
Konstrukcja alignmentu optymalnego
Istnieją algorytmy umożliwiające obliczenie alignmentu
optymalnego dowolnych dwóch sekwencji.
Alignment globalny oblicza się zgodnie z algorytmem
Needleman a-Wunscha.
Aligment lokalny konstruuje się przy pomocy algorytmu
Smith-Watermana.
Algorytmy te stosują technikę programowania dynamicznego -
podziału dużego problemu na mniejsze, łatwe do rozwiązania i
składania z tych prodproblemów całości rozwiązania.
Marcin Gołębiewski Ph.D. Bioinformatyka Wykład III
Przeszukiwanie baz sekwencji
Przeszukiwanie baz sekwencji polega na
1
dopasowaniu sekwencji kwerendowej do każdej sekwencji w
bazie (po kolei),
2
stwierdzeniu, które dopasowania są wynikiem przypadku
(losowe), a które są efektem wspólnego pochodzenia i
podobieństwa struktury (statystycznie istotne).
Do konstrukcji dopasowań można wykorzystać dowolny
algorytm, jednak te oparte na programowaniu dynamicznym
są zbyt wolne.
Marcin Gołębiewski Ph.D. Bioinformatyka Wykład III
Statystyczna istotność dopasowania
Statystyczna istotność dopasowania jest miarą  sensowności
alignmentu .
Dokładniej, mówi ona, jak prawdopodobne jest znalezienie w
losowej bazie sekwencji, której alignment z sekwencją
kwerendową będzie miał score większy lub równy score
aktualnego dopasowania.
Losowa baza sekwencji, to baza o wielkości takiej, jak
faktycznie przeszukiwana, w której pozamieniano litery, nie
zmieniając przy tym składu bazy - czyli ich częstości
występowania.
Jak widać, o istotności dopasowania można mówić wyłącznie
w kontekście przeszukiwania bazy sekwencji.
Marcin Gołębiewski Ph.D. Bioinformatyka Wykład III
Miary statystycznej istotności dopasowania
Istnieją dwie miary statystycznej istotności alignmentu:
1
E-value - oczekiwana liczba losowych sekwencji, których
alignmenty z sekwencją kwerendową będą miały score wyższy
lub równy score ocenianego dopasowania.
2
P-value - prawdopodobieństwo, że istnieje przynajmniej jedna
losowa sekwencja, której alignment z sekwencją kwerendową
będzie miał score większy bądz
równy score ocenianego
alignmentu.
E-value i p-value są ze sobą związane, dla wartości mniejszych
od 0.01 E(S) P(S).
Statystycznie istotne będą dopasowania, dla których e-value i
p-value będą dużo mniejsze od 1.
Standardowo uznaje się za próg istotności wartość 0.01
Marcin Gołębiewski Ph.D. Bioinformatyka Wykład III
Marcin Gołębiewski Ph.D. Bioinformatyka Wykład III