4/22/2009 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ů Struktura proteinů (NK) ADSQTSSNRAGEFSIPPNTDFRAIF FANAAEQQHIKLFIGDSQEPAAYHK LTTRDGPREATLNSGNGKIRFEVSV NGKPSATDARLAPINGKKSDGSPF TVNFGIVVSEDGHDSDYNDGIVVL QWPIG primární (sekvence) t I I I I f rag j glutamin | t t t t I threon tyr j tryptofan | h I t j selenocystein | Gly Leu Asp Asn Glu Gln Arg Lys Phe Ser Thr Tyr Trp ~Mer Cys Pro Sec G A V L i D N E Q R K H F S T Y W M C P U terciární Nukleové báze 05 CAo Ö&. Adenine Cytosine O Guanine Thymine Uracil adenin cytosin guanin thymin uracil A C G T U Třídění aminokyselin Aminokyseliny s podobnými vlastnostmi mohou plnit v proteinu stejné funkce - bývají vzájemně zastupitelné O OH ^^^^OH NH2 CHS NH2 cine Leucine •liplulit -^, small aromatic ^ ^^^1^ ^y^*'^ positive no n-pol ar / charged vpr?lw 1 4/22/2009 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 neopdoví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émeř 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 Vstupní data Sekvence AK (nt) v určitém formátu - dnes desítky formátů, mnohé obsahují krom sekvence i doplňující data Bližší např. http://emboss.sourceforge.net/docs/themes/SequenceFormats.html • FASTA formát >název popis dle vlastní volbyj SEKVENCESEKVENCESEKVENCESEKVENC ESEKVENCESEKVENCE 2 4/22/2009 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. • BLOSSUM (Blocks Substitution Matrix) - je odvozena z vysoce konzervovaných oblastí neobsahujících mezery — lepší pro lokální alignment. Je využívána v blastp, vhodná pro identifikaci neznámé nukleotidové sekvence. • GONNET -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 -5 -2 -1 0 -1 -2 -1 -1 -1 -2 -2 -2 -2 -2 -2 -2 -4 -3 -3 -2 -2 -3 -3 D E NQ H Matrice BLOSSUM vypadá analogicky, liší se hodnoty. DNA matice A 1 T -10000 1 G -10000 -10000 1 C -10000 -10000 -10000 1 AT 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 meióze (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 lili II II --GCGG-AGAGG-AA- 3 4/22/2009 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: ATCTTCAGTGTTTCCCCTGTTTTGCCC.ATTTAGTTCGCTC | iiiiiiiiiiiiiiiiiiiiiiiiii iiiiiiiiiiiii ATCTTCAGTGTTTCCCCTGTTTTGCCCGATTTAGTTCGCTC Dlouhá mezera: ATCTTCAGTGTTTCCCCTGTTTTGCCC....................ATTTAGTTCGCTC IIIIIIIIIIIIIIIIIIIIIIIIIII IIIIIIIIIIIII 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é. Multiple sequence alignment - MSA (mnohonásobné srovnání) 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í primerů (oligonukleotidů) pro PCR Metody MSA • Dynamické programování (dynamic programming) -rozšíření pairwise alignmentu • Progresivní alignment (progressive sequence alignment) - nejčastěji používaný k vytvoření alignmentu; využívá fylogenetické informace • Iterativní alignment (iterative sequence alignment) -odstraňuje problémy progresivního alignmentu pomocí opakování alignmentu pro podskupiny sekvencí 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í 4 4/22/2009 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 ( ( PAIIL:0.16435, RSIIL:0.13654) :0.03384, ( CVIIL:0.16563, BCLB:0.26800) :0.02264, ( ( BCLA:0.17899, BCLD:0.26633) :0.18717, BCLC:0.29707) :0.03484); DIST = percentage divergence (/100) Length = number of sites used in comparison 1 vs. 2 DIST = 0.6491; length = 114 1 vs. 3 DIST = 0.6842; length = 114 1 vs. 4 DIST = 0.9298; length = 114 1 vs. 5 DIST = 0.9035; length = 114 1 vs. 6 DIST = 0.9386; length = 114 1 vs. 7 DIST = 0.9825; length = 114 2 vs. 3 DIST = 0.3772; length = 114 2 vs. 4 DIST = 0.9123; length = 114 2 vs. 5 DIST = 0.8947; length = 114 2 vs. 6 DIST = 0.9123; length = 114 2 vs. 7 DIST = 0.9386; length = 114 3 vs. 4 DIST = 0.9123; length = 114 3 vs. 5 DIST = 0.9386; length = 114 3 vs. 6 DIST = 0.9298; length = 114 3 vs. 7 DIST = 0.9474; length = 114 4 vs. 5 DIST = 0.9211; length = 114 4 vs. 6 DIST = 0.9035; length = 114 4 vs. 7 DIST = 0.9649; length = 114 5 vs. 6 DIST = 0.9561; length = 114 5 vs. 7 DIST = 0.9211; length = 114 6 vs. 7 DIST = 0.9649; length = 114 Neighbor-joining Method Saitou, N. and Nei, M. (1987) The Neighbor-joining Method: A New Method for Reconstructing Phylogenetic Trees. Mol. Biol. Evol., 4(4), 406-425 This is an UNROOTED tree Numbers in parentheses are branch lengths Cycle 1 = SEQ: 2 ( 0.17807) joins SEQ: 3 ( 0.19912) Cycle 2 = SEQ: 1 ( 0.34101) joins Node: 2 ( 0.13706) Cycle 3 = SEQ: 5 ( 0.44298) joins SEQ: 7 ( 0.47807) Cycle 4 = SEQ: 4 ( 0.44518) joins SEQ: 6 ( 0.45833) Cycle 5 (Last cycle, trichotomy): Node: 1 ( 0.12171) joins Node: 4 ( 0.01864) joins Node: 5 ( 0.02083) .nj soubor .dst soubor 7 PAIIL 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). 5 4/22/2009 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 sekvenci 2) tvorba párových alignmentů postupně podle příbuznosti (topologie guide tree) • Dnes obsahuje často iterativní smyčku 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í. 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 CLUSTAL 2.0.10 multiple sequence alignment PAIIL RSIIL CVIIL BCLB BCLC BCLA BCLD CVIIL BCLB BCLC BCLA PAIIL RSIIL CVIIL BCLB BCLC ---LVEKLPQYDVFVDIATIPYSFDVGSWQNKVKTDAAGEVVACTVTWAGAPGVLPGAAA AIATNQGVVADGCFTYSSKVPESTGRMPFTLVATIDVGSGVTFVKGQWKSVRGSAMHIDS LRETALALRAEVSVLFIRFALKDAGIVAPIELEVRDAATAVPDADDLLHPSCRPLKDHYW -----------------------------------------------------AQQGVFT KFGVGAVVN----------------YFSKATPQPVQPAPVP--------TGGGERDGIFT YASLSAIWG----------------TAAPSSQGSGNQGAETGGTGAGNIGGGGERDGTFN -------------------------------------ADSQT---------SSNRAGEFS LPANTRFGVTAFANSSGTQTVNVLVNNETA— ATFSGQSTNNAVIGTQVLNSGSSGKVQV LPANTSFGVTAFANAANTQTIQVLVDNVVK— ATFTGSGTSDKLLGSQVLNSGS-GAIKI LPARINFGVTVLVNSAATQHVEIFVDNEPR— AAFSGVGTGDNNLGTKVINSGS-GNVRV LPPNIAFGVTALVNSSAPQTIEVFVDDNPKPAATFQGAGTQDANLNTQIVNSGK-GKVRV LPPHIKFGVTALTHAANDQTIDIYIDDDPKPAATFKGAGAQDQNLGTKVLDSGN-GRVRV IPPNTDFRAIFFANAAEQQHIKLFIGDSQEPAAYHKLTTRDGPRE — ATLNSGN-GKIRF Programové balíky • Existují programy pro pairwise alignment i pro MSA • Využívají lokální nebo globální alignment nebo přip. kombinaci obou • Neexistuje univerzální „nejlepší" program - záleží na konkrétním použití PAIIL RSIIL BCLA 6 4/22/2009 Pairwise alignment „programy" Oblasti použití: •Přímé porovnání dvou sekvencí • Vyhledávání podobných sekvencí v databázích Needle & Water •vytvořeny 1970 Needleman S.B. and Wunsch C.D. (1970) A general method applicable to the search for similarities in the amino acid sequence of two proteins. Journal of Molecular Biology 48: 443-453. • využívají dynamic programming, • umožňují vložení mezer Needle -globální pairwise alignment, Needleman-Wunsch algoritmus Water - lokální pairwise alignment, Smith-Waterman algoritmus Globálně podobné sekvence Needle PA-IIL 1 ATQGVFTLPANTRFGVTAFANSSGTQTVNVLVNNETAATFSGQSTNNAVI 50 1 AQQGVFTLPANTSFGVTAFANAANTQTIQVLVDNVVKATFTGSGTSDKLL 50 51 GTQVLNSGSSGKVQVQVSVNGRPSDLVSAQVILTNELNFALVGSEDGTDN 100 RS-IIL 100 DYNDGIAVLNWPLG 113 Water PA-IIL 1 ATQGVFTLPANTRFGVTAFANS SGTQTVNVLVNNETAATFSGQSTNNAVI 50 | .||||||||||.||||||||::.|||:.|||:|...|||:|..|::.:: 1 AQQGVFTLPANTSFGVTAFANAANTQTIQVLVDNVVKATFTGSGTSDKLL 50 51 GTQVLNSGSSGKVQVQVSVNGRPSDLVSAQVILTNELNFALVGSEDGTDN 100 |:|||||| ||.:::||||||:||||||.|.||.|:||||:||||||||| 51 GSQVLNSG-SGAIKIQVSVNGKPSDLVSNQTILANKLNFAMVGSEDGTDN 99 101 DYNDAVVVINWPLG 114 ||||.:.|:||||| 100 DYNDGIAVLNWPLG 113 Lokálně podobné sekvence Needlí PA-IIL BCLB PA-IIL BCLB PA-IIL 1 SQPFTHDDLYALLQLAGNDATAVQANGDQAVLDRMRQFMTAQLVEKLPQY 50 1 -------------------------------------------------- 0 51 DVFVDIATIPYSFDVGSWQNKVKTDAAGEVVACTVTWAGAPGVLPGAAAK 100 1----------------------------ATQGVFTLPANTRFGVTAFANS 22 ...|:||||.|..|||||..|| 101 FGVGAVVNYFSKATPQPVQPAPVPTGGGERDGIFTLPPNIAFGVTALVNS 150 L 23 SGTQTVNVLV—NNETAATFSGQ STNNAVIGTQVLNSGSSG KVQVQVSVN 70 |..||:.|.| |.:.||||.|..|.:|.:.||::||| .|||:|.|:.| 151 SAPQTIEVFVDDNPKPAATFQGAGTQDANLNTQIVNSG-KGKVRVVVTAN 199 L 71 GRPSDLVSAQVILTNELNFALVGSEDGTDNDYNDAVVVINWPLG 114 |:||.:.|.||.:..:..|.|||||||.|.||||.:.::||||| 200 GKPSKIGSRQVDIFKKTYFGLVGSEDGGDGDYNDGIAILNWPLG 243 Water PA-IIL 4 GVFTLPANTRFGVTAFANSSGTQTVNVLV—NNETAATFS GQS TNNAVIG |:||||.|..|||||..|||..||:.|.| |.:.||||.|..|.:|.:. BCLB 132 GIFTLPPNIAFGVTALVNSSAPQTIEVFVDDNPKPAATFQGAGTQDANLN PA-IIL 52 TQVLNSGSSGKVQVQVSVNGRPSDLVSAQVILTNELNFALVGSEDGTDND ||::||| .|||:|.|:.||:||.:.|.||.:..:..|.|||||||.|.| BCLB 182 TQIVNSG-KGKVRVVVTANGKPSKIGSRQVDIFKKTYFGLVGSEDGGDGD PA-IIL 102 YNDAVVVINWPLG 114 |||.:.::||||| BCLB 231 YNDGIAILNWPLG 243 PA-IIL 51 GSQVLNSG-SGAIKIQVSVNGKPSDLVSNQTILANKLNFAMVGSEDGTDN 101 DYNDAVVVINWPLG 114 99 PA-IIL BCLB RS-IIL PA-IIL 101 PA-IIL 230 RS-IIL BLAST algoritmus Heuristický algoritmus jehož základem je hledání slov (několikapísmenných sekvencí), s dostatečnou podobností (poskytují dostatečně vysoké skóre v substituční matici) • Tvorba k-písmenných slov ze vstupní sekvence _„ pro proteiny typicky 3-písmenných (v případě DNA 11-písmenný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. j^r r i>í_*.=-:-íí ■ i pqc 4mJ cef Waid í lid • Prohledání databázových sekvencí Je hledána shoda s nalezenými vysoce podobnými slovy. it p P Q G L F • 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é. cD P v K G v v ►S 1.1. 1 IILd-i r. \.I3K,! -> 7 1 t ] -1 ' 'Uff 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ů. 7 4/22/2009 FASTA algoritmus FastA algoritmus nejprve provádí rychlé prohledání pro nalezení odpovídajících sekvencí, 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řícce 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 úseků (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í aacggcttacg Příklad porovnání sekvencí GGCTTTCGG a AACGGCTTACG 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 on a 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) 3. Kombinace alignmentů (viz. 1.) v pořadí dle přibuznosti - od nejvíce podobných k nejméně příbuzným (viz. 2.). Jednou vložené mezery jsou zachovány. Clustal W/Clustal X Pod alignmentem je uváděn tzv. consensus -dohodnuté symboly vyjadřující „konzervovanost" každého sloupce: * - identické residuum ve všech sekvencích : - silně konzervovaný sloupec . - slabě konzervovaný sloupec ippntdFRaiffanaaeqqhiklfigdsqepaayhklttrdgpre—atlnsgngkirfe lppntafkaifyanaadrqilílfiddapepaatfvgnsedgvr,—ftlnskggkirie lippniafgvtalvnssapqtievfvddnpkpaatfqgagtqdanjntqivnsgkgkvrvv lpphikfgvtalthaandqtidiyidddpkpaatfkgagaqdqnjgtkvldsgngrvrvi 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 (tree1) • Skládání sekvencí v pořadí dle tree1 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 8 4/22/2009 Algoritmus MUSCLE (podobne PRRP a MAFFT) Přepočítáni vzdálenosti sekvenci na základě vzniklého MSA1 - tvorba druhé distance matrix (D2) Na základě D2 sestaven vylepšený príbuzenský strom (tree2) Progresivní alignment (viz bod 3) na základě tree2 - vytvorení druhého MSA Refinement - rozděleni vzniklého stromu na dvě části a vytvorení 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ů ^ ;;;; -H v -ŕ Hpinr L Ww* di^nan sulanlim tír ft>*. H |hc MUK.LĽ itcviilliii Ihirc jn.' threí mia u^n: Supe I lukjíl pofímiveL Sltfe impcvuJ pr^reiiivŕk ind ílapi J ikIíktkmi. A iHiláple lignrrKW i Další skórovací schémata (scoring schemes) pro pairwise alignment Algoritmy založené na matici (matrix-based algorithms) -např. ClustalW, MUSCLE; pomocí substituční matice je příslušné dvojici (AK) přiřazena hodnota. Rozhoduje pouze identita těchto dvou AK, případně jejich nejbližší okolí (viz. např. BLAST) Schémata založená na konzistenci (consistency-based schemes) - poprvé v T-Coffee, dále v PCMA, ProbCons, MUMMALS, MAFFT, aj. Vychází z nejlepších možných alignmentů každé dvojice sekvencí. Využívá často i data z různých zdrojů (např. strukturní informace). Cílem je dosáhnout maximální konzistence (vnitřní shody). Výsledek je přesnější, ale výpočet je časově náročnější. 4. 5. 6. 7. T-Coffee http://www.tcoffee.org/Projects_ho me_page/t_coffee_home_page.í^_^ (Tree-based Consistency Objective Function for alignment Evaluatron) Pomalejší ale výrazně přesnější než ClustalW Je schopen kombinovat data z více předchozích alignmentů, které mohly být vytvořeny různými postupy (lokální, globální, strukturní podobnost,...) Hlavním rozdílem oproti tradičním metodám progresivního alignmentů je použití pozičně specifického skórovacího schématu (extended library) namísto substituční matice. T-Coffee Provedení pairwise alignmentů pro všechny dvojice sekvencí pomocí globálního a pomocí lokálního alignmentu (dve primární knihovny). Jednotlivým pairwise alignmentům je přiřazena váha podle poměru počtu identických residui k celkovému počtu residuí. Kombinace obou knihoven. Pokud je rozdíl v globalním a lokálním alignmentu, jsou zachovány oba s příslušnou váhou. Vzniká pozičně specifická matice (extended library), která je dále použita pro vlastní progresivní alignment. 1) 2) 3) Zlepšení přesnosti -strukturní informace • Sekvence s vyšší homologií (>40%) - vysoká přesnost alignmentu • Bez homologie - nepoužitelné • Tzv. twilight zone - málo podobné sekvence (nižší než 20% homologie) = špatná (méně než 30%) přesnost alignmentu Řešení: nejčastěji využití znalosti strukturní podobnosti (2D nebo 3D), která se behem 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 9 4/22/2009 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) BAliBASE - První vytvořená sada benchmarkových testů pro multiple alignment programy (Thompson et al., 1999) - byla vytvořena pomocí manuálně provedeného alignmentu Na základě srovnání 3D struktur byly vytvořeny další sety: HOMSTRAD [Mizuguchi et al., 1998]. OxBench [Raghava et al., 2003] PREFAB [Edgar, 2004] 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 et al. BMC Bioinformatics 2008 9:213 doi:10.1186/1471-2105-9-213 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 T Nejčastěji používaný (ClustalW) neznamená nejpřesnější - každý program je kompromisem mezi přesností a rychlostí ▼ 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, l999) 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 10 4/22/2009 11