2013-04-14

1

Po co porównujemy sekwencje?

Identyfikacja sekwencji określonych eksperymentalnie.

Przewidywanie funkcji/struktury nieznanych genów/białek na podstawie homologii ze
znanymi sekwencjami.

Określenie odległości ewolucyjnej pomiędzy sekwencjami.

Elementy bioinformatyki

Porównywanie sekwencji biologicznych

2013-04-14

2

Homologia

Homologia określa wspólne pochodzenie ewolucyjne

ortologi: sekwencje pochodzące od wspólnego przodka których rozdzielenie
nastąpiło na drodze specjacji
paralogi: sekwencje pochodzące od wspólnego przodka których rozdzielenie
nastąpiło na drodze duplikacji genu
ksenologi: sekwencje których podobieństwo wynika z horyzontalnego transferu
genów (ang. lateral gene transfer, LGT)

Analogia: różne pochodzenie ewolucyjne lecz podobna funkcja

(konwergencja: podobne cechy powstają w odpowiedzi na podobne czynniki
środowiskowe)

Elementy bioinformatyki

Porównywanie sekwencji biologicznych

Homologia a podobieństwo

•

Homologia jakościowo definiuje pokrewieństwo sekwencji.

•

Podobieństwo pozwala na ilościowy opis wyniku przyrównania dwóch sekwencji
(wyrażone procentowo lub przez podanie ilości reszt podobnych).

Elementy bioinformatyki

Porównywanie sekwencji biologicznych

2013-04-14

3

Podobieństwo a identyczność

• W przypadku sekwencji nukleotydowych mówimy zazwyczaj jedynie o identyczności

(istnieją algorytmy oceniające puryny i pirymidyny w kategorii podobieństwa)

• Sekwencje białkowe:

o identyczność najczęściej wyrażona jest jako procent (liczba) identycznych reszt
o podobieństwo określa procent (liczbę) reszt charakteryzujących się podobnymi

właściwościami fizykochemicznymi:

o hydrofobowe, hydrofilowe
o polarne, niepolarne
o kwaśne, zasadowe
o aromatyczne, alifatyczne
o małe, rozbudowane

Elementy bioinformatyki

Porównywanie sekwencji biologicznych

Jak wnioskować o homologii sekwencji?

Elementy bioinformatyki

Porównywanie sekwencji biologicznych

Rost B. Protein Eng. 1999; 12; 85-94.

2013-04-14

4

Przyrównanie globalne i lokalne

Alignment: dopasowanie dwóch lub wielu (ang. Multiple Sequence Alignment, MSA) sekwencji
biologicznych. Praktycznie dopasowanie najczęściej tworzy się tak aby odpowiadające sobie reszty były
w tych samych kolumnach.

Przyrównanie globalne zakłada, iż sekwencje są podobne na całej długości. Metoda może być skutecznie
stosowana do porównywania blisko spokrewnionych sekwencji o zbliżonej długości.

Przyrównanie lokalne znajduje lokalne regiony o wysokim podobieństwie. Podejście można zastosować
do analizy sekwencji o różnej długości oraz takich które uległy większej dywergencji.

N

L

GPSTKD

FGKI

SES

R

EFDNQ

NLGPSTKDD

FGKI

LGPSTKDDQ

Globalne

|

||||

|

Lokalne

||||

Q

L

NQLERS

FGKI

NM

R

LEDALV

QNQLERSSN

FGKI

NQLERSSNN

Elementy bioinformatyki

Porównywanie sekwencji biologicznych

http://www.ebi.ac.uk/2can/tutorials/protein/align.html

Wprowadzanie przerw

•

Algorytmy przyrównywania sekwencji uwzględniają wprowadzanie przerw w sekwencjach

(odzwierciedlających insercje/delecje).

• Delecje/insercje są rzadsze z punktu widzenia ewolucji niż substytucje.
• Brak teorii pozwalającej na ustalenie optymalnej wysokości kar.

• Wprowadzenie przerwy jest zazwyczaj ujemnie punktowane.
• Otwarcie przerwy wiąże się z wyższą karą za przerwy niż jej poszerzenie.

𝑾 = 𝜸 + 𝜹 × (𝒌 − 𝟏)

