bioinformatyka w6 2008 web

background image

Bioinformatyka, wykład 6

(18.XI.2008)

krzysztof_pawlowski@sggw.pl

Dopasowanie sekwencji

Dopasowanie sekwencji

c.d.

c.d.

Sequence

Sequence

alignment

alignment

background image

Programowanie dynamiczne

Programowanie dynamiczne

Porównuje każdą

parę

znaków dwóch sekwencji i tworzy dopasowanie

Uwzględnia wszystkie możliwe przyrównania uwzględniając:

dopasowania (matches),

niedopasowania (mismatches),

przerwy (gaps).

Przerwy są

wstawiane, aby uzyskać

wzrost liczby dopasowań

w innych miejscach.

Przyjmuje pewien system punktacji (scoring system)

Rozpatruje wszystkie możliwości

Stara się

uzyskać

maksymalną

liczbę

dopasowań

między identycznymi lub

podobnymi znakami

Znajduje optymalne dopasowanie (może istnieć

więcej niż

jedno

takie dopasowanie)

Czas obliczeń

proporcjonalny do iloczynu długości sekwencji

background image

Programowanie dynamiczne

Programowanie dynamiczne

Przyjęty system punktacji:

dopasowanie (match): +1

niedopasowanie (mismatch): -1

przerwa (gap): -1

AGA--TTGATACCCA

AGACATTAA---CTA

match

mismatch

gap

background image

Programowanie dynamiczne

Programowanie dynamiczne

Programowanie dynamiczne uwzględnia każdą

dodawaną

parę

znaków

i z powrotem przelicza optymalne dopasowanie.

C

A

sekwencja 1:

G A T A C T A

sekwencja 2:

G A T T A C C A

T
|
T

A

T

+

=

Dotychczasowe dopasowanie musi być

optymalne!

A
|
A

G
|
G

T
|
T

A

T

A
|
A

G
|
G

C

A

+1 +1 +1 –1 –1 = +1

G A T - A C
| | | |
G A T T A -

+1 +1 +1 –1 +1 –1 = +2

- - G A T A C

G A T T A - -

–1 –1 –1 –1 –1 –1 –1 = –7

+1 +1 +1 –1 = +2

Już

utworzone dopasowanie, do którego jest dodawana kolejna para znaków,

musi być

optymalne.

- G A T A C

| |

G A T T A -

–1 –1 –1 +1 +1 –1 = –2

background image

Tworzenie macierzy punktacji, w której każda komórka reprezentuje punktację

dla

najlepszego dopasowania kończącego się

w danej pozycji

Programowanie dynamiczne

Programowanie dynamiczne

Cofanie się

w macierzy, aby znaleźć

optymalne dopasowanie

sekwencja 1:

G A T A C T A

sekwencja 2

:

G A T T A C C A

Przyjęty system punktacji:

dopasowanie (match): +1

niedopasowanie (mismatch): -1

przerwa (gap): -1

background image

G A T A C T A

G
A
T
T
A
C
C
A

Znaki sekwencji
ułożone wzdłuż

dwu-wymiarowej
siatki

Węzły siatki
znajdują

się

między znakami

Programowanie dynamiczne

Programowanie dynamiczne

dopasowanie jako

dopasowanie jako

ś

ś

cie

cie

ż

ż

ka w macierzy

ka w macierzy

background image

G A T A C T A

G
A
T
T
A
C
C
A

Celem jest
znalezienie
optymalnej ścieżki

stąd

dotąd

Programowanie dynamiczne

Programowanie dynamiczne

dopasowanie jako

dopasowanie jako

ś

ś

cie

cie

ż

ż

ka w macierzy

ka w macierzy

background image

G A T A C T A

G
A
T
T
A
C
C
A

Każda ścieżka
odpowiada
pewnemu
dopasowaniu

Które
dopasowanie
jest optymalne?

Programowanie dynamiczne

Programowanie dynamiczne

dopasowanie jako

dopasowanie jako

ś

ś

cie

cie

ż

ż

ka w macierzy

ka w macierzy

background image

G A T A C T A

G
A
T
T
A
C
C
A

punktacja dla
ścieżki jest sumą

przyrastających
punktacji
krawędzi.

A

porównane z

A

match

= +1

Programowanie dynamiczne

Programowanie dynamiczne

dopasowanie jako

dopasowanie jako

ś

ś

cie

cie

ż

ż

ka w macierzy

ka w macierzy

background image

G A T A C T A

G
A
T
T
A
C
C
A

A

porównane z

T

mismatch

= -1

punktacja dla
ścieżki jest sumą

przyrastających
punktacji
krawędzi.

Programowanie dynamiczne

Programowanie dynamiczne

dopasowanie jako

dopasowanie jako

ś

ś

cie

cie

ż

ż

ka w macierzy

ka w macierzy

background image

G A T A C T A

G
A
T
T
A
C
C
A

T

porównane z przerwą

gap

= -1

przerwa porównana z

T

punktacja dla
ścieżki jest sumą

przyrastających
punktacji
krawędzi.

Programowanie dynamiczne

Programowanie dynamiczne

dopasowanie jako

dopasowanie jako

ś

ś

cie

cie

ż

ż

ka w macierzy

ka w macierzy

background image

G A T A C T A

G
A
T
T
A
C
C
A

Programowanie dynamiczne

Programowanie dynamiczne

dopasowanie jako

dopasowanie jako

ś

ś

cie

cie

ż

ż

ka w macierzy

ka w macierzy

Znaczenie punktu w
macierzy:

wszystkie znaki do
tego miejsca są

ze

sobą

porównane,

czego można dokonać

na wiele sposobów
(ścieżek).

Pozycja

x

oznacza:

przyrównanie

GA

z

GA

x

--GA

GA--

-GA

G-A

GA

GA

background image

G A T A C T A

G
A
T
T
A
C
C
A

Rozszerzanie się

ścieżki i
przyrastanie
punktacji.

0

-1

+1

-1

Programowanie dynamiczne

Programowanie dynamiczne

