Bioinformatyka

Wykład Bioinformatyka

Wykład 5, 2008

Bioinformatyka

Wykład 5

E. Banachowicz

Zakład Biofizyki Molekularnej

IF UAM

http://www.amu.edu.pl/~ewas

Porównywanie sekwencji

• Pierwsze pytanie biologa molekularnego,

kiedy odkryje nową sekwencję:

Czy w bazie sekwencji są już sekwencje podobne

do mojej?



sekwencje są identyczne –

nic nowego….

 sekwencja jest podobna (ma „krewnych”)

– nowy członek

znanej rodziny

 sekwencja ma kilka podobnych regionów, motywów lub

domen

– można zaproponować funkję

 Nie ma znaczącego podobieństwa

– dużo pracy…..

Wykład Bioinformatyka

Wykład 5, 2008

Porównywanie sekwencji

• Celem porównania białek jest między

innymi przypisanie informacji znanej dla
jednej cząsteczki drugiej cząsteczce

Algorytmy

• macierze punktowe (DotPlot)
• programowanie dynamiczne
• metody heurystyczne (BLAST, FASTA)
• metody statystyczne (modele Markova,

statystyka Bayesa)

Rodzaje dopasowań

• pokrycie sekwencji

– globalne, lokalne

• liczba sekwencji porównywanych

– para (pairwise sequence alignment)

– więcej niż dwie (multiple sequences alignment)

Wykład Bioinformatyka

Wykład 5, 2008

Pokrycie sekwencji

• dopasowanie globalne – dopasowanie

wzdłuż całej sekwencji

(zastosowanie: do białek

składających się z pojedynczej domeny lub
homologicznych słabo zróżnicowanych)

• dopasowanie lokalne – uwzględnia

domenową naturę białek, szuka
subsekwencji (

zastosowanie: do białek

wielodomenowych, mRNA z sekwencją genomową

)

Macierze punktowe (DotPlot)

•

http://www.biophys.uni-duesseldorf.de/local/DOTPLOT/dotplot.html

• Dotter:

http://www.cgb.ki.se/cgb/groups/sonnhammer/Dotter.html

•

http://www.changbioscience.com/res/resd.html

• wykrywają fragmenty powtarzalne i rearanżacje
• opierają się na ocenie wizualnej – czasami skuteczniejsze niż

alignment

Wykład Bioinformatyka

Wykład 5, 2008

H5N1 (HA, swan)

H5N1 (HA, chicken)

Dotter

• niektóre układy punktów tworzą ścieżkę
• każda ścieżka odpowiada jednemu dopasowaniu

M Y S E Q U E N C E

M Y

S E Q

U E N C E

H I S

S E Q

E N C E

M Y

E Q U

E N C E

H I

S E Q

E N C E

znaleźć najlepszą
ścieżkę!

Wykład Bioinformatyka

Wykład 5, 2008

Liniowe zestawienie dwóch sekwencji

Pairwise Sequence Alignment

ABEERNALEDLAGERDFWGALSTOUTWRARWATERA

ACBEERGYALEDILAGERAFGSTOUTFAWATERM

sekwencja 2

sekwencja 1

ClareSansom

Punktacja dla białek jest bardziej złożona – 20 aminokwasów

ABEERNALEDLAGERDFWGALSTOUTWRARWATERA

ACBEERGYALEDILAGERAFGSTOUTFAWATERM

ClareSansom

Wykład Bioinformatyka

Wykład 5, 2008

ABEERNALEDLAGERDFWGALSTOUTWRARWATERA

ACBEERGYALEDILAGERAFGSTOUTFAWATERM

ClareSansom

ABEERNALEDLAGERDFWGALSTOUTWRARWATERA

ACBEERGYALEDILAGERAFGSTOUTFAWATERM

ClareSansom

Wykład Bioinformatyka

Wykład 5, 2008

ABEERNALEDLAGERDFWGALSTOUTWRARWATERA

ACBEERGYALEDILAGERAFGSTOUTFAWATERM

ClareSansom

ABEERNALEDLAGERDFWGALSTOUTWRARWATERA

ACBEERGYALEDILAGERAFGSTOUTFAWATERM

ClareSansom

Wykład Bioinformatyka

Wykład 5, 2008

ABEERNALEDLAGERDFWGALSTOUTWRARWATERA

ACBEERGYALEDILAGERAFGSTOUTFAWATERM

Insercja/Delecja => GAPS

zestawienie – jeden-do-jeden