Gdzie:
W – całkowita wartość kary za przerwę
γ – kara za otwarcie przerwy
δ – kara za poszerzenie przerwy
k – długość przerwy

Elementy bioinformatyki

Porównywanie sekwencji biologicznych

2013-04-14

5

Macierze punktowania

(ang. scoring matrix)

Punktacja sprowadzona jest do liczb całkowitych.

Zazwyczaj punktacja dodatnia przyznawana jest identycznym lub podobnym resztom, natomiast
negatywna lub zero różnym.

Najprostszy przykład macierzy punktowania opiera się o ocenę identyczności (identyczne=1, różne=0).

Punktowanie DNA często poza identycznością uwzględnia także ocenę tranzycji oraz transwersji (np.
identyczność=3; tranzycja=2; transwersja=0).

Punktowanie ze względu na cechy fizykochemiczne (sekwencje białkowe): macierze tworzone w oparciu
o podobieństwo fizykochemiczne aminokwasów.

Macierze punktowania substytucji aminokwasów (ang. substitution matrix): opracowane na podstawie
analizy substytucji aminokwasów obserwowanych dla grup podobnych sekwencji.

Elementy bioinformatyki

Porównywanie sekwencji biologicznych

Algorytmy przyrównania sekwencji

Metoda macierzy kropkowej

Elementy bioinformatyki

Porównywanie sekwencji biologicznych

http://www.ncbi.nlm.nih.gov/books/NBK6831/

http://www.csse.monash.edu.au/~lloyd/Seminars/2007-DPA/

2013-04-14

6

Macierze punktowania

PAM (ang. Point Accepted Mutation) opracowana przez Margaret Dayhoff w 1978r. Macierze PAM
zostały wyznaczone dla grupy 71 blisko spokrewnionych rodzin sekwencji (ponad 1500 sekwencji; >85%
identyczności). Macierz PAM1 określa częstość substytucji (wyrażone jako prawdopodobieństwo
podstawienia) dla każdej z reszt gdy 1% reszt w sekwencji ulegnie zmianie. Macierze PAM o wyższych
wartościach indeksów tworzone są przez przemnażanie macierzy PAM1 (PAM1

100

=PAM100). Wartość

indeksu przy macierzy PAM wzrasta wraz ze stopniem substytucji aminokwasów, co odpowiada
odległości ewolucyjnej .

BLOSUM (BLOcks SUbstitution Matrix) opracowane zostały przez Henikoff S. i Henikoff, J.G. w 1992
roku przy wykorzystaniu ponad 2000 konserwatywnych wzorców (ponad 500 rodzin, <60aa; bez
przerw). Macierze BLOSUM obliczane są jako logarytm ze stosunku częstości substytucji danej reszty
inną do oczekiwanego prawdopodobieństwa losowego wystąpienia takiej zmiany. Wartość indeksu przy
macierzy BLOSUM określa stopień identyczności sekwencji.

Elementy bioinformatyki

Porównywanie sekwencji biologicznych

Henikoff, S.; Henikoff, J.G. PNAS, 1992. 89, 10915–10919.

Macierze PAM

Elementy bioinformatyki

Porównywanie sekwencji biologicznych

http://www.biotec.tu-dresden.de/schroeder/group/teaching/elab/bioinfo1/lab8

PAM250

2013-04-14

7

Macierze BLOSUM

Elementy bioinformatyki

Porównywanie sekwencji biologicznych

http://www.birec.org/sandbox/omamasaudtutorial

BLOSUM 62

Macierze punktowania substytucji aminokwasów

• Macierze punktowania substytucji aminokwasów są obecnie najczęściej wykorzystywane przy

porównywaniu sekwencji białkowych. Powstały na bazie obserwacji empirycznych i okazały się
lepsze od macierzy opartych o cechy fizykochemiczne aminokwasów.

• Macierze PAM lepiej sprawdzają się przy tworzeniu przyrównania globalnego, natomiast

wykorzystując algorytmy bazujące na lokalnym przyrównaniu lepiej wybrać macierz BLOSUM.

• Najwyższe oceny przyznawane są za identyczność, wysokie oceny są też przypisywane resztom dla

których często obserwuje się substytucję.

Elementy bioinformatyki

Porównywanie sekwencji biologicznych

2013-04-14

8

Algorytmy przyrównania sekwencji

Metoda programowania dynamicznego

Elementy bioinformatyki

Porównywanie sekwencji biologicznych

http://lslwww.epfl.ch/biowall/VersionE/ApplicationsE/SequenceE.html

Algorytmy oparte o metodę

programowania dynamicznego

Algorytm Needlemann-Wunsch – oparty na programowaniu dynamicznym algorytm
przyrównania globalnego.

1

Algorytm Smith- Waterman umożliwia lokalne przyrównanie sekwencji bazując na
metodzie programowania dynamicznego.

2

[1] Needleman, S.B.; Wunsch, C.D.; Journal of Molecular Biology; 1970; 48; 443–53
[2] Smith, T. F.; Waterman, M. S. Journal of Molecular Biology; 1981; 147; 195–197.

Elementy bioinformatyki

Porównywanie sekwencji biologicznych

2013-04-14

9

Algorytmy Needlemann-Wunscha

𝑲𝒎𝒂𝒙 𝒊, 𝒋 =

K (i−1, j−1) + S(I, J)

K(i−1, j) + g
K(i, j−1) + g

Gdzie:
K (i, j) – punktacja dla komórki (i,j)
S (I,J) – punktacja dla podstawienia w komórce (i, j)
g – kara za przerwy

Elementy bioinformatyki

Porównywanie sekwencji biologicznych

(I)

A

G

C

0

-1

-2

-3

T

-1

-1

A

-2

G

-3

C

-4

(II)

A

G

C

0

-1

-2

-3

T

-1

-1

-2

-3

A

-2

0

-1

-2

G

-3

-1

1

0

C

-4

-2

0

2

(III)

A

G

C

0

-1

-2

-3

T

-1

-1

-2

-3

A

-2

0

-1

-2

G

-3

-1

1

0

C

-4

-2

0

2

Algorytmy Smith- Watermana

𝑲 𝒊, 𝒋 = 𝒎𝒂𝒙

K (i−1, j−1) + S(I, J)

K(i−1, j) + g
K(i, j−1) + g

𝟎

Gdzie:
K (i, j) – punktacja dla komórki (i,j)
S (I,J) – punktacja dla podstawienia w komórce (i, j)
g – kara za przerwy

Elementy bioinformatyki

Porównywanie sekwencji biologicznych

(I)

A

G

C

0

0

0

0

T

0

0

A

0

G

0

C

0

(II)

A

G

C

0

0

0

0

T

0

0

0

0

A

0

1

0

0

G

0

0

2

1

C

0

0

1

3

(III)

A

G

C

0

0

0

0

T

0

0

0

0

A

0

1

0

0

G

0

0

2

1

C

0

0

1

3

2013-04-14

10

Algorytmy przyrównania sekwencji

Metoda oparta na słowach

Metoda heurystyczna nie gwarantująca odnalezienia wszystkich, ani prawdziwych
homologów.

Szybsza (50-100x) od programowania dynamicznego.

Opiera się o wyszukiwanie identycznych lub podobnych fragmentów (słów, krotek) o
długości kilku (aminokwasy) do kilkunastu/kilkudziesięciu (nukleotydy) reszt.

Elementy bioinformatyki

Porównywanie sekwencji biologicznych

Program BLAST i FASTA

BLAST (Basic Local Alignment Search Tool) zaprojektowany został w 1990 roku przez
Stephena Altschula.

1

Jest oparty na algorytmie heurystycznym stanowiącym przybliżenie

algorytmu Smith- Watermana. Pozwala na tworzenie przyrównania lokalnego.

FASTA – opracowana przez D.J. Lipmana i W.R. Pearsona w 1985 roku. Podobnie jak
BLAST oparty na algorytmie Smith- Watermana. Wykorzystuje heurystyczną metodę
opartą na słowach.

[1] Altschul, S.; Gish, W.; Miller, W.; Myers, E.; Lipman, D.; Journal of Molecular Biology; 1990; 215; 403–410.
[2] Lipman, D.J.; Pearson, W.R.; Science; 1985; 227; 1435–41.

Elementy bioinformatyki

Porównywanie sekwencji biologicznych

2013-04-14

11

Algorytm FASTA

Elementy bioinformatyki

