Bioinformatyka
Wykład IV
Marcin Gołębiewski Ph.D.
Zakład Biotechnologii
Wydział Biologii i Nauk o Ziemi
Uniwersytet Mikołaja Kopernika
15 marca 2010
Marcin Gołębiewski Ph.D. Bioinformatyka Wykład IV
Wstęp
Przeszukiwanie dużej bazy sekwencji z użyciem algorytmu
Smith-Watermana, czy Needlemana-Wunscha trwa długo,
dlatego stosuje się inne algorytmy, które pozwalają proces
przyspieszyć, ale kosztem absolutnej poprawności wyników.
Programem, który jest najczęściej używany do przeszukiwania
jest BLAST.
Przeszukiwanie przy użyciu pojedynczej sekwencji nie jest
najczujszą możliwą metodą.
Do przeszukiwania można wykorzystać informacje płynące z
dopasowania wielu sekwencji - możliwość znalezienie
odległych homologów jest wtedy znacząco większa.
Z kilku możliwości najczęściej stosowanym i najszybszym
programem jest PSI-BLAST (Position Specific Iterated
BLAST).
Marcin Gołębiewski Ph.D. Bioinformatyka Wykład IV
Czułość i specyficzność
Czułość przeszukiwania to prawdopodobieństwo
niepominięcia istotnego dopasowania. Im czułość wyższa,
tym większą mamy pewność, że nalez
liśmy wszystkie
faktyczne homologi znajdujące się w bazie sekwencji.
Specyficzność to prawdopodobieństwo błędnego uznania
dopasowania za istotne. Im wyższa specyficzność, tym rzadziej
w wynikach znajdą się bzdury (czyli przypadkowe alignmenty).
Na ogół im wyższa czułość i niższa specyficzność danej
metody, tym wolniej ona działa.
Marcin Gołębiewski Ph.D. Bioinformatyka Wykład IV
Zasada działania programu BLAST I
BLAST działa szybciej, niż algorytmy oparte na
programowaniu dynamicznym (SW, NW) ponieważ nie
konstruuje alignmentów sekwencji kwerendowej z wszystkimi
sekwencjami z bazy.
Sekwencje, które praktycznie na pewno nie dadzą istotnego
dopasowania są odrzucany po szybkim, pobieżnym
sprawdzeniu, jaka jest szansa, że ich dopasowanie z sekwencją
kwerendową będzie sensowne.
Sprawdzenie to opiera się na założeniu, że istotnie podobne
sekwencje zawierają krótkie, bardzo podobne fragmenty, tzw.
słowa w niezbyt dużej odległości od siebie.
Słowa muszą spełniać trzy warunki:
1
score dopasownia musi być większy od ustalonego progu,
2
nie mogą się nakładać,
3
odległość między nimi musi być mniejsza niż ustalony próg.
Marcin Gołębiewski Ph.D. Bioinformatyka Wykład IV
Zasada działania programu BLAST II
BLAST zawdzięcza swoją szybkość temu, że sprawdza
obecność słów z sekwencji kwerendowej w specjalnie
przygotowanej tablicy, zawierającej informację o tym jakie
słowa występują w kolejnych sekwencjach z bazy i jaka jest
ich pozycja (tzw. lookup table).
Dla wybranych sekwencji konstruowany jest przy pomocy
programowania dynamicznego alignment i oceniana jego
istotność.
W związku z tym, że BLAST używa lookup table, baza musi
zostać odpowiednio przygotowana, służy do tego program
formatdb (BLAST) bądz
makeblastdb (BLAST+).
Marcin Gołębiewski Ph.D. Bioinformatyka Wykład IV
Działanie BLASTa - przykład
Sekwencja kwerendowa:
ATATTGGCAACCGTTAGCCATGCGAATTAGAGGA
Sekwencja z bazy: ATTTTGGCAACGGTTCGCCATGGGGTT-
TAGACCAGGCGAACTAGACTT
Sprawdzamy, czy w sekwencji z bazy występują
czteronukleotydowe słowa z sekwencji kwerendowej: ATAT,
TATT, ATTG, TTGG, TGGC, GGCA, GCAA. . .
Na przykład:
ATTTTGGCAACGGTTCGCCATGGGGTTTAGACCAGGCG-
AACTAGACTT
TTGG GCCA
Jeżeli przyjmiemy, że score dopasowań i
TTGG GCCA
przekracza ustalony próg i słowa mogą znajdować się w
odległości większej niż 8 nt, to będziemy konstruować
alignment tych dwóch sekwencji.
Marcin Gołębiewski Ph.D. Bioinformatyka Wykład IV
PSI-BLAST - przeszukiwanie przy pomocy profili
PSI-BLAST to algorytm wykorzystujący BLAST do
iteracyjnego (powtarzanego) przeszukiwania bazy białkowej
sekwencją białkową przy użyciu informacji płynących z
dopasowania wielu sekwencji.
W metodzie tej obecność konkretnego aminokwasu w danej
pozycji sekwencji z bazy jest  nagradzana score zależnym od
składu kolumny alignmentu do której ten aminokwas jest
dopasowywany, a nie tylko od macierzy wagowej - mówimy, że
score jest pozycyjnie specyficzny.
Dzięki temu, mamy możliwość wykrywania dalekich
homologów, których podobieństwo liczone  tradycyjną
metodą (w/g macierzy wagowej) byłoby zbyt niskie, żeby
uznać dopasowania za istotne.
Marcin Gołębiewski Ph.D. Bioinformatyka Wykład IV
PSI-BLAST - zasada działania
W pierwszym kroku PSI-BLAST identyfikuje homologi obecne
w bazie przy pomocy zwykłego BLASTa.
Następnie z sekwencji, które dały dopasowania o istotnośći
wyższej (e-value niższym) od założonego progu konstruowane
jest dopasowanie wielu sekwencji.
Na podstawie tego dopasowania i macierzy wagowej tworzony
jest profil - tablica rozmiaru l � 20, w której określone są
scores dla każdego z możliwych 20 aminokwasów w danej
pozycji.
Profil ten służy następnie do przeszukiwania bazy, a homologi
zidentyfikowane w ten sposób są do niego włączane, jeżeli
istotność ich dopasowań była wystarczająco wysoka.
Dwa powyższe punkty powtarzane są ustaloną liczbę razy,
albo do momentu, kiedy przestają się pojawiać sekwencje
dające odpowiednio istotne dopasowania.
Marcin Gołębiewski Ph.D. Bioinformatyka Wykład IV
PSI-BLAST - parametr  inclusion threshold
Najważniejszym z parametrów umożliwiających kontrolę nad
przeszukiwaniem jest w przypadku PSI-BLASTa tzw. próg
włączenia (inclusion threshold).
Jest to maksymalna wartość e-value, jaką może mieć
dopasowanie danej sekwencji, aby była ona włączona do
profilu.
Użycie zbyt wysokiej wartości powoduje, że do profilu
włączane są  śmieci - sekwencje, które nie są homologami
sekwencji kwerendowej.
Z kolei zbyt niska wartość wykluczy z profilu sekwencje, które
powinny się w nim znalez
ć, czyli faktyczne odległe homologi.
Właściwą wartość trzeba za każdym razem dobrać
eksperymentalnie.
Dobrym punktem startowym jest wartość 0.005.
Marcin Gołębiewski Ph.D. Bioinformatyka Wykład IV
Marcin Gołębiewski Ph.D. Bioinformatyka Wykład IV