przerwy odzwierciedlają wydarzenia ewolucyjne

(wyzwanie dla programistów)

ClareSansom

ABEERNALEDLAGERDFWGALSTOUTWRARWATERA

ACBEERGYALEDILAGERAFGSTOUTFAWATERM

Insercja/Delecja => GAPS

ClareSansom

Wykład Bioinformatyka

Wykład 5, 2008

ABEERN-ALEDLAGERDFWGALSTOUTWRARWATERA

ACBEERGYALEDILAGERAFGSTOUTFAWATERM

Insercja/Delecja => GAPS

ClareSansom

ABEERN-ALED-LAGERDFWGALSTOUTWRARWATERA

ACBEERGYALEDILAGERAFGSTOUTFAWATERM

Insercja/Delecja => GAPS

ClareSansom

Wykład Bioinformatyka

Wykład 5, 2008

ABEERN-ALED-LAGERDFWGALSTOUTWRARWATERA

ACBEERGYALEDILAGERAFG-STOUTFAWATERM

Insercja/Delecja => GAPS

ClareSansom

ABEERN-ALED-LAGERDFWGALSTOUTWRARWATERA

ACBEERGYALEDILAGERAFG--STOUTFAWATERM

Insercja/Delecja => GAPS

ClareSansom

Wykład Bioinformatyka

Wykład 5, 2008

ABEERN-ALED-LAGERDFWGALSTOUTWRARWATERA

ACBEERGYALEDILAGERAFG---STOUTFAWATERM

Insercja/Delecja => GAPS

ClareSansom

ABEERN-ALED-LAGERDFWGALSTOUTWRARWATERA

ACBEERGYALEDILAGERAFG---STOUTFA-WATERM

Insercja/Delecja => GAPS

ClareSansom

Wykład Bioinformatyka

Wykład 5, 2008

ABEERN-ALED-LAGERDFWGALSTOUTWRARWATERA

ACBEERGYALEDILAGERAFG---STOUTFA--WATERM

Insercja/Delecja => GAPS

ClareSansom

ABEERN-ALED-LAGERDFWGALSTOUTWRARWATERA

ACBEERGYALEDILAGERAF-G--STOUTFA--WATERM

G<->W = -7
G<->G = +5

Insercja/Delecja => GAPS

ClareSansom

Wykład Bioinformatyka

Wykład 5, 2008

A-BEERN-ALED-LAGERDFWGALSTOUTWRARWATERA

ACBEERGYALEDILAGERAF-G--STOUTFA--WATERM

G<->W = -7
G<->G = +5

A<->C = -2
A<->A = +2

Insercja/Delecja => GAPS

ClareSansom

Insercja/Delecja => GAPS

• Punktownia przerw  programowanie

dynamiczne

Wykład Bioinformatyka

Wykład 5, 2008

Najlepsza ścieżka

optymalna?

najszybsza?

najkrótsza?

Madryt –Poznań

http://www.viamichelin.com

Najlepsza ścieżka?

A T

C T

G
A

T
T

C
C

Wykład Bioinformatyka

Wykład 5, 2008

Algorytm Needlemana-Wunscha

• strategia „najlepszej ścieżki” –

programowanie dynamiczne

• przeszukiwanie dotyczy pełnego zakresu

sekwencji (obszaru dopasowania)-
dopasowanie globalne

• każda podścieżka stanowić może fragment

optymalnej ścieżki. Ścieżki szuka się
poszerzając zakres podscieżek.

Needlemann, Wunch (1970) J.Mol.Biol. 48, 443-453

Sekwencja A

Wykład Bioinformatyka

Wykład 5, 2008

Algorytm Smitha-Watermana

• dopasowanie lokalne
• ścieżka dopasowania nie musi osiągać krawędzi

analizowanej sekwencji

• ścieżka jest lokalnie optymalna jeśli jej

wydłużanie/skracanie nie poprawia obliczonej dla niej

wartości

• system wartościowania dopasowania zaniża wartości w

regionach słabego dopasowania = przerwanie ścieżki

• mogą istnieć ścieżki złożone z kilku połączonych

ścieżek

Smith, Waterman (1981) J.Mol.Biol. 147, 195-197

Szukanie wielu dopasowań

-subdopasowania

• Metoda optymalna daje zawsze najlepsze

dopasowanie – nawet jeśli nie ma ono znaczenia
biologicznego

→ znaczących, niezachodzących na siebie

dopasowń lokalnych można naleźć kilka –
subdopasownia

