Srovnání sekvencí - základní vzorce

a= a1 a2 a3………..a100

b= b1 b2 b3………..b100

2

1100

1

2

i

ii baEuklidovská vzdálenost

City Block vzdálenost

100

1i

ii ba

Hammingova vzdálenost # počet odlišných pozic

a= 101010101b= 001110100

Euklidovská vzdálenost =

City Block vzdálenost

Hammingova vzdálenost = 3

100001001

3

1+0+0+1+0+0+0+0+1=3

Dvě struktury jsou homologické tehdy, mají li společného evolučního předka, nebo mají li podobnou strukturu + funkci.

Struktury mají vysoký stupeň homologie jsou li mezi nimi relativněmalé rozdíly.

Jsou určité makromolekuly homologické?Jaká část jedné molekuly je homologická k jaké části druhé molekuly?Jaké dvě makromolekuly mají typicky vysoká stupeň homologie?

Jak se sekvence liší?

Substituce (výměna)

Delece a inzerce

Komprese a expanze

Transpozice I N D U S T R Y

I N T E R E S T

Alignment nebo shodaINDUSTRY

INTEREST

INDUSTRY Delete DINUSTRY Delete UINSTRY Subst Y by SINSTRS Insert EINSTERS Insert EINSTERES Delete SINTERES Insert TINTEREST

Různé analýzy stejného páru

W A T E R W A T E R| |W I N E W I N E 

W A T E R W A T E R| | | |W I N E W I N E

W A T E R W I N E

Algoritmus - Dynamické programování

- podobný koncept jako „ dot matrix“

Aplikována na biologické sekvenceAplikována na biologické sekvence

S. B. Needleman & C. D. Wunsch. A general S. B. Needleman & C. D. Wunsch. A general method applicable to the search for similarities in method applicable to the search for similarities in the amino acid sequence of two proteins. the amino acid sequence of two proteins. J. Mol. J. Mol. Biol. 48:Biol. 48:443-453 (1970)443-453 (1970)

Základní kroky dynamického programování

Základní kroky dynamického programování

1) Inicializace skórovací matice (0 nebo 1)

2) Sumace -nalézt maximální počet shod který může být získán počínaje libovolnou pozicí a pokračováním „vpřed“

3) Traceback k nalezení maximálního alignmentu

Sumace:

1. Start v pravém dolním rohu2. Pohyb nahoru a vlevo o jednu pozici3. Nalezení největší hodnoty buď, v a) v segmentu řádku počínajícím jeden pod aktuální pozicí a pokračováním vpravo, nebo b) v segmentu sloupce počínajícím jeden vpravo od aktuální pozice a pokračováním dolů4. Připočtení této hodnoty k hodnotě aktuálního políčka5. Zopakování kroku 3 a 4 pro všechna políčka vlevo od aktuálního řádku a nahoru od aktuálního sloupce dokud se nedospěje k levému okraji matice.6. Pokud nejsme v levém horním rohu, pokračovat 2

Aplikace Hidden Markova Modelu na proteiny

stejné core všech 20 aminokyselin - karboxylová kyselina - aminoskupina

sekvence – primární struktura

CGGSLLNAN--TVLTAAHCCGGSLIDNK-GWILTAAHCCGGSLIRQG--WVMTAAHCCGGSLIREDSSFVLTAAHC

Primární struktura 4 příbuzných proteinů

CGSLIREDWVLTAAHC

Možný společný předek

Jednoduchý statistický profile

Pravděpodobnost výskytu CGGSV

0.8 * 0.4 * 0.8 * 0.6 * 0.2 = .031

Tímto výpočtem získáváme score pro určitou sekvenci.(Transformace do logaritmické funkce)

loge(0.8)+loge(0.4)+loge(0.8)+loge(0.6)+loge(0.2) = -3.48

Hidden Markov Model je druh dynamického statistického profiluMá komplexnější topologiii

HMM lze vizualizovat jako stroj finitních stavů

Stroj finitních stavů – pohybuje se skrze série stavů a produkujevýstupní stav ať už se stroj nachází v určitém stavu, nebo sepohybuje mezi nimi.

HMM generuje sekvenci proteinu emisí AA při průchodusériemi stavů. Každý stav je charakterizován tabulkouemisních pravděpodobností podobnýcj jako v profilu. Existujíi tranzitní pravděpodobnosti.

HMM – základní schéma

Možný HMM pro sekvenci ACCY. Protein je representovánjako sekvence pravděpodobností.Čísla ukazují pravděpodob-nosti, že se která aminokyselina nachází v danném stavu. Číslau šipek ukazují pravděpodobnosti přechodu mezi stavy.

match

insert

delete

Libovolná sekvence může být representována jedinečnoucestou v HMM. Pravděpodobnost určité sekvence je určena jako součin emisních a transitních pravděpodobnostípodél určité trajektorie (cesty)

ACCY 4 * .3 * .46 * .6 * .97 * .5 * .015 * .73 *.01 * 1 = 1.76x10-6.

loge(.4) + loge(.3) + loge(.46) + loge(.6) + loge(.97)

+ loge(.5) + loge(.015) + loge(.73) +loge(.01) + loge(1) = -13.25

Výpočet je jednoduchý je li známa cesta. Ve skutečném modeluexistuje mnoho různých cest generující téže sekvenci. Proto přesná pravděpodobnost sekvence je suma pravděpodobnostípřes všechny možné stavové trajektorie.

Výpočet nejlepší cesty:Výpočet nejlepší cesty:

- Viterbův algoritmus- forwarding algoritmus

Problém ACCY:

stavy: M – match, I – insertion, D – deletion

1)Pravd. že A je generováno jao stav I0 je vypočteno a vneseno do matice2)Pravd. že C je emitováno do stavu M1 a do stavu I1 je vneseno do matice jako C a I1/M13)vypočte se max (I1/M1)4)pointer je posunut od vítěze do stavu I05)opakuje se 2-5 dokud se matice nenaplní

Matice Viterbiho algoritmu

Význam score:

Model je generalizací jak jsou AA distribuovány v určité grupěpříbuzných sekvencí. Score tedy znamená příslušnost k dannétřídě.

Lokální versus globální scoring.

Problémy:

Vybudování setu pro HMM, je třeba odhadnout emisníkoeficienty. K tomu je třeba série příbuzných testovacích sekvencí.

Pokud je stavová trajektorie známa, je možné vypočítatjednotlivé pravděpodobnosti. V opačném případě je nalezenínejlepšího modelu pro danou testovací sadu problémem kterýnemá řešení v uzavřené formě.

Vážení sekvencí:

malá skupina vysoce podobných sekvencí může vnést do modelu nechtěnou závislost.

řešení: - vážení sekvencí

I0=I1+I2 I1=I2I2=I3+I4 I3=I4I3=I5+I6 I5=I6I4=I7+I8 I7=I8

I1=I2= .5 * I0I3=I4= .25*I1I5=I6=I7=I8= .125 * I1

Genetický algoritmus

The so-called genetic algorithm is a heuristic method that operates on pieces of information like nature does on genes in the course of evolution. Individuals are represented by a linear string of letters of an alphabet (in nature nucleotides, in genetic algorithms bits, characters, strings, numbers or other data structures) and they are allowed to mutate, crossover and reproduce. All individuals of one generation are evaluated by a fitness function. Depending on the generation replacement mode a subset of parents and offspring enters the next reproduction cycle. After a number of iterations the population consists of individuals that are well adapted in terms of the fitness function.

Základní popis genetického algoritmu

1) Je stvořena populace individualit- individua jsou charakterizována a vyjádřena jako sekvence bitů. (obecně – řada)- je definována tzv. fittness funkce. je definována tak, že vezme jako vstup individuum a poskytne jako výstup číslo nebo vektor který udává kvalitu individua- určí se hierarchie individuí podle fittness funkce

2) Provede se ohodnocení všech individuí v první populaci

3) Vytvoří se nová individua. Reprodukční schopnost individuí je proporcionální jejich hierarchii v danné populaci. Zahrnuje

následující operace

Mutace Variace Křížení

4) Výběr individuí pro novou generaci rodičů - v originálním genet. algoritmu se zavrhnou rodiče

a pouze individua z nové generace mohou tvořit příští rodiče

- upravovaný GA uvažuje pro zhodnocení celou populaci včetně rodičů. Do další generace jsou selektováni

fittness funkcí. (tzv. elitářská výměna)

5) opakuj kroky 2 až 4 dokud není dosaženo požadované vlastnosti, nebo dokud neproběhne předepsaný počet iterací

Matematické základy GA položil J.H.Holland v tzv. „schemata theorem“

-schema je generalizací nebo částí individua

01010010100101010101110101010101 a01011010100101110001110111010111

může být sumarizováno schematem:

0101#010100101#10#011101#10101#1

Očekávané množství výskytu určitého schematu v čase t+1

Úloha: největší druhá mocnina integer < 32

Evoluční strategie:

jde o optimalizační problém stejně jako u GA

Rozdíly:

-ES byla vytvořena jako optimalizační funkce-reprodukce v GA je proporcionální fittness funkci, nikoli v ES-GA činí rozdíly mezi genotypem a fenotypem, ES nikoli-v ES rodiče i potomci kompetují o přežití, nikoli v orig. GA-mutace je řídící silou u ES zatímco pro GA je to křížení

Hydropathy/Hydrophilicity/ Hydrophobicity

Hydropathy/Hydrophilicity/ Hydrophobicity

• Hydropathy & Hydrophobicity– stupeň ukazující “water hating” či “water

fearing”

• Hydrophilicity– stupeň ukazující “water loving”

Hydropathy/Hydrophilicity/ Hydrophobicity Analýza

Hydropathy/Hydrophilicity/ Hydrophobicity Analýza

Cíl: Nalézt kvantitativní popis stupně expozice proteinu

do vodného prostředí

Východisko: Tabulka expozic jednotilých aminokyselin

Hydrophobicity/Hydrophilicity Tables

Hydrophobicity/Hydrophilicity Tables

• Popisuje pravděpodobnost pro každou aminokyselinu, že bude nalezena ve vodném prostředí

• Používaná kriteria– Kyte-Doolittle hydropathy– Hopp-Woods hydrophilicity– Eisenberg et al. normalizovaná consensuální

hydrophobicita

Kyte-Doolittle hydropathyKyte-Doolittle hydropathyAminoAcid

Index AminoAcid

Index

R -4.5 S -0.8K -3.9 T -0.7D -3.5 G -0.4Q -3.5 A 1.8N -3.5 M 1.9E -3.5 C 2.5H -3.2 F 2.8P -1.6 L 3.8Y -1.3 V 4.2W -0.9 I 4.5

Hydrophilicity Plot - Příklad Hydrophilicity Plot - Příklad

Tento plot je pro tubulin, rozpustný cytoplasmatický protein. Regiony s vysokou hydrophilicitou jsou pravděpodobně exponovány do solventu (cytoplasmy), zatímco hydrophilní jsou pravděpodobně uvnitř nebointeragují s jinou částí proteinu

okno 7 AA

Amphiphilicity/AmphipathicityAmphiphilicity/Amphipathicity

K nalezení takové sekvence hledáme oblasti

kde se střídají krátké úseky nabitých aminokyselin

s kratkými úseky hydrofobních v opakované délce

která koresponduje s periodou ve struktuře