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, x

i

∈ A i

j = 0, 1 . . . m, y

j

∈ A).

Zbiory te nazywamy sekwencjami.
Alignment’em sekwencji X i Y nazywamy uporządkowany
zbiór par P

l

= (x

i

l

, y

j

l

), takich, że ∀l i

l

> i

l −1

∧ j

l

> j

l −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)

P

l

= (x

0

, y

0

), (x

2

, y

1

), (x

3

, y

2

), (x

4

, y

3

), (x

5

, y

6

)

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

Q

n

p

g

(insercje bądź delecje mogą

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 C Q 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-4

13

-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-2

10

-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-4

10

-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-3

15

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ądź 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