dopasowanie jako

dopasowanie jako

ś

ś

cie

cie

ż

ż

ka w macierzy

ka w macierzy

background image

G

G

A

T

A

T

-1

0 -1= -1

-1

0 -1
= -1

+1

0 +

1= +

1

0

background image

G

G

A

T

A

T

-2

-1 -1= -2

-2

-1

-1=

-2

-1

+1

-1

0 -1= -1

0 -1
= -1

0 +

1= +

1

-1 -1
= -2

-2

0

background image

-2

-1

-1=

-2

G

G

A

T

A

T

-2

-1 -1= -2

0

+2

+1 +

1= +

2

+1-1
= 0

0

0

+1 -1= 0

-1

+1

-1

0 -1= -1

0 -1
= -1

0 +

1= +

1

background image

-2

G

G

A

T

A

T

-2

-1 -1= -2

0

+1 -1= 0

-1

+1

0 -1= -1

0 -1
= -1

0 +

1= +

1

0

+2

+1 +

1= +

2

+1-1
= 0

0

-2

-1 -1= 0

-1

-2

-1 -

1= -2

-1-1
= -2

-2

background image

G A T A C T A

G
A
T
T
A
C
C
A

Rozszerzanie się

ścieżki i
przyrastanie
punktacji.

0

-1

+1

-1

Programowanie dynamiczne

Programowanie dynamiczne

dopasowanie jako

dopasowanie jako

ś

ś

cie

cie

ż

ż

ka w macierzy

ka w macierzy

background image

G A T A C T A

G
A
T
T
A
C
C
A

0

+1

-1

-2

-2

-1

Wybierana jest
najlepsza ścieżka
prowadząca do
każdego punktu
na siatce.

Rozszerzanie się

ścieżki i
przyrastanie
punktacji.

Programowanie dynamiczne

Programowanie dynamiczne

dopasowanie jako

dopasowanie jako

ś

ś

cie

cie

ż

ż

ka w macierzy

ka w macierzy

background image

G A T A C T A

G
A
T
T
A
C
C
A

0

-1

-2

0

+2

+1

-1

-2

0

Wybierana jest
najlepsza ścieżka
prowadząca do
każdego punktu
na siatce.

Rozszerzanie się

ścieżki i
przyrastanie
punktacji.

Programowanie dynamiczne

Programowanie dynamiczne

dopasowanie jako

dopasowanie jako

ś

ś

cie

cie

ż

ż

ka w macierzy

ka w macierzy

background image

G A T A C T A

G
A
T
T
A
C
C
A

0

-2

0

+2

+1

-1

-2

0

-2

-1

Wybierana jest
najlepsza ścieżka
prowadząca do
każdego punktu
na siatce.

Rozszerzanie się

ścieżki i
przyrastanie
punktacji.

Programowanie dynamiczne

Programowanie dynamiczne

dopasowanie jako

dopasowanie jako

ś

ś

cie

cie

ż

ż

ka w macierzy

ka w macierzy

background image

G A T A C T A

G
A
T
T
A
C
C
A

0

+1

-1

-2

-1

-3

-2

-3

-2

+3

-1

-1

0

0

+1

+1

+2

Wybierana jest
najlepsza ścieżka
prowadząca do
każdego punktu
na siatce.

Rozszerzanie się

ścieżki i
przyrastanie
punktacji.

Programowanie dynamiczne

Programowanie dynamiczne

dopasowanie jako

dopasowanie jako

ś

ś

cie

cie

ż

ż

ka w macierzy

ka w macierzy

background image

G A T A C T A

G
A
T
T
A
C
C
A

0

+1

-1

-1

-2

-2

0

0

+1

+2

-5

-4

-5

-4

-3

-3

-1

-3

-2

-1

0

+1

+2

0

+1

-1

+2

-3

-1

-2

+1

+3

+2

+1

+2

+3

Wybierana jest
najlepsza ścieżka
prowadząca do
każdego punktu
na siatce.

Rozszerzanie się

ścieżki i
przyrastanie
punktacji.

Programowanie dynamiczne

Programowanie dynamiczne

dopasowanie jako

dopasowanie jako

ś

ś

cie

cie

ż

ż

ka w macierzy

ka w macierzy

background image

G

G A T A C T A

A
T
T
A
C
C
A

0

+1

-1

-1

-2

-2

0

0

+1

+2

-4

-4

-3

-3

-1

-2

0

+2

0

+1

-1

+2

-2

+2

+1

+2

+3

-8

-7

-6

-5

-7

-6

-5

-5

-3

-2

-3

-4

-1

-1

0

+1

+1

+1

+3

+2

-4

-6

-3

-2

-3

-1

-4

-5

+1

+3

+1

0

+2

+4

+4

+3

+2

+2

+3

-2

0

-1

+2

+2

+3

Wybierana jest
najlepsza ścieżka
prowadząca do
każdego punktu
na siatce.

Rozszerzanie się

ścieżki i
przyrastanie
punktacji.

Programowanie dynamiczne

Programowanie dynamiczne

dopasowanie jako

dopasowanie jako

ś

ś

cie

cie

ż

ż

ka w macierzy

ka w macierzy

background image

G A T A C T A

G
A
T
T
A
C
C
A

Cofanie się

do

tyłu i wybór
optymalnej
ścieżki i
dopasowania.

0

+1

-1

-1

-2

-2

0

0

+1

+2

-4

-4

-3

-3

-1

-2

0

+2

0

+1

-1

+2

-2

+2

+1

+2

+3

-8

-7

-6

-5

-7

-6

-5

-5

-3

-2

-3

-4

-1

-1

0

+1

+1

+1

+3

+2

-4

-6

-3

-2

-3

-1

-4

-5

+1

+3

+1

0

+2

+4

+4

+3

+2

+2

+3

-2

0

-1

+2

+2

+3

Programowanie dynamiczne

Programowanie dynamiczne

dopasowanie jako

dopasowanie jako

ś

ś

cie

cie

ż

ż

ka w macierzy

ka w macierzy

background image