Porównywanie sekwencji biologicznych

(A) Wyszukiwanie słów identycznych do tych otrzymanych z zadanej sekwencji.
(B) Powtórna ocena z wykorzystaniem macierzy PAM, dalszej analizie podlegają tylko segmenty o wysokiej
punktacji.
(C) Analiza segmentów sekwencji które umożliwiają utworzenie przyrównania po wprowadzeniu przerw (ocena z
uwzględnieniem kar za przerwy)
(D) Wykorzystanie programowania dynamicznego do optymalizacji nałożenia.

http://www.compbio.dundee.ac.uk/ftp/preprints/review93/Figure9.pdf

Algorytm BLAST

Elementy bioinformatyki

Porównywanie sekwencji biologicznych

(A) Wyszukiwanie słów podobnych do tych otrzymanych z zadanej sekwencji (o punktacji wyższej niż graniczna).
(B) Porównanie otrzymanych słów z bazą i wyszukanie identycznych dopasowań.
(C) Dla każdego znalezionego w bazie słowa przedłuża nałożenie w obu kierunkach do momentu aż ocena
nałożenia jest wyższa niż wartość progowa.

http://cs124.cs.ucdavis.edu/Workshop4/blast/index.html

A

B

C

2013-04-14

12

Rodzaje programu BLAST

Elementy bioinformatyki

Porównywanie sekwencji biologicznych

nucleotide blast

Przeszukiwanie nukleotydowej bazy danych przy użyciu sekwencji nukleotydowej w
zapytaniu.

Algorytmy: blastn, megablast, discontiguous megablast

protein blast

Przeszukiwanie białkowej bazy danych przy użyciu sekwencji białka w zapytaniu.

Algorytmy: blastp, psi-blast, phi-blast, delta-blast

blastx

Przeszukiwanie białkowej bazy danych przy użyciu przetłumaczonej sekwencji
nukleotydowej w zapytaniu.

tblastn

Przeszukiwanie przetłumaczonej nukleotydowej bazy danych przy użyciu sekwencji
białka w zapytaniu.

tblastx

Przeszukiwanie przetłumaczonej nukleotydowej bazy danych przy przetłumaczonej
sekwencji nukleotydowej w zapytaniu.

Dodatkowo wiele specjalistycznych algorytmów programu BLAST jak np. bl2seq pozwalający na porównanie
dwóch sekwencji.

http://blast.ncbi.nlm.nih.gov/Blast.cgi?CMD=Web&PAGE_TYPE=BlastHome

2013-04-14

13

2013-04-14

14

Elementy bioinformatyki

Porównywanie sekwencji biologicznych

Elementy bioinformatyki

Porównywanie sekwencji biologicznych

2013-04-14

15

Interpretacja wyników

Elementy bioinformatyki

Porównywanie sekwencji biologicznych

Raw score (S): miara podobieństwa jako suma punktów za każdą parę reszt. Zależy od wybranego systemu
punktacji i długości sekwencji.

𝑺 =

𝒑𝒂𝒓𝒚 𝒓𝒆𝒔𝒛𝒕

𝒔

𝒊

