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 naleź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ądź 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:
ATT

TTGG

CAACGGTTC

GCCA

TGGGGTTTAGACCAGGCG-

AACTAGACTT

Jeżeli przyjmiemy, że score dopasowań

TTGG
TTGG

i

GCCA
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 znaleźć, 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