G A T A C T A

G
A
T
T
A
C
C
A

Uzyskane
dopasowanie

A
A

-
T

T
T

A
A

C
C

T
C

A
A

G
G

Programowanie dynamiczne

Programowanie dynamiczne

dopasowanie jako

dopasowanie jako

ś

ś

cie

cie

ż

ż

ka w macierzy

ka w macierzy

background image

Optimalne

dopasowanie

globalne

Optymal ne

dopasowanie

lolalne

dopasowanie globalne i lokalne

dopasowanie globalne i lokalne

dopasowanie globalne

(Needleman & Wunsch, 1970)

przyrównuje sekwencje na

całej długości; wykorzystuje tak dużo znaków, jak to jest tylko możliwe.

dopasowanie lokalne

(

Smith & Waterman

, 1981)

przyrównuje fragmenty sekwencji,

które wykazują

największe podobieństwo; poszukuje najlepiej pasujących regionów;

znajduje regiony konserwowane. Gdy obliczana wartość

punktacji w macierzy jest

mniejsza od zera, to wartość

ta jest ustawiana na zero, a dopasowanie ulega

zakończeniu do tego miejsca i rozpoczynany jest nowe` dopasowanie od nowego
miejsca

LGPSSKQTGKGS-SRIWDN

| | ||| | |

LN-ITKSAGKGAIMRLGDA

-------TGKG--------

|||

-------AGKG--------

sekwencje o podobnej

długości, blisko

spokrewnione

sekwencje o różnych

długościach, posiadające

regiony

i domeny zachowane,

podobne tylko

w niektórych obszarach

background image

System punktacji

System punktacji

Zaawansowany system punktacji (nadawanie różnych wag dla
niedopasowań

i przerw w zależnosci

od ich długości):

Macierze podstawień

aminokwasów (PAM, BLOSUM)

Macierze podstawień

nukleotydów

System punktacji dla przerw: gap penalties, affine gap penalty

Prosty system punktacji:

match

: +1

+1

mismatch

: -1

0

gap

: -1

-1

background image

Typowe systemy punktacji

Typowe systemy punktacji

z

sekwencje DNA

Match = +1

Mismatch = -3

Gap penalty = -5

Gap extension penalty = -2

z

sekwencje białkowe

Macierz Blossum62

Gap open penalty = -11

Gap extension = -1

background image

Istotno

Istotno

ść

ść

dopasowania

dopasowania

Czy punktacja dopasowanie jest znacząco większa od punktacji

oczekiwanej dla dopasowania losowych sekwencji o tej samej

długości i składzie?

3 > Z

brak homologii

3 < Z < 6

istnieje homologia

Z > 6

silna homologia

Tworzenie metodą

Monte Carlo

losowych(-ej) sekwencji (o tej samej

długości i składzie co rzeczywiste).

Przyrównanie losowych(-ej) sekwencji (powtórzenie 100-1000 razy) przy
tych samych parametrach.

Określenie rozkładu punktacji, średniej i odchylenie standardowego (SD).

Wyliczenie Z-score: Z = (score

obs

score

ran

)/SD

ran

Rozkład „score-ów”

nie jest normalny i dlatego nie można przekształcić

Z-score

na prawdopodobieństwo.

background image

Istotno

Istotno

ść

ść

dopasowania

dopasowania

Wykres zależności logarytmu ułamka dopasowań

z punktacją

S równą

lub większą

od wartości punktacji S’

Określenie E-value

Oczekiwana liczba przypadkowych dopasowań

z punktacją

większą

niż

obserwowana

Dla dopasowań

lokalnych rozkład maksymalnych „scorów”

dopasowania

dla sekwencji losowych przyjmuje rozkład wartości ekstremalnych
(extreme

values

distribution)(Karlin

i Altschul

1990).

S’

Log
p(S>=S’)

S

e

Kmn

E

λ

=

Oczekiwana (wg rozkładu prawdopodobieństwa)
liczba dopasowań

z punktacją

równą

przynajmniej S

background image

'

2

S

mn

E

=

2

ln

ln

'

K

S

S

=

λ

!

a

E

e

a

E

Bit score-

znormalizowana punktacja uwzględniająca

warunki jego naliczania i przyjęte systemy punktacji

(parametry lambda i K)

Prawdopodobieństwo
znalezienia dokładnie a

dopasowań

o punktacji >= S:

Prawdopodobieństwo
znalezienia przynajmniej 1

dopasowania o punktacji >=S

E

e

p

= 1

Jeżeli spodziewamy się

znaleźć

przynajmniej 3

dopasowania o punktacji >= S, to

prawdopodobieństwo tego że znajdziemy co
najmniej jedno wynosi 0,95. Programy z grupy
BLAST posługują

się

wartością

E zamiast

bezpośrednim prawdopodobieństwem ze względu
na łatwiejsze rozróżnienie

background image

dopasowanie wielu sekwencji (MSA)

dopasowanie wielu sekwencji (MSA)

przyrównanie (porównanie) wielu (co najmniej trzech) sekwencji

HBB_HUMAN --------VHLTPEEKSAVTALWGKVN--VDEVGGEALGRLLVVYPWTQRFFESFGDLST

HBB_HORSE --------VQLSGEEKAAVLALWDKVN--EEEVGGEALGRLLVVYPWTQRFFDSFGDLSN

HBA_HUMAN ---------VLSPADKTNVKAAWGKVGAHAGEYGAEALERMFLSFPTTKTYFPHF-DLS-

HBA_HORSE ---------VLSAADKTNVKAAWSKVGGHAGEYGAEALERMFLGFPTTKTYFPHF-DLS-

GLB5_PETMA PIVDTGSVAPLSAAEKTKIRSAWAPVYSTYETSGVDILVKFFTSTPAAQEFFPKFKGLTT

MYG_PHYCA ---------VLSEGEWQLVLHVWAKVEADVAGHGQDILIRLFKSHPETLEKFDRFKHLKT

LGB2_LUPLU --------GALTESQAALVKSSWEEFNANIPKHTHRFFILVLEIAPAAKDLFSFLKGTSE

*: : : * . : .: * :

* : .

HBB_HUMAN PDAVMGNPKVKAHGKKVLGAFSDGLAHLDN-----LKGTFATLSELHCDKLHVDPENFRL

HBB_HORSE PGAVMGNPKVKAHGKKVLHSFGEGVHHLDN-----LKGTFAALSELHCDKLHVDPENFRL

HBA_HUMAN ----HGSAQVKGHGKKVADALTNAVAHVDD-----MPNALSALSDLHAHKLRVDPVNFKL

HBA_HORSE ----HGSAQVKAHGKKVGDALTLAVGHLDD-----LPGALSNLSDLHAHKLRVDPVNFKL

GLB5_PETMA ADQLKKSADVRWHAERIINAVNDAVASMDDT--EKMSMKLRDLSGKHAKSFQVDPQYFKV

MYG_PHYCA EAEMKASEDLKKHGVTVLTALGAILKKKGH-----HEAELKPLAQSHATKHKIPIKYLEF

LGB2_LUPLU VP--QNNPELQAHAGKVFKLVYEAAIQLQVTGVVVTDATLKNLGSVHVSKG-VADAHFPV

. .:: *. : . : *. * . : : .

HBB_HUMAN LGNVLVCVLAHHFGKEFTPPVQAAYQKVVAGVANALAHKYH------

HBB_HORSE LGNVLVVVLARHFGKDFTPELQASYQKVVAGVANALAHKYH------

HBA_HUMAN LSHCLLVTLAAHLPAEFTPAVHASLDKFLASVSTVLTSKYR------

HBA_HORSE LSHCLLSTLAVHLPNDFTPAVHASLDKFLSSVSTVLTSKYR------

GLB5_PETMA LAAVIADTVAAG---------DAGFEKLMSMICILLRSAY-------

MYG_PHYCA ISEAIIHVLHSRHPGDFGADAQGAMNKALELFRKDIAAKYKELGYQG

LGB2_LUPLU VKEAILKTIKEVVGAKWSEELNSAWTIAYDELAIVIKKEMNDAA---

: : .: ... . :

background image

Dopasowania wielu sekwencji

Dopasowania wielu sekwencji

-

-

zastosowanie

zastosowanie

Określanie powiązań

filogenetycznych między sekwencjami

Poszukiwanie odległych homologów

Poszukiwanie wspólnych, konserwowanych wzorów, motywów
i domen w sekwencjach, odpowiedzialnych za odpowiednie
funkcje biochemiczne lub strukturę

przestrzenną.

Grupowanie białek w rodziny o wspólnej funkcji biochemicznej
lub historii ewolucyjnej. Identyfikowanie członków rodzin białek.

Identyfikowanie zachodzących fragmentów sekwencji powstałych
w wyniku losowego sekwencjonowania genomów i ułatwienie ich
składania w jedną

całą

sekwencję.

Najbardziej wiarygodny dla sekwencji o podobnej długości
i posiadających zachowanie regiony.

background image

Dopasowania wielu sekwencji a analizy filogenetyczne

Dopasowania wielu sekwencji a analizy filogenetyczne

sekw1

N

F

L

AWSQ

G

A

sekw2

N

F

I

AWSQ

G

A

sekw3

N

F

I

AWTQ

-

A

sekw4

N

-

I

AWSQ

G

A

N

-

I

AWSQ

G

A

N

F

L

AWSQ

G

A

N

F

I

AWSQ

G

A

N

F

I

AWTQ

-

A

+

F

I

->

L

-

G

background image

Dopasowania wielu sekwencji

Dopasowania wielu sekwencji

-

-

metody

metody

Programowanie dynamiczne (PD) -

zbyt skomplikowane dla wielu

sekwencji; stosowany dla niewielu krótkich sekwencji
program MSA

(dopasowanie globalne)

Progresywne dopasowanie globalne (hierarchiczne)
programy: CLUSTALW, CLUSTALX

Metody iteracyjne
programy: MultAlin, PRRP, DIALIGN,

SAGA (algorytm genetyczny)

Metody aproksymacyjne:

background image

Dopasowanie wielu sekwencji i PD

Dopasowanie wielu sekwencji i PD

-

-

z

z

ł

ł

o

o

ż

ż

ono

ono

ść

ść

problemu

problemu

Optymalne dopasowanie dwóch sekwencji przy pomocy
programowania dynamicznego -

macierz punktacji

w kwadracie, wymagany czas: L

2

; L -

długość

sekwencji

Optymalne dopasowanie trzech sekwencji przy pomocy
programowania dynamicznego -

macierz punktacji w

sześcianie; wymagany czas: L

3

Optymalne dopasowanie N sekwencji przy pomocy
programowania dynamicznego -

macierz punktacji w N

wymiarach: wymagany czas: L

N

- rośnie wykładniczo ze

wzrostem liczby sekwencji (N)

background image

Dopasowanie wielu sekwencji

Dopasowanie wielu sekwencji

-

-

trzy sekwencje

trzy sekwencje

V

S

N

S

S

N

A

A

S

V S N - S

- S N A

- - - A S

start

Szukanie optymalnego dopasowania w objętości sześcianu.

background image

Dopasowanie wielu sekwencji i PD

Dopasowanie wielu sekwencji i PD

program MSA

program MSA

Liczenie w objętości (w przestrzeni N-wymiarowej) punktacji dla
wielokrotnego dopasowania.

Optymalne dopasowanie to takie, który posiada najlepszy SP score.

Punktacja dla wielokrotnego dopasowania jest sumą

punktacji

uzyskanych dla porównania wszystkich par sekwencji w wielokrotnym
alignment-cie

(miara SP –

sum of

pairs).

background image

Progresywne

Progresywne

dopasowanie

dopasowanie

globalne

globalne

-

-

program CLUSTALW

program CLUSTALW

>HBB_HUMAN

VHLTPEEKSAVTALWGKVNVDEVGGEALGRLLVVYPWTQRFFESFGDLSTPDAVMGNPKVKAHGKKVLGAFSDGLAHLDNLKGTFA

TLSELHCDKLHVDPENFRLLGNVLVCVLAHHFGKEFTPPVQAAYQKVVAGVANALAHKYH*

>HBB_HORSE

VQLSGEEKAAVLALWDKVNEEEVGGEALGRLLVVYPWTQRFFDSFGDLSNPGAVMGNPKVKAHGKKVLHSFGEGVHHLDNLKGTFA

ALSELHCDKLHVDPENFRLLGNVLVVVLARHFGKDFTPELQASYQKVVAGVANALAHKYH*

>HBA_HUMAN

VLSPADKTNVKAAWGKVGAHAGEYGAEALERMFLSFPTTKTYFPHFDLSHGSAQVKGHGKKVADALTNAVAHVDDMPNALSALSDL

HAHKLRVDPVNFKLLSHCLLVTLAAHLPAEFTPAVHASLDKFLASVSTVLTSKYR*

>HBA_HORSE

VLSAADKTNVKAAWSKVGGHAGEYGAEALERMFLGFPTTKTYFPHFDLSHGSAQVKAHGKKVGDALTLAVGHLDDLPGALSNLSDL

HAHKLRVDPVNFKLLSHCLLSTLAVHLPNDFTPAVHASLDKFLSSVSTVLTSKYR*

>MYG_PHYCA

VLSEGEWQLVLHVWAKVEADVAGHGQDILIRLFKSHPETLEKFDRFKHLKTEAEMKASEDLKKHGVTVLTALGAILKKKGHHEAEL

KPLAQSHATKHKIPIKYLEFISEAIIHVLHSRHPGDFGADAQGAMNKALELFRKDIAAKYKELGYQG*

>GLB5_PETMA

PIVDTGSVAPLSAAEKTKIRSAWAPVYSTYETSGVDILVKFFTSTPAAQEFFPKFKGLTTADQLKKSADVRWHAERIINAVNDAVA

SMDDTEKMSMKLRDLSGKHAKSFQVDPQYFKVLAAVIADTVAAGDAGFEKLMSMICILLRSAY*

>LGB2_LUPLU

GALTESQAALVKSSWEEFNANIPKHTHRFFILVLEIAPAAKDLFSFLKGTSEVPQNNPELQAHAGKVFKLVYEAAIQLQVTGVVVT

DATLKNLGSVHVSKGVADAHFPVVKEAILKTIKEVVGAKWSEELNSAWTIAYDELAIVIKKEMNDAA*

Sekwencje globin

background image

Porównujemy zestaw 7 sekwencji :HAHU, HBHU,HAHO, HBHO, MYWHP,

PILHB i LGHB

Dopasowujemy osobno każdą

możliwą

parę

sekwencji i obliczamy

według pewnego algorytmu wzajemne podobieństwo sekwencji w
obrębie każdej z 21 par

Wynik przedstawiamy w macierzy podobieństw

DOPASOWANIA WIELOKROTNE

DOPASOWANIA WIELOKROTNE

(MULTIALIGNMENT)

(MULTIALIGNMENT)

Metoda hierarchiczna

Metoda hierarchiczna

HAHU

HBHU

HAHO

HBHO

MYWHP

PILHB

HBHU

21.1

HAHO

32.9

19.7

HBHO

20.7

39.0

20.4

MYWHP

11.0

9.8

10.3

9.7

PILHB

9.3

8.6

9.6

8.4

7.0

LGHB

7.1

7.3

7.5

7.4

7.3

4.3

background image

Tworzenie drzewa przewodniego

Tworzenie drzewa przewodniego

LGHB

LGHB

PILHB

PILHB

MYWHB

MYWHB

HAHU

HAHU

HAHO

HAHO

HBHU

HBHO

background image

Stopniowe zestawianie sekwencji

Stopniowe zestawianie sekwencji

dopasowanych

dopasowanych

HBHO

HBHU

Programowanie
dynamiczne

dopasowanie

HBHO

HBHU

HAHU

HAHO

Programowanie
dynamiczne

dopasowanie

HAHU

HAHO

background image

HBHO

HBHU

HAHU

HAHO

Programowanie
dynamiczne

HBHO

HBHU

HAHU

HAHO

Nowa
przerwa

dopasowanie czterech sekwencji

-

Dodawanie kolejnych sekwencji, coraz

bardziej odległych według drzewa
przewodniego

background image

Sekwencyjne przyrównywanie sekwencji, ze względu na podobieństwo opisane na
drzewie: przyrównanie najpierw sekwencji najbardziej podobnych, a następnie
dołączanie do już

utworzonego dopasowania pozostałych najbardziej podobnych

sekwencji wg przewodniego drzewa filogenetycznego. Sekwencje po dopasowaniu są

traktowane jako całość.

HBB_HUMAN VHLTPEEKSAVTALWGKVNVDEVGGEALGRLLVVYPWTQRFFESFGDLSTPDAVMGNPKVKAHGKKVLGAFSDGLAHLDNLK

HBB_HORSE VQLSGEEKAAVLALWDKVNEEEVGGEALGRLLVVYPWTQRFFDSFGDLSNPGAVMGNPKVKAHGKKVLHSFGEGVHHLDNLK

HBB_HUMAN GTFATLSELHCDKLHVDPENFRLLGNVLVCVLAHHFGKEFTPPVQAAYQKVVAGVANALAHKYH

HBB_HORSE GTFAALSELHCDKLHVDPENFRLLGNVLVVVLARHFGKDFTPELQASYQKVVAGVANALAHKYH

HBA_HUMAN VLSPADKTNVKAAWGKVGAHAGEYGAEALERMFLSFPTTKTYFPHFDLSHGSAQVKGHGKKVADALTNAVAHVDDMPNALSA

HBA_HORSE VLSAADKTNVKAAWSKVGGHAGEYGAEALERMFLGFPTTKTYFPHFDLSHGSAQVKAHGKKVGDALTLAVGHLDDLPGALSN

HBA_HUMAN LSDLHAHKLRVDPVNFKLLSHCLLVTLAAHLPAEFTPAVHASLDKFLASVSTVLTSKYR

HBA_HORSE LSDLHAHKLRVDPVNFKLLSHCLLSTLAVHLPNDFTPAVHASLDKFLSSVSTVLTSKYR

+

HBB_HUMAN VHLTPEEKSAVTALWGKVN--VDEVGGEALGRLLVVYPWTQRFFESFGDLSTPDAVMGNPKVKAHGKKVLGAFSDGLAHLDNLK

HBB_HORSE VQLSGEEKAAVLALWDKVN--EEEVGGEALGRLLVVYPWTQRFFDSFGDLSNPGAVMGNPKVKAHGKKVLHSFGEGVHHLDNLK

HBA_HUMAN -VLSPADKTNVKAAWGKVGAHAGEYGAEALERMFLSFPTTKTYFPHF-DLS-----HGSAQVKGHGKKVADALTNAVAHVDDMP

HBA_HORSE -VLSAADKTNVKAAWSKVGGHAGEYGAEALERMFLGFPTTKTYFPHF-DLS-----HGSAQVKAHGKKVGDALTLAVGHLDDLP

HBB_HUMAN GTFATLSELHCDKLHVDPENFRLLGNVLVCVLAHHFGKEFTPPVQAAYQKVVAGVANALAHKYH

HBB_HORSE GTFAALSELHCDKLHVDPENFRLLGNVLVVVLARHFGKDFTPELQASYQKVVAGVANALAHKYH

HBA_HUMAN NALSALSDLHAHKLRVDPVNFKLLSHCLLVTLAAHLPAEFTPAVHASLDKFLASVSTVLTSKYR

HBA_HORSE GALSNLSDLHAHKLRVDPVNFKLLSHCLLSTLAVHLPNDFTPAVHASLDKFLSSVSTVLTSKYR

background image

HBB_HUMAN --------VHLTPEEKSAVTALWGKVN--VDEVGGEALGRLLVVYPWTQRFFESFGDLSTPDAVMGNPKVKAHGKKVLGAFSD

HBB_HORSE --------VQLSGEEKAAVLALWDKVN--EEEVGGEALGRLLVVYPWTQRFFDSFGDLSNPGAVMGNPKVKAHGKKVLHSFGE

HBA_HUMAN ---------VLSPADKTNVKAAWGKVGAHAGEYGAEALERMFLSFPTTKTYFPHF-DLS-----HGSAQVKGHGKKVADALTN

HBA_HORSE ---------VLSAADKTNVKAAWSKVGGHAGEYGAEALERMFLGFPTTKTYFPHF-DLS-----HGSAQVKAHGKKVGDALTL

GLB5_PETMA PIVDTGSVAPLSAAEKTKIRSAWAPVYSTYETSGVDILVKFFTSTPAAQEFFPKFKGLTTADQLKKSADVRWHAERIINAVND

HBB_HUMAN GLAHLDN---LKGTFATLSELHCDKLHVDPENFRLLGNVLVCVLAHHFGKEFTPPVQAAYQKVVAGVANALAHKYH

HBB_HORSE GVHHLDN---LKGTFAALSELHCDKLHVDPENFRLLGNVLVVVLARHFGKDFTPELQASYQKVVAGVANALAHKYH

HBA_HUMAN AVAHVDD---MPNALSALSDLHAHKLRVDPVNFKLLSHCLLVTLAAHLPAEFTPAVHASLDKFLASVSTVLTSKYR

HBA_HORSE AVGHLDD---LPGALSNLSDLHAHKLRVDPVNFKLLSHCLLSTLAVHLPNDFTPAVHASLDKFLSSVSTVLTSKYR

GLB5_PETMA AVASMDDTEKMSMKLRDLSGKHAKSFQVDPQYFKVLAAVIADTVAAG---------DAGFEKLMSMICILLRSAY-

HBB_HUMAN VHLTPEEKSAVTALWGKVN--VDEVGGEALGRLLVVYPWTQRFFESFGDLSTPDAVMGNPKVKAHGKKVLGAFSDGLAHLDNLK

HBB_HORSE VQLSGEEKAAVLALWDKVN--EEEVGGEALGRLLVVYPWTQRFFDSFGDLSNPGAVMGNPKVKAHGKKVLHSFGEGVHHLDNLK

HBA_HUMAN -VLSPADKTNVKAAWGKVGAHAGEYGAEALERMFLSFPTTKTYFPHF-DLS-----HGSAQVKGHGKKVADALTNAVAHVDDMP

HBA_HORSE -VLSAADKTNVKAAWSKVGGHAGEYGAEALERMFLGFPTTKTYFPHF-DLS-----HGSAQVKAHGKKVGDALTLAVGHLDDLP

HBB_HUMAN GTFATLSELHCDKLHVDPENFRLLGNVLVCVLAHHFGKEFTPPVQAAYQKVVAGVANALAHKYH

HBB_HORSE GTFAALSELHCDKLHVDPENFRLLGNVLVVVLARHFGKDFTPELQASYQKVVAGVANALAHKYH

HBA_HUMAN NALSALSDLHAHKLRVDPVNFKLLSHCLLVTLAAHLPAEFTPAVHASLDKFLASVSTVLTSKYR

HBA_HORSE GALSNLSDLHAHKLRVDPVNFKLLSHCLLSTLAVHLPNDFTPAVHASLDKFLSSVSTVLTSKYR

GLB5_PETMA PIVDTGSVAPLSAAEKTKIRSAWAPVYSTYETSGVDILVKFFTSTPAAQEFFPKFKGLTTADQLKKSADVRWHAERIINAVND

GLB5_PETMA AVASMDDTEKMSMKLRDLSGKHAKSFQVDPQYFKVLAAVIADTVAAGDAGFEKLMSMICILLRSAY

+

background image

Progresywne

Progresywne

dopasowanie

dopasowanie

globalne

globalne

-

-

program CLUSTALW

program CLUSTALW

HBB_HUMAN --------VH

L

TPEEKSAVTAL

W

GKVN--VDEVGGEALGRLLVVY

P

WTQRF

F

ESFGDLST

HBB_HORSE --------VQ

L

SGEEKAAVLAL

W

DKVN--EEEVGGEALGRLLVVY

P

WTQRF

F

DSFGDLSN

HBA_HUMAN ---------V

L

SPADKTNVKAA

W

GKVGAHAGEYGAEALERMFLSF

P

TTKTY

F

PHF-DLS-

HBA_HORSE ---------V

L

SAADKTNVKAA

W

SKVGGHAGEYGAEALERMFLGF

P

TTKTY

F

PHF-DLS-

GLB5_PETMA PIVDTGSVAP

L

SAAEKTKIRSA

W

APVYSTYETSGVDILVKFFTST

P

AAQEF

F

PKFKGLTT

MYG_PHYCA ---------V

L

SEGEWQLVLHV

W

AKVEADVAGHGQDILIRLFKSH

P

ETLEK

F

DRFKHLKT

LGB2_LUPLU --------GA

L

TESQAALVKSS

W

EEFNANIPKHTHRFFILVLEIA

P

AAKDL

F

SFLKGTSE

*

: : :

*

. : .:

*

:

*

: .

HBB_HUMAN PDAVMGNPKVKA

H

GKKVLGAFSDGLAHLDN-----LKGTFAT

L

SEL

H

CDKLHVDPENFRL

HBB_HORSE PGAVMGNPKVKA

H

GKKVLHSFGEGVHHLDN-----LKGTFAA

L

SEL

H

CDKLHVDPENFRL

HBA_HUMAN ----HGSAQVKG

H

GKKVADALTNAVAHVDD-----MPNALSA

L

SDL

H

AHKLRVDPVNFKL

HBA_HORSE ----HGSAQVKA

H

GKKVGDALTLAVGHLDD-----LPGALSN

L

SDL

H

AHKLRVDPVNFKL

GLB5_PETMA ADQLKKSADVRW

H

AERIINAVNDAVASMDDT--EKMSMKLRD

L

SGK

H

AKSFQVDPQYFKV

MYG_PHYCA EAEMKASEDLKK

H

GVTVLTALGAILKKKGH-----HEAELKP

L

AQS

H

ATKHKIPIKYLEF

LGB2_LUPLU VP--QNNPELQA

H

AGKVFKLVYEAAIQLQVTGVVVTDATLKN

L

GSV

H

VSKG-VADAHFPV

. .::

*

. : . :

*

.

*

. : : .

HBB_HUMAN LGNVLVCVLAHHFGKEFTPPVQAAYQKVVAGVANALAHKYH------

HBB_HORSE LGNVLVVVLARHFGKDFTPELQASYQKVVAGVANALAHKYH------

HBA_HUMAN LSHCLLVTLAAHLPAEFTPAVHASLDKFLASVSTVLTSKYR------

HBA_HORSE LSHCLLSTLAVHLPNDFTPAVHASLDKFLSSVSTVLTSKYR------

GLB5_PETMA LAAVIADTVAAG---------DAGFEKLMSMICILLRSAY-------

MYG_PHYCA ISEAIIHVLHSRHPGDFGADAQGAMNKALELFRKDIAAKYKELGYQG

LGB2_LUPLU VKEAILKTIKEVVGAKWSEELNSAWTIAYDELAIVIKKEMNDAA---

: : .: ... . :

α-helisa

background image

Metody

Metody

iteracyjne

iteracyjne

Problemy dopasowania progresywnego: dalsze przyrównania zależą

od

początkowej pary sekwencji (szczególnie jeśli są

to sekwencje odległe); błędy

powstałe przy pierwszym przyrównaniu będą

powielane dalej.

Metody iteracyjne -

wielokrotnie przeprowadzają

dopasowania podgrup

sekwencji, a następnie wykonują

przyrównanie tych podgrup w dopasowanie

globalne wszystkich sekwencji. Podgrupy są

wybierane ze względu na ułożenie

na drzewie filogenetycznym lub losowo.

background image

FASTA

FASTA

-

-

algorytm

algorytm

Tworzenie listy słów znaków o zadanej długości (k-tup dla DNA: 4-6; dla białek:
1, 2) i określenie ich położenia w sekwencjach.

MRSCNSCMI

MR

1

RS

2

SC

3, 6

CN

4

NS

5

CM

7

MI

8

MIRSCNCN

MI

1

IR

2

RS

3

SC

4

CN

5, 7

NC

6

Liczenie różnicy położenia dla odpowiednich słów. Słowa, które wykazują

samą

różnicę

w położeniu i znajdują

się

w fazie są

regionem, gdzie sekwencje

pasują

do siebie.

MRSCNSCG

RS

2

SC

3, 6

CN

4

MI

8

IRSCNCN

RS

3

SC

4

CN

5, 7

MI

1

-

=

RS

-1

SC

-1, 2

CN

-1, -3

MI

7

background image

FASTA

FASTA

-

-

algorytm

algorytm

Łączenie znalezionych par słów w regiony początkowe bez przerw znajdujące
się

w pewnej odległości od siebie.

-MRSCNSCMIGWQIAAWYA

MIRSCNCNA--WQAGSWYLA

Łączenie regionów początkowych w większe regiony najlepiej pasujące

(o największej punktacji) i mogące uwzględniać

przerwy.

-MRSCNSCMIGWQIAAWYA

MIRSCNCNA--WQAGSWYLA

Przeprowadzenie optymalnego lokalnego dopasowania w oparciu o algorytm
Smith-Watermana dla wybranych regionów, a następnie pomiędzy całą

sekwencją

wysłaną

i znalezioną

w bazie o najlepszej punktacji. Określenie

istotności statystycznej dopasowań

(E-value).

background image

BLAST

BLAST

-

-

algorytm

algorytm

Tworzenie listy słów znaków o zadanej długości (k-tup dla DNA: 11, 3 w
przypadku tłumaczenia; dla białek: 2, 3) i określenie sąsiadujących
(podobnych) słów –

neighorhood words

(dla sekwencji aminokwasowych).

MLIPQGDELVISWA

MLI

LIP

IPQ

PQG

QGD

GDE

DEL

ELV

LVI

VIS

ISW

SWA

PEG,PRG,PSG,PQA,PAA,LQW,...

GDA,GDF,ASE,QDE,IDL,ADE...

background image

BLAST

BLAST

-

-

algorytm

algorytm

MLIPQGDELVISWA

PQG 18
PEG 15
PRG 14
PKG 14
PNG 13
PDG 13
PHG 13
PMG 13
PSG 13
PQA 12
PQN 12
...

Zidentyfikowanie w obrębie sąsiadujących (podobnych) słów tylko takich (~50),
które najmniej różnią

się

od wzorca wg macierzy BLOSUM62

(>T –

punktacja progowa, score

threshold).

T>13

Poszukiwanie wybranych słów w sekwencjach w bazie danych i ich
przyrównywanie (dopasowywanie). Dla sekwencji DNA szukane są

identyczne

słowa.

GQTERFCVLMLIPQGDELVISWANASSCS

NQWGYASCAALLPRGDFLVLGWIGHAALI

background image

BLAST

BLAST

-

-

algorytm

algorytm

Rozszerzanie dopasowania w regionie, w którym zostały znalezione
przynajmniej dwa słowa, aż

do regionów o niskiej punktacji. Określenie

regionów HSP (high-scoring

segment pair).

GQTERFCVLMLIPQGDELVISWANASSCS

NQWGYASCAALLPRGDFLVLGWIGHAALI

HSP

Przeprowadzenie optymalnego lokalnego dopasowania w oparciu o algorytm
Smith-Watermana uwzględniającego wszystkie znalezione regiony HSP.
Określenie istotności statystycznej dopasowań

(E-value).

background image

Filtrowanie region

Filtrowanie region

ó

ó

w o s

w o s

ł

ł

abej z

abej z

ł

ł

o

o

ż

ż

ono

ono

ś

ś

ci

ci

Maskowanie (nieuwzględnianie w porównaniach sekwencji) regionów
o niskiej złożoności składu, niskiej entropii -

LCR (low-complexity

regions):

powtórzenia nukleotydów lub aminokwasów

ciągi tych samych, dwóch lub jednego znaku

Regiony te mogą

dawać

wysokie wartości punktacji dla sekwencji

w rzeczywistości niehomologicznych

-

wyniki fałszywe pozytywne

Programy do poszukiwania i maskowania tych regionów:

PRSS (w pakiecie FASTA)
SEG (wykorzystywany przez BLASTP)
PSEG
NSEG
DUST (wykorzystywany przez BLASTN)
XNU
RepeatMasker

Filtrowanie tych regionów jest opcją

domyślną

w programie BLAST.

X -

dla aminokwasów, N -

dla nukleotydów

Ponad połowa sekwencji białkowych w bazach posiada przynajmniej jeden LCR

background image

>gi|730028|sp|P40692|MLH1_HUMAN DNA mismatch repair protein Mlh1 1)

Length = 756

Score = 233 bits (593), Expect = 8e-62

Identities = 117/131 (89%), Positives = 117/131 (89%)

Query: 1 IETVYAAYLPKNTHPFLYLSLEISPQNVDVNVHPTKHEVHFLHEESILERVQQHIESKLL 60

IETVYAAYLPKNTHPFLYLSLEISPQNVDVNVHPTKHEVHFLHEESILERVQQHIESKLL

Sbjct: 276 IETVYAAYLPKNTHPFLYLSLEISPQNVDVNVHPTKHEVHFLHEESILERVQQHIESKLL 335

Query: 61 GSNSSRMYFTQTLLPGLAGPSGEMVKXXXXXXXXXXXXXXDKVYAHQMVRTDSREQKLDA 120

GSNSSRMYFTQTLLPGLAGPSGEMVK DKVYAHQMVRTDSREQKLDA

Sbjct: 336 GSNSSRMYFTQTLLPGLAGPSGEMVKSTTSLTSSSTSGSSDKVYAHQMVRTDSREQKLDA 395

Query: 121 FLQPLSKPLSS 131

FLQPLSKPLSS

Sbjct: 396 FLQPLSKPLSS 406

Filtrowanie region

Filtrowanie region

ó

ó

w o s

w o s

ł

ł

abej z

abej z

ł

ł

o

o

ż

ż

ono

ono

ś

ś

ci

ci

LCR (low-complexity

regions

background image

Por

Por

ó

ó

wnanie program

wnanie program

ó

ó

w FASTA i BLAST

w FASTA i BLAST

BLAST

FASTA

może podawać

więcej niż

jeden

region o wysokiej punktacji

podaje tylko jedno najlepsze
dopasowanie

lepszy dla sekwencji białek niż

DNA

lepszy dla sekwencji DNA niż

białek

szybszy niż

FASTA

wolniejszy niż

BLAST

mniej czuły niż

FASTA przy użyciu

domyślnych ustawień

bardziej czuły niż

BLAST

daje gorsze rozróżnienie między
prawdziwymi i fałszywymi homologami

daje lepsze rozróżnienie między
prawdziwymi i fałszywymi homologami


Document Outline


Wyszukiwarka

Podobne podstrony:
bioinformatyka w13 2008 9 web
bioinformatyka w2 2008 web
bioinformatyka w9 2008 web
bioinformatyka w11 2008 web
bioinformatyka w4 2008 web
bioinformatyka w10 2008 web
bioinformatyka w12 2008 9 web
bioinformatyka w3 2008 web
bioinformatyka w7 2008 web
bioinformatyka w1 2008 web
bioinformatyka w8 2008 web
bioinformatyka w5 2008 web
bioinformatyka w13 2008 9 web
bioinformatyka w2 2008 web
bioinformatyka w9 2008 web

więcej podobnych podstron