Trzeba szukać więcej niż jednego dopasowania!

(lalign, SIM)

Przykład:
•Czynnik krzepnięcia IX (F9, SWISS-PROT P00740)
•Czynnik krzepnięcia XII (F12, SWISS-PROT P00748)

Wykład Bioinformatyka

Wykład 5, 2008

Dopasowanie optymalne

i suboptymalne

>sp|P00740|FA9_HUMAN Coagulation factor IX precursor (EC 3.4.21.22)
(Christmas factor) (Plasma thromboplastin component) (PTC) [Contains:
Coagulation factor IXa light chain; Coagulation factor IXa heavy chain] -
Homo sapiens (Human).
MQRVNMIMAESPGLITICLLGYLLSAECTVFLDHENANKILNRPKRYNSGKLEEFVQGNL
ERECMEEKCSFEEAREVFENTERTTEFWKQYVDGDQCESNPCLNGGSCKDDINSYECWCP
FGFEGKNCELDVTCNIKNGRCEQFCKNSADNKVVCSCTEGYRLAENQKSCEPAVPFPCGR
VSVSQTSKLTRAETVFPDVDYVNSTEAETILDNITQSTQSFNDFTRVVGGEDAKPGQFPW
QVVLNGKVDAFCGGSIVNEKWIVTAAHCVETGVKITVVAGEHNIEETEHTEQKRNVIRII
PHHNYNAAINKYNHDIALLELDEPLVLNSYVTPICIADKEYTNIFLKFGSGYVSGWGRVF
HKGRSALVLQYLRVPLVDRATCLRSTKFTIYNNMFCAGFHEGGRDSCQGDSGGPHVTEVE
GTSFLTGIISWGEECAMKGKYGIYTKVSRYVNWIKEKTKLT

>sp|P00748|FA12_HUMAN Coagulation factor XII precursor (EC 3.4.21.38)
(Hageman factor) (HAF) [Contains: Coagulation factor XIIa heavy chain; Beta-
factor XIIa part 1; Beta-factor XIIa part 2; Coagulation factor XIIa light
chain] - Homo sapiens (Human).
MRALLLLGFLLVSLESTLSIPPWEAPKEHKYKAEEHTVVLTVTGEPCHFPFQYHRQLYHK
CTHKGRPGPQPWCATTPNFDQDQRWGYCLEPKKVKDHCSKHSPCQKGGTCVNMPSGPHCL
CPQHLTGNHCQKEKCFEPQLLRFFHKNEIWYRTEQAAVARCQCKGPDAHCQRLASQACRT
NPCLHGGRCLEVEGHRLCHCPVGYTGPFCDVDTKASCYDGRGLSYRGLARTTLSGAPCQP
WASEATYRNVTAEQARNWGLGGHAFCRNPDNDIRPWCFVLNRDRLSWEYCDLAQCQTPTQ
AAPPTPVSPRLHVPLMPAQPAPPKPQPTTRTPPQSQTPGALPAKREQPPSLTRNGPLSCG
QRLRKSLSSMTRVVGGLVALRGAHPYIAALYWGHSFCAGSLIAPCWVLTAAHCLQDRPAP
EDLTVVLGQERRNHSCEPCQTLAVRSYRLHEAFSPVSYQHDLALLRLQEDADGSCALLSP
YVQPVCLPSGAARPSETTLCQVAGWGHQFEGAEEYASFLQEAQVPFLSLERCSAPDVHGS
SILPGMLCAGFLEGGTDACQGDSGGPLVCEDQAAERRLTLQGIISWGSGCGDRNKPGVYT DVAYYLAWIREHTVS

P00740

P00748

ExPasy

Dopasowanie optymalne

i suboptymalne

lalign

http://www.ch.embnet.org/software/LALIGN_form.html

Wykład Bioinformatyka

Wykład 5, 2008

oraz dopasowania 2 i 3:

SIM

http://www.expasy.ch/tools/sim-prot.html

P00740
P00748

Wykład Bioinformatyka

Wykład 5, 2008

Wartości substytucji

i kary za przerwy

• schemat wartościowania I:

– (match) dopasowany: +1
– (mismatch) niedopasowany: -1
– (gap) przerwa: -1

(nie-afiniczne kary za przerwy –każda przerwa traktowana jest tak samo)

• schemat wartościowania II:

– dopasowany: +1
– niedopasowany: -1
– otwarcie przerwy: G
– przedłużenie przerwy: L

