algorytm Fasta i BLAST.PDF

(114 KB) Pobierz
‘‘Wstep do obliczeniowej biologii molekularnej’’
(J. Tiuryn, wyk´
lad nr.6, 23 listopada 2005)
Spis tre´ci
s
3 Przeszukiwanie baz danych
3.1 Heurystyczne algorytmy . . . . . . . . . .
3.1.1 FASTA . . . . . . . . . . . . . . . .
3.1.2 BLAST . . . . . . . . . . . . . . .
3.1.3 Statystyka por´wnywania sekwencji
o
3.1.4 PSI-BLAST . . . . . . . . . . . . .
3.1.5 Uliniowienie sekwencji z profilem .
3.2 Macierze substytucyjne . . . . . . . . . . .
3.2.1 PAM . . . . . . . . . . . . . . . . .
3.2.2 BLOSUM . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
36
36
36
38
39
41
42
44
44
46
3
Przeszukiwanie baz danych
Jest du˙ o baz dnaych specjalizujacych sie w r´znych aspektach zwiazanych
z
o˙
z sekwencjami naturalnie pojawiajacymi sie w biologii. Dla sekwencji DNA
gl´wne bazy danych to: GenBank (USA), EMBL (Europa), DDBJ (Japonia).
o
Natomiast dla bialek gl´wna baza danych jest Swiss-Prot. Przeszukiwanie
o
baz danych jest jedna z gl´wnych metod pracy wsp´lczesnego biologa. Poni˙ ej
o
o
z
om´wimy kilka zagadnie´ zwiazanych z praktycznymi aspektami przeszuki-
o
n
wania baz.
3.1
Heurystyczne algorytmy
Om´wimy dwa najbardziej popularne heurystyczne algorytmy u˙ ywane do
o
z
obliczania przybli˙ onej warto´ci lokalnego uliniowienia. Algorytmy te stanowi a
z
s
standardowe narzedzie do przeszukiwania baz danych w procesie wyszukiwa-
nia podobie´ stw pomiedzy sekwencjami.
n
3.1.1
FASTA
Jest to heurystyczny algorytm (Lipman, Pearson, 1985) slu˙ acy do przy-
z
bli˙ onego obliczania lokalnego uliniowienia danego wzorca
Q
wzgledem tek-
z
stowej sekwencji
T
wzietej z bazy danych. Zwykle stosuje sie go do kole-
jnych sekwencji z bazy danych. Na poczatku u˙ ytkownik wybiera liczbowy
z
parametr, zwany
ktup.
Standardowo sugerowane warto´ci dla
ktup
to 6 dla
s
36
sekwencji DNA oraz 2 dla bialek. Przyjmijmy, ze
k
jest warto´cia parametru
˙
s
ktup.
Przez
k-slowo
bedziemy rozumie´ dowolne slowo dlugo´ci
k.
Niech
n
=
c
s
|Q|
oraz
m
=
|T |.
Dzialanie algorytmu mo˙ na przedstawi´ w nastepujacych
z
c
czterech krokach.
1. Dla 1
≤
i
≤
n,
1
≤
j
≤
m
algorytm znajduje pary (i,
j),
takie ze
k-
˙
slowo zaczynajace sie w
Q
w pozycji
i
jest identyczne z
k-slowem
zaczy-
najacym sie w
T
w pozycji
j.
Ka˙ da taka para (i,
j)
nazywa sie
goracym
z
miejscem.
Operacje te mo˙ na wykona´ efektywnie sporzadzajac na
z
c
poczatku tablice haszujaca dla
Q,
lub (rzadziej) dla wszystkich sl´w
T
o
z bazy danych.
2. Ka˙ de gorace miejsce (i,
j)
mo˙ na traktowa´ jako odcinek dlugo´ci
z
z
c
s
k
le˙ acy na przekatnej o numerze
1
(i
−
j)
w tablicy
V
(otrzymanej
z
metoda dynamicznego programowania —
V
oczywi´cie nie mamy). Al-
s
gorytm przypisuje pewne warto´ci dodatnie goracym miejscom oraz
s
warto´ci ujemne przerwom pomiedzy takimi miejscami (im dlu˙ sza
s
z
przerwa, tym mniejsza warto´´). Dla ka˙ dej przekatnej zawierajacej
sc
z
gorace miejsce, algorytm wybiera fragment pomiedzy goracymi miejs-
cami o maksymalnej warto´ci. W ten spos´b zostaje wybranych 10
s
o
przekatnych (i zawartych w nich fragment´w) o maksymalnej warto´ci.
o
s
Dla ka˙ dego z tych fragment´w algorytm znajduje cze´´ takiego frag-
z
o
sc
mentu (podslowo) o maksymalnej warto´ci uliniowienia bez spacji (do
s
obliczania tej warto´ci stosuje sie tablice PAM lub BLOSUM) Taka
s
cze´´ fragmentu nazwiemy
poduliniowieniem.
Niech
init1
bedzie na-
sc
jlepszym poduliniowieniem.
3. Wybrane sa poduliniowienia, kt´rych warto´´ przekracza pewna z g´ry
o
sc
o
ustalona granice. Z tych dobrych poduliniowie´ pr´buje sie ulo˙ y´ ulin-
n o
z c
iowienie o maksymalnej warto´ci. W tym celu buduje sie nastepujacy
s
graf poduliniowie´ . Wierzcholkami sa poduliniowienia. Ka˙ demu wierz-
n
z
cholkowi jest przypisana liczba bedaca warto´cia tego poduliniowienia.
s
Je´li
u
i
v
sa poduliniowieniami, takimi ze
u
zaczyna sie w pozycji (i,
j)
s
˙
i ko´ czy w pozycji (i +
d, j
+
d),
a
v
zaczyna sie w pozycji (i
, j
), to
n
tworzymy krawed´ od
u
do
v,
gdy
i > i
+
d
oraz
j > j
+
d,
tzn gdy
z
wiersz (kolumna) w kt´rym zaczyna sie
v
jest poni˙ ej wiersza (na prawo
o
z
od kolumny), w kt´rym ko´ czy sie
u.
Krawedzi tej przypisujemy pewna
o
n
wage zale˙ aca od liczby spacji jakie trzeba wprowadzi´ we fragmencie
z
c
lokalnego uliniowienia, w kt´rym poduliniowienie
v
wystepuje po po-
o
duliniowieniu
u.
Im wieksza liczba spacji tym waga takiej krawedzi jest
Gl´wna przekatna ma numer 0, przekatne o numerach dodatnich le˙ a nad gl´wna
o
z
o
przekatna, a o numerach ujemnych pod gl´wna przekatna.
o
1
37
mniejsza. Nastepnie algorytm znajduje droge o maksymalnej warto´ci
s
w wy˙ ej opisanym grafie. Taka droga wyznacza lokalne uliniowienie
z
pomiedzy dwoma slowami. To nie musi by´ optymalne lokalne ulin-
c
iowienie pomiedzy
Q
oraz
T
. Oznaczmy to uliniowienie przez
initn.
4. Algorytm wraca do poduliniowienia
init1
z kroku 2 i znajduje najlepsze
lokalne uliniowienie wok´l przekatnej zawierajacej
init1
w pasie [−8, 8]
o
(dla bialek) oraz w pasie [−16, 16] (dla DNA). Niech
opt
bedzie takim
uliniowieniem.
W ten sps´b
Q
jest por´wnywane z kolejnymi slowami
T
z bazy danych.
o
o
Biorac pod uwage
opt
lub
initn
wyznacza sie mala liczbe sl´w
T
, najbardziej
o
obiecujacych z punktu widzenia uliniowienia z
Q.
Dla ka˙ dego z nich wykonuje
z
sie pelny algorytm Smitha-Watermana obliczajacy optymalne uliniowienia.
3.1.2
BLAST
Algorytm BLAST (Altschul
et.al.
1990) podaje jako wynik cale spektrum
rozwiaza´ (uliniowie´ ) wraz z oszacowaniem statystycznej istotno´ci znalezionego
n
n
s
rozwiazania (czyli prawdopodobie´ stwa tego, ze znaleziona warto´´, lub warto´´
n
˙
sc
sc
od niej wieksza mogla sie pojawi´ przypadkiem (z losowej sekwencji)).
c
BLAST por´wnuje wzorzec
Q
z ka˙ da sekwencja z bazy danych, starajac
o
z
sie zidentyfikowa´ te sekwencje
T
, dla kt´rych MSP (maximal
segment pair,
c
o
czyli para podsl´w r´wnej dlugo´ci maksymalizujaca warto´´ uliniowienia bez
o o
s
sc
spacji
2
) jest wieksze od pewnej z g´ry ustalonej warto´ci
C.
W ten spos´b
o
s
o
wybiera sie pewne slowa
T
“podejrzane” o pewne podobie´ stwo z
Q.
n
Jak sie szuka takich
T
, dla kt´rych MSP jest wieksze od
C?
Ustala
o
sie dlugo´´
w
oraz warto´´ graniczna
t.
Nastepnie BLAST znajduje wszys-
sc
sc
tkie
w-podslowa
w
T
, dla kt´rych istnieje
w-podslowo
w
Q
o warto´ci ulin-
o
s
iowienia (bez spacji) wiekszej od
t.
Ka˙ de takie miejsce jest rozszerzane w
z
celu znalezienia warto´ci uliniowienia wiekszej od
C.
Je´li w trakcie rozsz-
s
s
erzania warto´´ uliniowienia (kt´ra mo˙ e rosna´ lub male´ z ka˙ dym krokiem
sc
o
z
c
c
z
rozszerzenia) spadnie poni˙ ej pewnej warto´ci progowej, to poszukiwania dla
z
s
takiego miejsca sa przerywane.
Dob´r warto´ci
C, w
oraz
t
ma kluczowe znaczenie dla jako´ci znaj-
o
s
s
dowanych wynik´w. Na przyklad, dla por´wnywania bialek
w
jest przyj-
o
o
mowane pomiedzy 3 a 5, natomiast dla DNA jest zwykle r´wne okolo 12.
o
2
Przy u˙ yciu pewnej macierzy substytucyjnej.
z
38
3.1.3
Statystyka por´wnywania sekwencji
o
Poni˙ ej przedstawimy podstawowe wyniki teorii (Karlin, Altschul’1990), na
z
kt´rej BLAST opiera analize statystycznej istotno´ci znalezionego wyniku
o
s
uliniowienia. Teoria ta nie dotyczy uliniowie´ ze spacjami. Opracowanie
n
analogicznej teorii dla uliniowie´ ze spacjami stanowi problem otwarty.
n
Analiza jednej sekwencji
Na poczatek zajmiemy sie analiza probabilistyczna jednej sekwencji. Dany
jest alfabet
A
=
{a
1
, . . . , a
r
},
z kt´rego losowany jest ciag liter o praw-
o
dopodobie´ stwach
{p
1
, . . . , p
r
}.
Z ka˙ dym wystapieniem litery
a
i
w sekwencji
n
z
zwiazana jest warto´´
s
i
bedaca liczba rzeczywista. Przyjmujemy nastepujace
sc
zalo˙ enia:
z
1. Dla pewnego
i
mamy
s
i
>
0.
2. Warto´´ oczekiwana warto´ci dla calego alfabetu jest ujemna:
sc
s
0.
r
i=1
p
i
s
i
<
Rozwa˙ amy zmienna losowa
M
(n) przyjmujaca warto´´ maksymalna dla
z
sc
segmentu w losoowej sekwencji dlugo´ci
n.
s
Twierdzenie 3.1.1
Warto´´ oczekiwana dla
M
(n)
jest rzedu
sc
jest jedynym dodatnim rozwiazaniem r´wnania
o
r
ln
n
,
λ
∗
gdzie
λ
∗
p
i
·
e
λ·s
i
= 1.
i=1
Twierdzenie 3.1.2
Prob
M
(n)
−
ln
n
>x
λ
∗
≈
1
−
e
−K·e
−λ∗
x
,
gdzie
K
jest stala zadana szybko zbie˙ nym szeregiem.
z
n
˜
Zatem wycentrowna zmienna losowa
M
=
m(n)
−
ln
∗
ma rozklad EVD
λ
(extreme value distribution), zwany te˙ rozkladem Gumbela.
z
Ponadto oczekiwana liczba wystapie´ segment´w w losowej sekwencji dlugo´ci
n
o
s
ln
n
−λ
∗
x
n,
o warto´ci wiekszej ni˙
λ
∗
+
x
wynosi
K
·
e
s
z
.
Powy˙ sze twierdzenie wynika z nastepujacej og´lniejszej uwagi: liczba
z
o
wystapie´ ‘oddzielnych’ segment´w o wysokiej warto´ci (tzn. o warto´ci
n
o
s
s
ln
n
wiekszej ni˙
λ
∗
+x) jest aproksymowane przez rozklad Poissona o parametrze
z
∗
a
=
K
·
e
−λ
x
.
39
Przypomnijmy, ze rozklad Poissona o parmetrze
a
dla zmiennej losowej
˙
x
przyjmujacej warto´ci naturalne wyglada nastepujaco
s
a
k
−a
·
e .
Prob
(X =
k)
=
k!
Zatem prawdopodobie´ stwo napotkania
m
lub wiecej r´znych segment´w
n
o˙
o
m−1 a
i
o du˙ ej warto´ci wynosi 1
−
e
−a
·
i=1 i!
. Przyjmujac
m
= 1 dostajemy
z
s
pierwsza cze´´ twierdzenia. Druga cze´´ wynika natychmiast z faktu, ze
sc
sc
˙
warto´´ oczekiwana dla zmiennej losowej o rozkladzie Poissona z parametrem
sc
a
wynosi
E(X)
=
a.
n
s
s
Niech
S
=
ln
∗
+x bedzie warto´cia segmentu w losowej sekwencji dlugo´ci
λ
n.
W´wczas, zgodnie z Twierdzeniem 3.1.2, oczekiwana liczba wystapie´
o
n
∗
x
segment´w rozlacznych o warto´ci co najmniej
S
wynosi
K
·
e
−λ
=
K
·
o
s
∗
S
∗
S
e
ln
n−λ
=
K
·n·e
−λ
. To jest wla´nie tzw. E-value obliczane przez program
s
BLAST.
∗
E
=
K
·
n
·
e
λ S
.
Statystyka por´wnywania dw´ch sekwencji
o
o
Mamy dwie sekwencje: jedna losowana z rozkladem na literach
{p
1
, . . . , p
r
},
a druga z rozkladem
{p
1
, . . . , p
r
}.
Ponadto mamy tablice substytucyjna
(s
i,j
)
1≤i,j≤r
. Przyjmujemy nastepujace zalo˙ enia:
z
1.
i,j
p
i
p
j
s
i,j
<
0, oraz
2. Dla pewnych
i, j,
mamy
s
i,j
>
0.
o˙
3. Rozklady
{p
1
, . . . , p
r
}
oraz
{p
1
, . . . , p
r
}
nie r´znia sie zbytnio od siebie.
3
Dalej analiza wyglada podobnie do przypadku jednej sekwencji o dlugo´ci
s
m·n,
gdzie
m
i
n
sa dlugo´ciami losowych sekwencji. W szczeg´lno´ci niech
λ
∗
s
o s
λs
i,j
= 1. Niech
bedzie jedynym dodatnim rozwiazaniem r´wnania
i,j
p
i
p
j
e
o
M
(m,
n)
bedzie zmienna losowa wyra˙ ajaca maksymalna warto´´ lokalnego
z
sc
uliniowienia (bez spacji) losowych sl´w o dlugo´ciach
m
oraz
n
generowanych
o
s
z powy˙ szych rozklad´w. W´wczas mamy nastepujace twierdzenie
z
o
o
ln
mn
+
x
Prob
M
(m,
n) >
λ
∗
≈
1
−
e
−K·e
−λ
∗
x
.
Jest to tzw. warto´´
p-value,
czyli prawdopodobi´ stwo tego, ze mo˙ na ulin-
sc
n
˙
z
iowi´ pare losowych sekwencji o dlugo´ciach
m
oraz
n
tak, ze natrafimy na
c
s
˙
Techniczna definicje tego zalo˙ enia pomijamy tutaj, odsylajac zainteresowanego
z
czytelnika do publikacji.
3
40

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin