Bioinformatyka
Wykład V
Marcin Gołębiewski Ph.D.
Zakład Biotechnologii
Wydział Biologii i Nauk o Ziemi
Uniwersytet Mikołaja Kopernika
21 marca 2010
Marcin Gołębiewski Ph.D. Bioinformatyka Wykład V
Wstęp
Konstrukcja alignmentów wielu sekwencji jest jednym z
ważnych zadań bioinformatyki.
Alignmentów wielu sekwencji używa się w analizie
filogenetycznej, przy przeszukiwaniu baz danych za pomocą
profili i modeli Markova, do identyfikacji funkcjonalnych
domen w sekwencjach, przy obliczaniu struktur białek itp.
Marcin Gołębiewski Ph.D. Bioinformatyka Wykład V
Co to jest multiple alignment?
Rozszerzenie pojęcia alignmentu dwóch sekwencji na większą ich
liczbę nazywamy multiple alignment.
motif I motif II
TraI_RP4_ YITDEQGKT.ERLGHVRVTNCE.ANTLPAV..........MA...EVMATQHGNTRSEADKTYHL 71
TraI_R751_ YITDAQSKD.HRLGHVQATNCE.AGSIQDA..........IT...EVLATQHTNTRAKGDKTYHL 71
NikB_R64_ YATRLRNESFVALVDVMKDGCEWVNFYGVTCFHNCTSLETAAADMEYIARQAHYAKDDTDPVFHY 92
MobA_pTF-F14_ YIREPQNRNPNEKV.LYANG...RGFISDT..H.......AAQREEMVALAAE.AVRSRNPVNHY 74
Rlx_pC221_ YA.EKRAEE..KSG.L...NC..D..VDYA..........KS...AFKQTRALYGKEDGIQA.HT 57
Rlx_pS194_ YA.EERAEE..KSG.L...NC..D..VDYA..........KS...YFKQTRALYGKENGVQA.HT 57
Rlx_pC223_ YA.EKRAEE..KSA.L...NC..D..IDYA..........KS...SFKATREMYGKTDGNEG.HV 57
VirD2_pTiC58_ YLSRKGRLELQRSARHLDIPLPPDQIHELARS.......WVQETGTYDESQPDEERQQELTT.HI 85
VirD2_pRiA4B_ YLSRKGKLELQRSARHLDIPLPPDQIHELARS.......WVQETGTYDESQPDEERQQELTT.HI 85
VirD2_pTiOct_ YLSRKGKLELQRSARHLDIPVPPDQIRELAQS.......WVTEAGIYDESQSDDDRQQDLTT.HI 85
. . . . .
30 40 50 60 70
motif II motif III
TraI_RP4_ LV.SFRAG.EKPDA.ETLR.AIEDRICAGLGFAEHQRVSAVHHDTDNLHIHIAINKIHPTRNTIH 132
TraI_R751_ IV.SFRAG.EQPSA.DTLR.AIEERICVGLGYGEHQRISAVHNDTDNLHIHIAINKIHPTRHTMH 132
NikB_R64_ IL.SWQSH.ESPRP.EQIYDSVRHTLKS.LGLADHQYVSAVHTDTDNLHVHVAVNRVHPETGYLN 153
MobA_pTF-F14_ IL.SWREG.EQPSP.EQVEEAVSIFLDE.LGLQEHQVIYALHKDTDNLHLHIAVNRVHPET..LK 133
Rlx_pC221_ VIQSFKPG.EVT.P.EQCN.QLGLELAE.KIAPNHQVAVYTHTDKDHYHNHIVINSVDLETGKKY 117
Rlx_pS194_ VIQSFKPG.EVT.A.KECN.EIGLELAK.KIAPDYQVAVYTHTDKDHYHNHIIINSVNLETGNKY 117
Rlx_pC223_ VIQSFKPN.EVT.P.EQCN.QLGLELAE.KIAPNHQVAVYTHNDTDHVHNHIVINSIDLETGKKF 117
VirD2_pTiC58_ IV.SFPAGTSQVAAYAASREWAAEMFGSGAGGGRYNYLTAFHIDRDHPHLHVVVNR......... 140
VirD2_pRiA4B_ IV.SFPAGTSQAAAYAASREWAAEMFGSGAGGGSYNYLTAFHIDRDHPHLHVVVNR......... 140
VirD2_pTiOct_ IV.SFPAGTDQTAAYEASREWAAEMFGSGYGGGRYNYLTAYHVDRDHPHLHVVVNR......... 140
. . . . . .
80 90 100 110 120 130
Marcin Gołębiewski Ph.D. Bioinformatyka Wykład V
Co to jest multiple alignment?
W idealnym przypadku aminokwasy, bądz
zasady w każdej
kolumnie alignment u mają wspólne pochodzenie ewolucyjne i
zajmują podobne miejsca w strukturach swoich cząsteczek.
Z zasady zawsze istnieje  dobry alignment  ewolucyjny dla
dowolnego zestawu sekwencji (nawet, jeżeli ich struktury nie
dają się nałożyć) - jednak stwierdzenie który, z bardzo wielu
możliwych alignmentów, jest właściwy może nie być możliwe.
Alignment w sensie strukturalnym możemy zweryfikować,
jeżeli tylko dysponujemy strukturami wszystkich cząsteczek w
nim uczestniczących, w przypadku alignmentu ewolucyjnego
nie ma takiej możliwości.
Marcin Gołębiewski Ph.D. Bioinformatyka Wykład V
Po co konstruować alignment y wielu sekwencji?
Podstawowymi pytaniami w analizie sekwencji białkowych są:
1
Czy dana sekwencja należy do określonej rodziny białek?
2
Jeżeli tak, to jakie zakonserwowane elementy w niej
występują?
3
Jaka jest przypuszczalna funkcja danego białka?
Aby odpowiedzieć na powyższe pytania konieczne jest
porównanie badanej sekwencji z zestawieniem sekwencji
rodziny, o przynależność do której podejrzewamy nasze białko,
a następnie określenie, jakie regiony są w takim zestawieniu
zakonserwowane.
Marcin Gołębiewski Ph.D. Bioinformatyka Wykład V
Po co konstruować alignment y wielu sekwencji?
Drugim niezmiernie istotnym zastosowaniem alignmentów jest
analiza filogenetyczna. Drzewa filogenetyczne konstruuje się
na podstawie alignmentów.
Trzecim zastosowaniem jest identyfikacja nieznanych do tej
pory członków rodzin białkowych w bazach danych. Znów
punktem wyjścia jest alignment danej rodziny, który
konwertuje się do profilu, bądz
ukrytego modelu Markova
(Hidden Markov Model - HMM).
Marcin Gołębiewski Ph.D. Bioinformatyka Wykład V
Scoring alignment u wielu sekwencji
System oceny alignment u wielu sekwencji powinien brać pod
uwagę dwa fakty:
1
pewne pozycje są silniej zakonserwowane, niż inne (score
powinien być  pozycyjnie specyficzny )
2
sekwencje tworzące alignment nie ewoluowały niezależnie,
związki między nimi określa drzewo filogenetyczne
Idealnym score dla alignment u wielu sekwencji byłoby
prawdopodobieństwo takiego alignmentu przy założeniu
prawidłowego drzewa filogenetycznego i modelu ewolucji.
W takim przypadku prawdopodobieństwo alignment u jest
iloczynem prawdopodobieństw wszystkich zdarzeń
ewolucyjnych potrzebnych do jego wygenerowania poprzez
sekwencje pośrednie i apriorycznego prawdopodobieństwa
sekwencji wspólnego przodka ( korzenia - root).
Marcin Gołębiewski Ph.D. Bioinformatyka Wykład V
Scoring alignment u wielu sekwencji
Na ogół nie znamy  prawidłowego drzewa , a model ewolucji
musiałby być tak skomplikowany, że jego stosowanie jest w
praktyce niemożliwe - stosujemy więc przybliżenia zakładające:
niezależność kolumn alignment u
niezależną ewolucję poszczególnych sekwencji
Marcin Gołębiewski Ph.D. Bioinformatyka Wykład V
Score typu  suma par
Najczęściej stosuje się scoring typu  suma par (sum of pairs -
SP), gdzie score alignment u jest równy sumie score ów
poszczególnych kolumn, a score kolumny jest sumą score ów
wszystkich par symboli w danej kolumnie:

k l
S(m) = G + (S(mi)), S(mi) = (mi , mi )
i kS(m) - score alignmentu, G - funkcja ważąca przerwy, S(mi) -
score i-tej kolumny.
Niestety ten typ score ma wady, co dobrze ilustruje
następujący przykład:
Przypuśćmy, że mamy kompletnie zakonserwowaną kolumnę
składającą się z N leucyn (L). Score SP takiej kolumny w/g
N(N-1)
BLOSUM62 (s(L, L) = 5) będzie wynosił 5 � . Jeżeli w
2
takiej kolumnie znajdzie się jedna glicyna (G) i N - 1 leucyn
(s(L, G) = -4), score takiej kolumny wyniesie
5 - (-4) � (N - 1) mniej, a co więcej, różnica będzie rosła
wraz z ilością leucyn w kolumnie!
Marcin Gołębiewski Ph.D. Bioinformatyka Wykład V
Metoda progresywna
Ze względu na zbyt dużą złożoność obliczeniową algorytmu
konstruującego optymalny alignment, konieczne jest
stosowanie algorytmów heurystycznych, szybszych, lecz nie
gwarantujących optymalności rozwiązania.
Najczęściej stosowaną heurystyką jest progresywna metoda
konstrukcji alignment ów.
Polega ona na sukcesywnej konstrukcji alignmentu na
podstawie alignmentu dwóch sekwencji.
Marcin Gołębiewski Ph.D. Bioinformatyka Wykład V
Metoda progresywna
Algorytm  alignment progresywny :
N(N-1)
1
utwórz alignmentów sekwencji (każda z każdą)
2
2
na podstawie score ów otrzymanych alignmentów oblicz
odległości między sekwencjami
3
na podstawie odległości oblicz drzewo przewodnie (np.
metodą neighbor joining)
4
utwórz alignment najbliżej spokrewnionych sekwencji, od
tego momentu jest on niezmienny
5
do istniejącego alignmentu dołącz kolejną, najbliższą
sekwencję
6
powtarzaj powyższy krok, dopóki są sekwencje do dołożenia
W niektórych metodach konstruuje się najpierw alignmenty z
najbardziej zbliżonych par, a następnie z utworzonych alignmentów
robi się alignment czterech sekwencji itd. Metoda ta nazywa się
alignment profili.
Marcin Gołębiewski Ph.D. Bioinformatyka Wykład V
Metody konstrukcji multiple alignments - algorytm
progresywny programu ClustalW
W programie ClustalW i jego odpowiedniku z interfacem
graficznym (ClustalX) zastosowano metodę progresywnej
konstrukcji alignmentu z użyciem profili i score w postaci SP.
Zaimplementowano także dodatkowe heurystyki poprawiające
wynik:
sekwencje są ważone w celu skompensowania nadreprezentacji
dużym podrodzin zbliżonych do siebie białek
macierz wagowa jest wybierana na podstawie wstępnego
oszacowania podobieństwa, sekwencje blisko spokrewnione
porównywane są przy pomocy macierzy  twardych np.
BLOSUM80, a odległe od siebie przy pomocy  miękkich np.
BLOSUM32
Marcin Gołębiewski Ph.D. Bioinformatyka Wykład V
Metody konstrukcji multiple alignments - algorytm
progresywny programu ClustalW
kary za przerwy są pozycyjnie specyficzne (różnią się w
poszczególnych kolumnach), zależą od stopnia
zakonserwowania kolumny i rodzaju aminokwasów jakie się w
niej pojawiają; kary są wyższe w kolumnach gdzie są
aminokwasy hydrofobowe
kara za otwarcie przerwy jest zmniejszana, jeżeli w kolumna
należy do ciągu min. pięciu aminokwasów hydrofilowych
obie kary za przerwy są zwiększane, jeżeli w kolumnie nie ma
przerw, ale są one w sąsiednich kolumnach
drzewo przewodnie może być dostosowywane  w locie ,
alignmenty o niskim score są przesuwane na póz
niejszy etap,
kiedy ilość informacji będzie większa
Marcin Gołębiewski Ph.D. Bioinformatyka Wykład V
Metody iteracyjne
Ponieważ w metodzie progresywnej  podalignmenty są z
założenia niezmienne, nie mogą być dopasowywane nawet kiedy
informacje uzyskane w póz
niejszych stadiach wskazywałyby na
sensowność takiej zmiany.
Algorytmy  iteracyjnego ulepszania (iterative refinement - IR) są
jednym z prostych sposobów na obejście tego problemu.
Schemat IR jest następujący:
1
skonstruuj alignment przy pomocy metody progresywnej
2
usuń pierwszą sekwencję, dopasuj ją do powstałego profilu
3
powtarzaj 2 dla wszystkich sekwencji
4
powtarzaj 2 i 3 ustaloną liczbę razy, lub do momentu, aż score
przestanie się zmieniać
Marcin Gołębiewski Ph.D. Bioinformatyka Wykład V
Ograniczenia metod konstrukcji alignmentów
Należy pamiętać, że poza przypadkami trywialnymi (zestaw
bardzo podobnych do siebie sekwencji), na ogół nie jesteśmy
w stanie poprawnie dopasować do siebie całości wszystkich
sekwencji.
Dlatego lepiej jest skupić się na ograniczonym zestawie
kolumn, które nie budzą wątpliwości. Na ogół będą to
sekwencje hydrofobowego rdzenia białek i np. zakonserwowane
reszty uczestniczące w katalizie, czy tworzeniu kieszeni
wiążącej substrat.
Konstruując alignmenty strukturalne stwierdzono, że w
przypadku wyraz
nie homologicznych białek (ok. 30%
identyczności) jedynie połowa aminokwasów w strukturach
dawała się nałożyć. Nie możemy więc oczekiwać, że
konstruując alignment nie biorący pod uwagę informacji
strukturalnych uzyskamy więcej.
Marcin Gołębiewski Ph.D. Bioinformatyka Wykład V
Marcin Gołębiewski Ph.D. Bioinformatyka Wykład V