(afiniczne kary za przerwy –kara za otwarcie, kary za przedłużenie )

Punktacja

S – punktacja za dopasowanie
Score = Max(S)

ATTGTCAAAGACTTGAGCTGATGTGCAAATT

GGTCAGACATGA-CTGACAAGGGTATCGCCA

obszar dopasowania

dopasowanie

niedopasowanie

przerwa

S =



(dopasowania) -



(niedopasowania) -



(przerwy)

Wykład Bioinformatyka

Wykład 5, 2008

Punktowanie przerw

• non-affine model (nieafinicznie): równo

(match:4, mismatch:-3, gap:-4)

• affine model (afinicznie): G + L n

(match:4, mismatch:-3, gap creation:-8, gap:-4)

A T G C

A 4 -3 -3 -3

T -3

4 -3 -3

G –3 -3

4 -3

C -3 -3 -3

GGTGCCAC-TCCAC-----CTG
AGTGCCACCCCCAATGCCGCTG

-3 4 4 4 4 4 4 4-4-3 4 4 4-3-4-4-4-4-4 4 4 4 :23
-3 4 4 4 4 4 4 412-3 4 4 4-312-4-4-4-4 4 4 4 :7

GGTGCCAC-TCCA---C--CTG
AGTGCCACCCCCAATGCCGCTG

-3 4 4 4 4 4 4 4-4-3 4 4 4-4-4-4 4-4-4 4 4 4 :26
-3 4 4 4 4 4 4 412-3 4 4 412-4-4 412-4 4 4 :2

4 -12

-3 -12

4 -12 4 -12

Programowanie dynamiczne –

najlepsza ścieżka

• schemat wartościowania I:

– (match) dopasowany: +1
– (mismatch) niedopasowany: -1
– (gap) przerwa: -1

(nie-afiniczne kary za przerwy –każda przerwa traktowana jest tak samo)

A T

C T

G
A

T
T

C
C

Wykład Bioinformatyka

Wykład 5, 2008

Programowanie dynamiczne
zasady:

A T

C T

G
A

T
T

C
C

dopasowane z

= -1

dopasowane z

= +1

NULL

dopasowane z

= -1

dopasowane z

NULL

= -1

Programowanie dynamiczne

-1

Wykład Bioinformatyka

Wykład 5, 2008

Programowanie dynamiczne

-1

stopniowe

poszerzanie ścieżek

-1

-2

Programowanie dynamiczne

-1

stopniowe

poszerzanie ścieżek

-1

-2

Wykład Bioinformatyka

Wykład 5, 2008

Programowanie dynamiczne

stopniowe

poszerzanie ścieżek

-1

-2

-1

Programowanie dynamiczne

stopniowe

poszerzanie ścieżek

-1

-2

-1

-3

-2

-1

-3

-1

Wykład Bioinformatyka

Wykład 5, 2008

Programowanie dynamiczne

stopniowe

poszerzanie ścieżek

-1

-2

-1

-3

-2

-1

-3

-1

-4

-5

-2

-3

-1

-3

-5

-4

-2

•wszystkie punkty
musza zostać zbadane

Programowanie dynamiczne

stopniowe

poszerzanie ścieżek

-1

-2

-1

-3

-2

-1

-3

-1

-4

-5

-2

-3

-1

-5

-4

-2

-6

-7

-4

-5

-3

-2

-1

-8

-7

-6

-5

-4

-3

-4

-3

-2

-1

-2

-1

Wykład Bioinformatyka

Wykład 5, 2008

Programowanie dynamiczne

stopniowe

poszerzanie ścieżek

-1

-2

-1

-3

-2

-1

-3

-1

-4

-5

-2

-3

-1

-5

-4

-2

-6

-7

-4

-5

-3

-2

-1

-8

-7

-6

-5

-4

-3

-4

-3

-2

-1

-2

-1

GA-TACTA
GATTACCA

Programowanie dynamiczne

stopniowe

poszerzanie ścieżek

GA-TACTA
GATTACCA

Wykład Bioinformatyka

Wykład 5, 2008

Statystyczne znaczenie dopasowań

• jaka jest wartość/ istotność dopasowania?

Dla dopasowań globalnych:
porównanie obliczonej wartości dla danego dopasowania z
wartościami obliczonymi dla wielu dopasowań
przypadkowych sekwencji o podobnym składzie i długości

Dla dopasowań lokalnych:
podstawą jest rozkład wartości granicznej,
scharakteryzowanej paramerami K i λ

ćwiczenia