Bit score (S') znormalizowana miara podobieństwa (niezależna od systemu punktacji).

𝑺′ = (𝝀 × 𝑺 − 𝒍𝒏𝑲)/𝒍𝒏𝟐

Gdzie:
λ, K – parametry statystyczne związane z wykorzystaną macierzą

E-value określa prawdopodobieństwo przypadkowego dopasowania sekwencji dla danego zestawu danych

𝑬 = 𝑲 × 𝒎 × 𝒏 × 𝒆

−𝝀𝑺

Gdzie:
m – liczba reszt w bazie
n – liczba reszt badanej sekwencji

O czym należy pamiętać

Elementy bioinformatyki

Porównywanie sekwencji biologicznych

• Szybkie metody porównywania sekwencji (np. BLAST) oparte są na metodach heurystycznych nie

gwarantujących kompletności ani poprawności wyników wyszukiwania.

• Dla krótkich sekwencji (<40aa) podobieństwo wyższe niż 50% może być przypadkowe.

• Porównywanie sekwencji białkowych pozwala na zwiększenie czułości wyszukiwania, zwłaszcza w przypadku

odległych homologów.

• Aby mówić o homologii białek/domen zwykle wymagane jest podobieństwo na całej długości sekwencji.

• Zasada przechodniości mówi, że jeśli sekwencja A jest homologiczna z B (na całej długości) oraz B jest

homologiem C to A i C też są homologami, nawet jeśli nie wynika to z przyrównania tych sekwencji.

2013-04-14

16

PSI-BLAST (ang. Position-Specific Iterative Basic Local Alignment Search Tool):

algorytm programu BLAST polegający na tworzeniu przyrównania wielu sekwencji na podstawie którego
wyznaczana jest macierz PSSM. Wykorzystanie wygenerowanej macierzy PSSM umożliwia w kolejnych
iteracjach przeszukiwania bazy danych programem PSI-BLAST wyszukiwanie odległych homologii.

PHI-BLAST (ang. Pattern-Hit Initiated Basic Local Alignment Search Tool):

algorytm programu BLAST umożliwiający wykorzystanie zdefiniowanego wcześniej wzorca (wyrażenia
regularnego) opisującego konserwatywny motyw sekwencyjny białka do przeszukiwania bazy danych
Protein.

Elementy bioinformatyki

Porównywanie sekwencji biologicznych

Macierz PSSM (macierz ocen specyficznych względem pozycji; ang. Position-specific
scoring matrix):

macierz wartości prawdopodobieństwa lub częstości występowania reszt określone dla kolejnych pozycji
przyrównania wielu sekwencji. Ważona macież PSSM uwzględnia korektę wartości prawdopodobieństwa
dla reszt nieobserwowanych lub obserwowanych rzadziej.

Wzorzec (wyrażenie regularne; ang. pattern/regular expression):

format zapisu sekwencji aminokwasowej pozwalający przedstawić motyw sekwencji. Określa wzajemne
pozycje reszt konserwatywnych oraz częściowo konserwatywnych

.

Elementy bioinformatyki

Porównywanie sekwencji biologicznych

2013-04-14

17

Elementy bioinformatyki

Porównywanie sekwencji biologicznych

2013-04-14

18

Wyrażenia regularne

Elementy bioinformatyki

Porównywanie sekwencji biologicznych

[FL]-[VL]-[ILM]-D-x-S-[GA]-SM-x

Składnia:
x- dowolna reszta
[FL] – dowolna reszta z wymienionych w nawiasie
{FL} – dowolna reszta za wyjątkiem wymienionych
w nawiasie
(2) – liczba powtórzeń dla podanej wcześniej
reszty/reszt (np. [FL] (2); x (2)

2013-04-14

19

PROSITE

http://prosite.expasy.org/

Elementy bioinformatyki

Porównywanie sekwencji biologicznych

O czym należy pamiętać

Elementy bioinformatyki

Porównywanie sekwencji biologicznych

• Wykorzystując program PSI-BLAST należy wykonać minimum 2 iteracje, lecz nie jest zalecane wykonywanie

więcej niż 5 iteracji.

• Wyniki otrzymane w programie PSI-BLAST należy przeanalizować w celu upewnienia się, że otrzymany profil

na którego podstawie obliczana jest macierz PSSM odzwierciedla funkcjonalny charakter reszt
aminokwasowych w określonych pozycjach znanych sekwencji.

• Wartość E otrzymana dla sekwencji tworzących pierwszy profil w programie PSI-BLAST warunkuje znaczenie

statystyczne uzyskanych wyników.

2013-04-14

20

Porównanie wielu sekwencji

(MSA; ang. Multiple Sequence Alignment)

Elementy bioinformatyki

Porównywanie sekwencji biologicznych

Pozwala określić konserwatywność reszt w sekwencji a
dzięki temu analizę
• Konserwatywności motywów i wzorców w grupie

spokrewnionych sekwencji.

• Funkcjonalnie istotnych reszt aminokwasowych.
• Filogenetyczną
• Drugo- i trzeciorzędowych struktur białek

Dopasowanie wielu sekwencji pozwala na weryfikację
porównania parami.

Algorytmy dopasowania wielu sekwencji

Algorytmy wyczerpujące:

stosowane są do analizy niewielkiej grupy sekwencji (do ok. 10 sekwencji) z wykorzystaniem metody
programowania dynamicznego. Zastosowanie metody do 10 sekwencji wymaga 10-wymiarowej macierzy.
Stosowalność metody do dużych zbiorów ogranicza czas obliczeń, który rośnie wykładniczo wraz liniowym
wzrostem ilości sekwencji w dopasowaniu.

Algorytmy heurystyczne:

szeroko stosowane i tańsze obliczeniowo algorytmy heurystyczne dzielą się na:
• metodę progresywną
• metodę iteracyjną
• metodę blokową

Elementy bioinformatyki

Porównywanie sekwencji biologicznych

2013-04-14

21

1. Przyrównanie globalne wszystkich par sekwencji

przy użyciu algorytmu Needlemana-Wunscha.

2. Oceny dopasowania zamienione zostają na

odległości ewolucyjne.

3. Na podstawie odległości tworzone jest drzewo

ewolucyjne (naprowadzające) metodą łączenia
sąsiadów (ang. Neighbor-joining).

Elementy bioinformatyki

Porównywanie sekwencji biologicznych

Metoda progresywne

4. Dwie najbliżej spokrewnione sekwencje

przyrównuje się ponownie.

5. Przyrównane sekwencje zamieniane są na

sekwencję konsensusową.

6. Do sekwencji konsensusowej przyrównana

zostaje najbliższa sekwencja z drzewa.

7. Kroki 5 i 6 powtarzane są, aż do utworzenia

całego MSA.

Elementy bioinformatyki

Porównywanie sekwencji biologicznych

Metoda progresywne

S

2,4

Uwzględnienie przerw w celu optymalizacji nałożenia

Sekwencja konsensusowa

S

2,4

S

3

2013-04-14

22

Metody iteracyjne

Metoda polega na utworzeniu wstępnego przyrównania o niskiej jakości. Kolejne etapy uwzględniają
wielokrotne iteracyjne przyrównywanie sekwencji, gdzie w każdej iteracji kolejność przyrównanych
sekwencji jest inna. Iteracje powtarzane są do momentu, aż oceny przyrównania nie ulegają poprawie.

Metody blokowe

Porównaniu podlegają krótsze fragmenty sekwencji porównywane parami we wszystkich kombinacjach.
Najwyżej oceniane segmenty służą jako punkt wyjścia do złożenia pełnego przyrównania.
Użyteczne do przyrównywania sekwencji charakteryzujących się tylko lokalnym podobieństwem.

Elementy bioinformatyki

Porównywanie sekwencji biologicznych

Funkcja oceniająca

Elementy bioinformatyki

Porównywanie sekwencji biologicznych

Sekwencja 1

G

K

N

Sekwencja 2

T

R

N

Sekwencja 3

S

H

E

-2 + 1 + 6 = 5

2013-04-14

23

Clustal W

Elementy bioinformatyki

Porównywanie sekwencji biologicznych

Problemy z dopasowywaniem sekwencji

• Regiony o niskiej złożoności mogą generować błędne dopasowanie.

• Mogą istnieć alternatywne dopasowania sekwencji.

• Jedna źle dopasowana lub niehomologiczna sekwencja może popsuć całe nałożenie.

Program Clustal W

• Opiera się na przyrównaniu globalnym dlatego nie nadaje się do przyrównywania sekwencji o równej

długości.

• Nie sprawdza się w przypadku długich przerw w przyrównaniu.
• Błędne przyrównanie sekwencji parami skutkuje utrwaleniem tego błędu w końcowym przyrównaniu.

Elementy bioinformatyki

Porównywanie sekwencji biologicznych

2013-04-14

24

Zasady wykonania dobrego dopasowania sekwencji.

1. Wybór zestawu sekwencji (regionów) do porównania.

2. Wybór kolejności porównania (na podstawie podobieństwa parami).

3. Dobór parametrów porównania (kary za przerwy, macierz).

4. Ocena MSA (przerwy, sekwencje psujące nałożenie, nałożenie reszt konserwatywnych).

5. Korekta zestawu sekwencji do nałożenia i ponowne MSA.

6. Ręczna korekta nałożenia (jeśli wymagana).

7. Analiza końcowego nałożenia (nałożenie reszt konserwatywnych, domen).

Elementy bioinformatyki

Porównywanie sekwencji biologicznych