5/21/2012 Chemoinformatika a bioinformatika Sequence alignment Osnova 1. Struktura biomakromolekul - sekvence 2. Alignment a jeho typy 3. Užívané algoritmy 4. Multiple sequence alignment 5. Programové balíky 6. Benchmark - porovnávání alignmentů Aminokyseliny j. Qj- Jr (CTI"* ISŮ Ä" název popis dle vlastní volbyj SEKVENCESEKVENCESEKVENCESEKVENC ESEKVENCESEKVENCE Pair-wise alignment Srovnání dvou sekvencí Sekvence mohou být seřazeny v celé své délce (global alignment) nebo jen v určitém regionu (local alignment). Local alignment Hledá úseky dvou sekvencí, které si podle zvolených kritérií dobře odpovídají. Nesnaží se zahrnout celé sekvence, pokud si jejich některé části neodpovídají. Global alignment Vychází z předpokladu, že obě srovnávané sekvence jsou víceméně shodné v celé své délce. Alignment k sobě přikládá celé sekvence (od počátku do konce) a to včetně částí, které si nepříliš odpovídají. Algoritmy • Téměř výhradně se užívají heuristické algoritmy - nalezení výsledku v dostatečně krátkém čase • Vývoj algoritmů je prováděn v návaznosti na srovnávání výsledků s tzv. zlatým standardem - alignment na základě známé 3D struktur 2 5/21/2012 Scoring matrix (skórovací matice) (a) HIWKN HL-KN (b) HIWKN H-LKN Scoring matrix (skórovací matice) Dvě sekvence považujeme za příbuzné, vycházejí-li ze společného předka; pak dobu potřebnou k jejich evoluci můžeme odvodit z množství rozdílů mezi nimi Záměna aa je častější než inserce/delece. Pravděpodobnost změny jedné aminokyseliny na jinou je přímo úměrná podobnosti obou aminokyselin. Matice vzniká přiřazením hodnoty (pravděpodobnosti) jednotlivým dvojcím aminokyselin v závislosti na jejich vzájemné „zastupitelnosti" - pravděpodobnosti substituce Typy matic • PAM (Point Accepted Mutation) - založena na mutacích v rámci globálního alignmentu, tj. ve vysoce konzerovovaných i mutabilních Oblastech. PAM 250 znamená, že 250 mutaci na 100 AA může nastat, PAM 10 akceptuje pouze 10 na 100, takže pouze velice podobné sekvence dosáhnou na pozitivní skóre. • BLOSUM (Blocks Substitution Matrix) - je odvozena z vysoce konzervovaných oblastí neobsahujících mezery - z těch počítá relativní zastoupení aa a pravděpodobnost jejich substitucí —► lepší pro lokální alignment. Je využívána v blastp, vnodná pro identifikaci neznámé nukleotidové sekvence. BLOSUM matrices vysokými čísly je dobrá pro porovnáni vysoce příbuznýcb sekvencí, zatímco nízké pro relativné vzdálené podobnosti • GÖNNET-vytvořena 1992, postupným opakováním cyklu: pairwise alignment- nová matice - nový pairwise alignment- nová matice... • DNA identity matrix V rámci jednoho typu existuje více jednotlivých matic založených na stejném principu, které se však liší konkrétními hodnotami a tedy i oblastí použití (vysoce příbuzné nebo naopak velmi vzdálené sekvence). Matice PAM 250 -3 -2 0 -1 -1 -1 -3 -2 -1 -1 0 -2 -2 -2 -2 -2 -2 -2 4 2 5 -2 -2 -3 -3 2 4 2 6 -5 -2-5-4-1 0 1 2 9 -4 0 -4 -5 -2 -2 -1 -1 7 10 -5 -3 -3_2 -6 -4 -5 -2_0_0 17 QHKRVMILF YW Matrice BLOSSUM vypadá analogicky, liší se hodnoty. A',r. Gly MM PhF? Thi Tip Tyr Vil Matice BLOSUM 62 Aťí Ajfl Alp C*$ GIa Olu Gly Lyí M#t Ph* Pří $+r- Thř Trp Tyr Val 3 5/21/2012 DNA matice A 1 T -10000 1 G -10000 -10000 i C -10000 -10000 -10000 i A T G C Jako pozitivní je uvažována pouze shoda, jakákoliv substituce je vysoce penalizována; jsou však povoleny mezery. Mezery (Gaps) Příčiny vzniku mezer: • Bodová mutace (velmi častá příčina) • Nepřesný crossover při meiose (inzerce nebo delece řetězce bází) • DNA slippage během replikace (vzniká repetice -opakující se sekvence v řetězci) • Inzerce retroviru • Translokace DNA mezi chromozomy Mezery nacházíme na začátku řetězce, uprostřed nebo na jeho konci. O ctgcggg---ggtaat i i i i i i i i —gcgg-agagg-aa- Mezery umožňují alignment sekvencí, kdy v jedné z nich došlo k deleci. Zvyšují však také možnost alignmentu náhodných sekvencí. Jejich přítomnost je proto vždy „penalizována", a to více než substituce. Čím nižší je penalizace mezer, tím lepší (dokonalejší) bude alignment, ovšem z biologického hlediska může jít o nesmysl. Jednotlivé programy obvykle penalizují přítomnost mezery (gap open) a také zvyšují penalizaci s délkou mezery (gap ext). Krátká mezera: atcttcagtgtttcccctgt tttgccc.atttagt tcgctc ii i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i ii atcttcagtgtttcccctgttttgcccgatttagttcgctc Dlouhá mezera: atcttcagtgtttcccctgt tttgccc....................atttagt tcgctc ii i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i ii atcttcagtgtttcccctgttttgcccgcccccccccccccccccccatttagttcgctc Skóre Každé dvojici sekvencí je ve výsledku přiřazeno číslo - skóre, které určuje míru jejich podobnosti Čím vyšší je skóre, tím vyšší je podobnost. Podle použité matice může být skóre i záporné. Příklad výpočtu AABBCCDDEEF AADDKKKEFGG Ve chvíli, kdy zafixujeme pozici dvou sekvencí, pak můžeme snadno vypočítat skóre pro dané přiložení (příklad BLOSUM 62): skóre pro dané přiložení = skóre na bázi jednotlivých aa + celková penalizace metod Například, celkové pozitivní skóre na úrovnijednotlivých aa ääbbccdd--eef a a - - - -ddkkkefgg 4+4 + 6 + 6 +1+5+6 = 32 Naopak, pro každou mezeru (-) je dána penalizace: první výskyt zleva -10, každá následující -1. aabbccdd--eef a a - - - -ddkkkefgg -10-1-1-1 -10-1 = -24 Celkové skóre 32 - 24 = 8 Multiple sequence alignment - MSA (mnohonásobné srovnáno Multiple alignment slouží k: • Nalezení „diagnostického vzoru" (diagnostic patterns) na jehož základě jsou charakterizovány proteinové rodiny • Odhalení či dokázání homologie mezi novou sekvencí a sekvencemi v databázích • Určení vzájemné příbuznosti sekvenci v rámci skupiny -tvorba fylogenetických stromů • Predikci sekundární a terciární struktury nových proteinů • Navržení primem (oligonukleotidů) pro PCR 4 5/21/2012 Metody MSA • Dynamické programování (dynamic programming) - rozšíření pairwise alignmentU - náročné na paměť a čas, nevhodné pro více než 3-4 sekvence (n=rozměrný prostor) • Progresivní alignment (progressive sequence alignment) - nejčastěji používaný k vytvoření alignmentu; využívá fylogenetické informace - hierarchický, nejdříve identifikuje nejpodobnější sekvence a následně inkorporuje ostatní • Iterativní alignment (iterative sequence alignment) - odstraňuje problémy progresivního alignmentu, který je závislý na prvotním přiložení nejpodobnějších sekvencí pomocí opakování alignmentu pro podskupiny sekvencí následující po globálním alignmentu • Hledání motivů - nalezení částí konzervovaných sekvenčních motivů pomocí globálního přiložení a následně „hodnocení" těcto úseků nezávisle na celé sekvenci Metody MSA Dynamické programování Simultánní alignment všech sekvencí - analogické pairwise alignmentu Programové balíky: MSA (Lipman et al., 1989) a DCA (Stoye et al., 1997), založené na Carrilově a Lipmanově algoritmu (1988) Využívá skórovací matice, ale vytváří n-rozměrný prostor (n = počet sekvencí) Extrémně náročný na výpočetní kapacity I při zjednodušení nepoužitelné pro více než cca 20 sekvencí Progresivní multiple alignment • Používá ho většina programů • Vznik-1987 Feng, D.-F. and Doolittle, R.F. (1987) J. Mol. Evol. 25, 351-360. 1) sestavení příbuzenského stromu (guide tree) z nepřiložených sekvencí Progresivní multiple alignment ■ Používá ho většina programů ■ Vznik-1987 Feng, D.-F. and Doolittle, R.F. (1987) J. Mol. Evol. 25, 351-360. 1) sestavení příbuzenského stromu (guide tree) z nepřiložených sekvencí 2) tvorba párových alignmentu postupně podle příbuznosti (topologie guide tree) • Dnes obsahuje často iterativní smyčku Guide tree vs. phylogenetic tree Guide tree je vypočítán na základě matice vzdáleností (distance matrix) vytvořené podle skóre pairwise alignmentu. Výstupem je .dnd soubor. Phylogenetic tree je vypočten na základě vytvořeného MSA. Vzdálenosti mezi sekvencemi jsou vypočteny a uloženy jako .ph soubor. Následně je možno je využít pro konstrukci fylogenetického stromu (soubory .nj, .ph, ,dst) pomocí zvolené metody (nj, phylip, dist). .dnd soubor PAIIĽ0.16435, RSIIL0.13654) :0.03384, ( CVIIL0.16563, BCLB:0.26800) :0.02264, ( ( BCLA:0.17899, BCLD:0.26633) :0.18717, BCLC:0.29707) :0.03484); 5 5/21/2012 Length - number of sites used in comparison 1 vs 2 DIST= 0 6491 length = 1 vs 3 DIST= 0 6342 length = 1 vs 4 DIST = 0 9293 length = 1 vs 5 DIST= 0 9035 length = 1 vs 6 DIST = 0 9336 length = 1 vs 7 DIST= 0 9325 length = 2vs 3 DIST= 0 3772 length = 2vs 4 DIST = 0 9123 length = 2vs 5 DIST= 0 3947 length = 2vs 6 DIST = 0 9123 length = 2vs 7 DIST= 0 9336 length = 3vs 4 DIST= 0 9123 length = 3vs 5 DIST = 0 9336 length = 3vs 6 DIST= 0 9293 length = 3vs 7 DIST= 0 9474 length = 4vs 5 DIST = 0 9211 length = 4 us 6 DIST= 0 9035 length = 4vs 7 DIST= 0 9649 length = 5vs 6 DIST = 0 9561 length = 5vs 7 DIST = 0 9211 length = 6vs 7 DIST= 0 9649 length = Neighbor-joining Method Saitou, N. and Nei, M. (1937) The Neighbor-joining Method: A New Method for Reconstructing PhylogeneticTrees. Mol. Biol. Evol., 4(4) ,406-425 This is an UNROOTED tree Numbers in parentheses are branch lengths Cycle 1 = SEQ: 2 ( 0.17307)joins SEQ: 3( 0.19912) Cycle 2 = SEQ: 1( 0.34101) joins Node: 2( 0.13706) Cycle 3 = SEQ: 5( 0.44293)joins SEQ: 7 ( 0.47307) Cycle 4 = SEQ: 4( 0.44513)joins SEQ: 6 ( 0.45333) Cycle 5 (Last cycle, trichotomy): Node: 1 ( 0.12171)joins Node: 4 ( 0.01364)joins Node: 5 ( 0.02033) ■nj soubor .ph soubor PAIIĽ0.34101, ( RSIIL0.17807, CVIIL0.19912) :0.13706) :0.12171, ( BCLA:0.44518, BCLC:0.45833) :0.01864, ( BCLB:0.44298, BCLD:0.47807) :0.02083); .dst soubor 7 PAUL 0.000 0.649 0.684 0.930 0.904 0.939 0.982 RSIIL 0.649 0.000 0.377 0.912 0.895 0.912 0.939 CVIIL 0.684 0.377 0.000 0.912 0.939 0.930 0.947 BCLA 0.930 0.912 0.912 0.000 0.921 0.904 0.965 BCLB 0.904 0.895 0.939 0.921 0.000 0.956 0.921 BCLC 0.939 0.912 0.930 0.904 0.956 0.000 0.965 BCLD 0.982 0.939 0.947 0.965 0.921 0.965 0.000 Phylogram a cladogram • Phylogram (phylogeny tree) - je rozvětvený diagram (strom), který naznačuje fylogenezi (postupný vývoj). Délka jednotlivých větví je úměrná velikosti změny v průběhu evoluce. • Cladogram - rovněž strom, v němž však všechny větve mají stejnou délku. Ukazuje tak sice „společné předky" pro jednotlivé sekvence, ale ne množství změn, jež od té doby prodělaly (evoluční dobu). Phy 8 m Phylogram II —- Cladogram íÉpf 1 — í —- Iterativní přístup (Gotoh, 1996; Notredame & Higgins, 1996) Vzniklý strom i alignment jsou následně optimalizovány do konvergence. Jinak jsou chyby vzniklé při prvním alignmentu (tvorba stromu) zachovány i ve výsledku. Nezaručuje nalezení nejlepšího výsledku, ale -na rozdíl od deterministických alternativ-je dostatečně robustní a dobře použitelný i pro velký počet sekvencí. 6 5/21/2012 Kombinace local a global alignment • S výhodou lze kombinovat lokální a globální alignment. • Lokální alignment může být reprezentován sadou kotvících bodů v místě dobré shody • Následný globální alignment pak tyto odpovídající úseky sekvencí zahrnuje (využito např. v ClustalW2) Výstup Výstupem je sada sekvencí (případně s vloženými mezerami) Různé formáty, nejčastěji používán .aln soubor, ale též .fasta, aj. Mnoho programů sloužících pro zobrazení a/nebo editaci - Bioedit - JalView - CINEMA 2.1... - JavaShade Výstup - .aln soubor — Y F S li AT PQ P VQ PAP VP-------- — T AAP S SQG SG N rtsh-KĎfťia s*affl«í pik imspi Tvorba k-písmenných slov ze vstupní sekvence pro proteiny typicky 3-písmenných (v případě DNA 11 -písmen ných) Porovnání slov na základě substituční matice algoritmus BLAST hledá na základě vloženého skóre slova, která jsou podobná každému slovu v zadané sekvenci. Vyhovující slova jsou následně uspořádána. ■WaH3.«T Warf 4 WO • Prohledání databázových sekvencí Je hledána shoda s nalezenými vysoce podobnými slovy. • Rozšíření slov na segmenty D Přesné shody slov s databázovými sekvencemi jsou rozšiřovány oběma směry. To pokračuje dokud skóre pro tuto dvojici sekvencí je dostatečně vysoké. Novější verze BLASTu (BLAST2) má mj. níže nastavenu hladinu pro hledání podobných slov, coz rozšiřuje možnost nalezení vzdálenějších homologů. itRppgc:: r r d p r i c v ■l ■ -2 T T 1 t 1 -] FASTA algoritmus FastA algoritmus nejprve provádí rychlé prohledání pro nalezení odpovídajících sekvenci, následuje _ přesnější porovnání zadané sekvence s databázovou sekvencí. Na rozdíl od algoritmu BLAST jsou zde tolerovány mezery. Proces: Obě porovnávané sekvence tvoří horizontální a vertikální osu grafu. Následně jsou jednotlivá slova z jedné sekvence porovnávána se slovy sekvence druhé. Odpovídající páry pak vytvoří sadu bodů. Body na úhlopříčce signalizují významnou shodu (či podobnost} v daném úseku. Cílem je nalezení nejdelšího shodného úseku (úseku s nejvyšším skóre}. V dalších krocích jsou zahrnuty konzervativní změny pro nejlepší úseky z prvního prohledání. Program pak vyhledává možnost spojení více takových úseku (může mezi nimi být mezera, či jsou na různých diagonálách} a tyto spojené úseky jsou posouzeny z hlediska zadaných kriterií c g g c t t a Příklad porovnání sekvencí GGCTTTCGG a AACGGCTTACG M S A „programy" Za posledních 10 let vzniklo pres 50 MSA programových balíků (Wallace, I. M., O'Sulllvan, O., Hlgglns, D. G. and Notredame, C. (2006). M-Coffee: combining multiple sequence alignment methods with T-Coffee. Nucleic Acids Res. 34, 1692-1699.) Clustal W (Thompson et al., 1994) Clustal X (Thompson et al., 1997) Dialign2 (Morgenstern, 1999) T-Coffee (Notredame et al., 2000) MAFFT (Katoh etal., 2002) MUSCLE (Edgar, 2004) Kalign (Lassmann, 2005) 8 5/21/2012 Clustal http://www.ebi.ac.uk/clustalw/ • V současné době nejužívanější program • První verze 1988 Higgins.D.G. and Sharp,P.M. (1988) CLUSTAL: a package for performing multiple sequence alignment ona microcomputer. Gene, 73,237-244. • Dnes používané verze: Clustal W (Thompson et al., 1994) Clustal X (Jeanmougin et al., 1998) • Využívá progresivní alignment ClustalW: Jednotlivým sekvencím přiřazuje váhy (weight -W) podle četnosti zastoupení (čím více jsou si sekvence podobné, tím nižší mají váhu a naopak) a penalizuje přítomnost mezer v závislosti na jejich pozici (position-specific gap penalties) ClustalW2 - postup 1. Provedení pairwise alignmentů pro každou dvojici sekvencí a určení jejich podobnosti - v závislosti na množství neodpovídajících residuí a mezer 2. Sestavení příbuzenského stromu (similarity tree) Kombinace alignmentů (viz. 1.) v pořadí dle příbuznosti - od nejvíce podobných k nejméně příbuzným (viz. 2.). Jednou vložené mezery jsou zachovány. Clustal W/Clustal X SE Pod alignmentem je uváděn tzv. consensus -dohodnuté symboly vyjadřující „konzervovanosť každého sloupce: * - identické residuum ve všech sekvencích - silně konzervovaný sloupec - slabě konzervovaný sloupec IPPNTľE^AIFFANAAEQQIIIKLFIGDSQEPÄÄYHKLTTRDGER]:—ATLNSGNGKIRFE LPPNTÍ Fl a.ifyanaadrqi LPPNIÍ f( ívtalvnssapq: lpphikfgvtalthaandq: l ílf iddapepaatfvgnsedg\ R. i ívfvddnpkpaatfqgagtqdí N. i ) iyidddpkpaatfkgagaqdc N. —ftlnskggkirie n t qivn sgkgkvrw gtkvldsgngrvrvi MUSCLE (Multiple Sequence Comparison by Log-Expectation) http://www.drive5.com/muscle Rychlejší určení „vzdálenosti" dvou sekvencí Tzv. log-expectation skórovací funkce Refinement metodou restricted partitioning Vhodný i pro velký počet sekvencí (5000 seq po 350 bp za 7 min na PC - rok 2004) Postup: • Sestavení matice pro každou dvojici sekvencí, určení jejich „vzdálenosti" a sestavení matice vzdáleností (distance matrix) • Na základě distance matrix je sestaven první příbuzenský strom (treel) • Skládání sekvencí v pořadí dle treel od větví ke kmenu - v každém rozvětvení je vytvořen profil, který při dalším porovnávání nahrazuje původní sekvence - výsledkem je první MSA Algoritmus MUSCLE (podobne PRRP a MAFFT) Přepočítání vzdáleností sekvencí na základě vzniklého MSA1 - tvorba druhé distance matrix (D2) Na základě D2 sestaven vylepšený příbuzenský strom (tree2) Progresivní alignment (viz bod 3) na základě tree2 - vytvoření druhého MSA Refinement - rozdělení vzniklého stromu na dvě části a vytvoření MSA pro každou z nich. Pokud je výsledný alignment lepší, je zachován. Toto se opakuje do konvergence (žádná další změna nevede k lepšímu výsledku) nebo do určeného počtu kroků I'lpiTT í- Thft JÍV)" UJľTWTUnjlŕh a Ik-cr lit 1ÍMLL- Nim -Ji^rv Slip .....■■ >■. -i.. ■ *40%) - vysoká přesnost alignmentů • Bez homologie - nepoužitelné • Tzv. twilight zone - málo podobné sekvence (nižší než 20% homologie) = špatná (méně než 30%) přesnost alignmentů Řešení: nejčastěji využití znalosti strukturní podobnosti (2D nebo 3D), která se během evoluce zachovává více než sekvence AK. Rozšíření konzistentního modelu Template-based alignment metody - vytváří alignment na základě strukturní informace známých homologů jednotlivých sekvencí v PDB databázi nebo získava "profil" sekvence na základě homologních sekvencí (pomocí BLASTu) Výhoda: vyšší přesnost T-CoHm Primary Ll&wy Expresso • Je založeno na 3DCoffee Expresso je MSA server, který srovnává sekvence za užití strukturní informace. Po zadání sekvencí vyhledá v databázi struktur (PDB) pomocí BLASTu homology a použije je jako templáty pro následný alignment zadaných sekvencí pomocí metod MSA založených na struktuře (např. SAP, Fugue). Benchmark (srovnávací testy) BAMBASE - První vytvořená sada benchmarkových testů pro multiple alignment programy (Thompson et al., 1999) - byla vytvořena pomocí manuálně provedeného alignmentů Na základě srovnání 3D struktur byly vytvořeny další sety: HOMSTRAD [Mizuguchi etal., 1998]. OxBench [Raghava et al., 2003] PREFAB [Edgar, 2004] 10 5/21/2012 Existují i specificky zaměřené benchmarkové sety, např. IRMBASE [Subramanian et al, 2005] -náhodné (nepřiložitelné) sekvence s vloženými motivy. Slouží k testování metod pro lokální alignment BaliBASE - ukázka alignmentu Perrodou eř al. BMC Bioinformatics 2008 9:213 doi:10.1186/1471-2105-9-213 SELM instance irue positive false negalřve B false positive Zopakování / shrnutí Alignment - přiložení sekvencí (2 nebo více) na základě podobnosti Využití pro hledání příbuznosti sekvencí, tvorba profilů proteinových rodin, aj. Řada programů využívajících rozdílné přístupy - použití závisí na vstupních datech a účelu Nejčastěji používaný (ClustalW) neznamená nejpřesnější - každý program je kompromisem mezi přesností a rychlostí ^viLsí^. Každý alignment potřebuje lidskou kontrolu !!! Local alignment For two-sequence comparisons, there is the well-known Smith and Waterman (1981) algorithm. Here we use Lalign For multiple sequences, the Gibbs sampler (Lawrence et al., 1993) and Dialign2 (Morgenstern, 1999) are the main automatic methods. These programs often perform well when there is a clear block of ungapped alignment shared by all of the sequences. They perform poorly, however, on general sets of test cases when compared with global methods 11 5/21/2012 12