Chemoinformatika a bioinformatika 8. Sequence alignment Mgr. Josef Houser houser@mail.muni.cz Zobrazit obrázek v plné velikosti HappyComputer Osnova •1. Struktura biomakromolekul – sekvence •2. Alignment a jeho typy •3. Užívané algoritmy •4. Multiple sequence alignment •5. Programové balíky • Biomakromolekuly Biomolekuly jsou přirozenou součástí živých organismů. Velké molekuly. Typické malé molekuly jsou tvořeny několika atomy až několika sty atomů. Makromolekuly tvoří tisíce až miliony atomů. Základní stavební jednotky hmoty. Jsou tvořeny atomy, které navzájem spojují kovalentní vazby. Biomolekuly Makromolekuly Biomakromolekuly Hormony Vitamíny Přírodní barviva Alkaloidy Cukry Plasty Polysaccharidy Nukleové kyseliny Proteiny Složení biomakromolekul •Vznikají spojováním velkého množství několika málo typů podjednotek Makromolekula Stavební jednotky Typ vazby Schéma Protein Aminokyseliny Peptidová Nukleová kyselina Nukleotidy Esterová Polysacharid Monosacharidy Glykosidická Aminokyseliny amino acids amino acids glycin alanin valin leucin izoleucin asparagová kys. asparagin glutamová kys. glutamin arginin lysin histidin fenylalanin serin threonin tyrozin tryptofan methionin cystein prolin selenocystein pyrolysin Gly Ala Val Leu Ile Asp Asn Glu Gln Arg Lys His Phe Ser Thr Tyr Trp Met Cys Pro Sec Pyr G A V L I D N E Q R K H F S T Y W M C P U O Třídění aminokyselin •Aminokyseliny s podobnými vlastnostmi mohou plnit v proteinu stejné funkce – bývají vzájemně zastupitelné Courtesy of http://prowl.rockefeller.edu Nukleové báze adenin cytosin guanin thymin uracil A C G T U Nukleová báze Adenin Nukleotid Adenosintrifosfát ATP Nukleotid Adenosinmonofosfát AMP Nukleosid Adenosin Polysacharidy •Komplikované sekvence – alignment se neprovádí Polymer Protein Nukleová kyselina Polysacharid Počet druhů základních stavebních jednotek 20 (22) 4 (DNA) 4 (RNA) desítky Počet typů vzájemných vazeb 1 1 2 x 4 (pro hexosu) Struktura proteinů (NK) primární (sekvence) sekundární terciární kvartérní ADSQTSSNRAGEFSIPPNTDFRAIFFANAAEQQHIKLFIGDSQEPAAYHKLTTRDGPREATLNSGNGKIRFEVSVNGKPSATDARLAPINGKKSDGSPF TVNFGIVVSEDGHDSDYNDGIVVLQWPIG PAIIL monomer PAIIL tetramer 5de36d73376b8521 Alignment •Srovnání (přiložení) dvou či více sekvencí (aminokyselinových, nukleotidových) na základě jejich vzájemné podobnosti. • http://www.getodd.com/duck/largeimg/faceoff1450.jpg Význam alignmentu •Identifikace sekvence v databázi •Hledání podobných sekvencí v databázi •Detekce mutací •Hledání konzervovaných částí sekvence •Odhalování příbuzenských vztahů •Předpověď funkce makromolekuly •Předpověď vyšších struktur • Typy alignmentu •Pairwise alignment – dvě sekvence • • • • •Multiple sequence alignment – více sekvencí • WLAKALKYLMETAQASSISTELARHHPRAVDAKRKSEMKRKTAMWLAKALKYLMETAQASSISTELARHHPRAVDAKRKSEMKRKTAM WLAKALKYLMETAQASSISTELARHHPRAVDAKRKSEMKRKTAMWLAKALKYLMETAQASSISTELARHHPRAVDAKRKSEMKRKTAM WLAKALKYLMETAQASSISTELARHHPRAVDAKRKSEMKRKTAMWLAKALKYLMETAQASSISTELARHHPRAVDAKRKSEMKRKTAM ... WLAKALKYLMETAQASSISTELARHHPRAVDAKRKSEMKRKTAMWLAKALKYLMETAQASSISTELARHHPRAVDAKRKSEMKRKTAM WLAKALKYLMETAQASSISTELARHHPRAVDAKRKSEMKRKTAMWLAKALKYLMETAQASSISTELARHHPRAVDAKRKSEMKRKTAM WLAKALKYLMETAQASSISTELARHHPRAVDAKRKSEMKRKTAMWLAKALKYLMETAQASSISTELARHHPRAVDAKRKSEMKRKTAM WLAKALKYLMETAQASSISTELARHHPRAVDAKRKSEMKRKTAMWLAKALKYLMETAQASSISTELARHHPRAVDAKRKSEMKRKTAM WLAKALKYLMETAQASSISTELARHHPRAVDAKRKSEMKRKTAMWLAKALKYLMETAQASSISTELARHHPRAVDAKRKSEMKRKTAM 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 příliš neodpoví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(Vpopis dle vlastní volby)¿ SEKVENCESEKVENCESEKVENCESEKVEN(¿)CESEKVENCESEKVENCE¿ • • POVINNÉ VOLITELNÉ 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 dvojicím aminokyselin v závislosti na jejich vzájemné „zastupitelnosti“ – pravděpodobnosti substituce matice_small 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 mutací 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, vhodná pro identifikaci neznámé nukleotidové sekvence. BLOSUM matrices vysokými čísly je dobrá pro porovnání vysoce příbuzných sekvencí, zatímco nízké pro relativně vzdálené podobnosti •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 •C 12 •G -3 5 •P -3 -1 6 •S 0 1 1 1 •A -2 1 1 1 2 •T -2 0 0 1 1 3 •D -5 1 -1 0 0 0 4 •E -5 0 -1 0 0 0 3 4 •N -4 0 -1 1 0 0 2 1 2 •Q -5 -1 0 -1 0 -1 2 2 1 4 •H -3 -2 0 -1 -1 -1 1 1 2 3 6 •K -5 -2 -1 0 -1 0 0 0 1 1 0 5 •R -4 -3 0 0 -2 -1 -1 -1 0 1 2 3 6 •V -2 -1 -1 -1 0 0 -2 -2 -2 -2 -2 -2 -2 4 •M -5 -3 -2 -2 -1 -1 -3 -2 0 -1 -2 0 0 2 6 •I -2 -3 -2 -1 -1 0 -2 -2 -2 -2 -2 -2 -2 4 2 5 •L -6 -4 -3 -3 -2 -2 -4 -3 -3 -2 -2 -3 -3 2 4 2 6 •F -4 -5 -5 -3 -4 -3 -6 -5 -4 -5 -2 -5 -4 -1 0 1 2 9 •Y 0 -5 -5 -3 -3 -3 -4 -4 -2 -4 0 -4 -5 -2 -2 -1 -1 7 10 •W -8 -7 -6 -2 -6 -5 -7 -7 -4 -5 -3 -3 2 -6 -4 -5 -2 0 0 17 • C G P S A T D E N Q H K R V M I L F Y W Matrice BLOSSUM vypadá analogicky, liší se hodnoty. Izoleucin Valin Matice PAM 250 •C 12 •G -3 5 •P -3 -1 6 •S 0 1 1 1 •A -2 1 1 1 2 •T -2 0 0 1 1 3 •D -5 1 -1 0 0 0 4 •E -5 0 -1 0 0 0 3 4 •N -4 0 -1 1 0 0 2 1 2 •Q -5 -1 0 -1 0 -1 2 2 1 4 •H -3 -2 0 -1 -1 -1 1 1 2 3 6 •K -5 -2 -1 0 -1 0 0 0 1 1 0 5 •R -4 -3 0 0 -2 -1 -1 -1 0 1 2 3 6 •V -2 -1 -1 -1 0 0 -2 -2 -2 -2 -2 -2 -2 4 •M -5 -3 -2 -2 -1 -1 -3 -2 0 -1 -2 0 0 2 6 •I -2 -3 -2 -1 -1 0 -2 -2 -2 -2 -2 -2 -2 4 2 5 •L -6 -4 -3 -3 -2 -2 -4 -3 -3 -2 -2 -3 -3 2 4 2 6 •F -4 -5 -5 -3 -4 -3 -6 -5 -4 -5 -2 -5 -4 -1 0 1 2 9 •Y 0 -5 -5 -3 -3 -3 -4 -4 -2 -4 0 -4 -5 -2 -2 -1 -1 7 10 •W -8 -7 -6 -2 -6 -5 -7 -7 -4 -5 -3 -3 2 -6 -4 -5 -2 0 0 17 • C G P S A T D E N Q H K R V M I L F Y W Izoleucin Valin Glycin Matice BLOSUM 62 http://upload.wikimedia.org/wikipedia/commons/5/52/BLOSUM62.gif GONNETova matice DNA matice • A 1 • T -10000 1 • G -10000 -10000 1 • C -10000 -10000 -10000 1 • 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 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. CTGCGGG---GGTAAT |||| || || --GCGG-AGAGG-AA- Krátká mezera: ATCTTCAGTGTTTCCCCTGTTTTGCCC-ATTTAGTTCGCTC ||||||||||||||||||||||||||| ||||||||||||| ATCTTCAGTGTTTCCCCTGTTTTGCCCGATTTAGTTCGCTC Dlouhá mezera: ATCTTCAGTGTTTCCCCTGTTTTGCCC--------------------ATTTAGTTCGCTC ||||||||||||||||||||||||||| ||||||||||||| ATCTTCAGTGTTTCCCCTGTTTTGCCCGCCCCCCCCCCCCCCCCCCCATTTAGTTCGCTC •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“, často 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). 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é. Score_Calculation 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 Například, celkové pozitivní skóre na úrovni jednotlivých aa A A B B C C D D - - E E F A A - - - - D D K K K E F G G 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. A A B B C C D D - - E E F A A - - - - D D K K K E F G G -10-1-1-1 -10-1 = -24 Celkové skóre 32 – 24 = 8 Multiple sequence alignment - MSA (mnohonásobné přiložení) •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 sekvencí 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 - 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 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í Computer Recovery 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šína 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 alignmentů 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 alignmentů. 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); .nj soubor •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) 1 4 3 2 6 5 7 .ph soubor BCL phylogram ( ( ( PAIIL:0.16435, RSIIL:0.13654) :0.03384, ( ( BCLA:0.17899, BCLD:0.26633) :0.18717, BCLC:0.29707) :0.03484) :0.02264, CVIIL:0.16563, BCLB:0.26800); .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). Phylogram a cladogram BCL rectangle cladogram BCL phylogram Phylogram Cladogram Phylogram a cladogram BCL rectangle cladogram BCL phylogram Phylogram Cladogram http://upload.wikimedia.org/wikipedia/commons/thumb/7/70/Phylogenetic_tree.svg/450px-Phylogenetic_t ree.svg.png File:Tree of life by Haeckel.jpg 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 ---LVEKLPQYDVFVDIATIPYSFDVGSWQNKVKTDAAGEVVACTVTWAGAPGVLPGAAA •BCLC AIATNQGVVADGCFTYSSKVPESTGRMPFTLVATIDVGSGVTFVKGQWKSVRGSAMHIDS •BCLA ------------------------------------------------------------ •BCLD LRETALALRAEVSVLFIRFALKDAGIVAPIELEVRDAATAVPDADDLLHPSCRPLKDHYW • • •PAIIL -----------------------------------------------------ATQGVFT •RSIIL -----------------------------------------------------AQQGVFT •CVIIL -----------------------------------------------------AQQGVFT •BCLB KFGVGAVVN----------------YFSKATPQPVQPAPVP--------TGGGERDGIFT •BCLC YASLSAIWG----------------TAAPSSQGSGNQGAETGGTGAGNIGGGGERDGTFN •BCLA -------------------------------------ADSQT---------SSNRAGEFS •BCLD RSDVLAAGATTCTADFAVCDRDGTVSGYFRWETSIEIAGSQPDTKQPGFKPSSDRNGNFS • * *. • •PAIIL LPANTRFGVTAFANSSGTQTVNVLVNNETA--ATFSGQSTNNAVIGTQVLNSGSSGKVQV •RSIIL LPANTSFGVTAFANAANTQTIQVLVDNVVK--ATFTGSGTSDKLLGSQVLNSGS-GAIKI •CVIIL LPARINFGVTVLVNSAATQHVEIFVDNEPR--AAFSGVGTGDNNLGTKVINSGS-GNVRV •BCLB LPPNIAFGVTALVNSSAPQTIEVFVDDNPKPAATFQGAGTQDANLNTQIVNSGK-GKVRV •BCLC LPPHIKFGVTALTHAANDQTIDIYIDDDPKPAATFKGAGAQDQNLGTKVLDSGN-GRVRV •BCLA IPPNTDFRAIFFANAAEQQHIKLFIGDSQEPAAYHKLTTRDGPRE--ATLNSGN-GKIRF •BCLD LPPNTAFKAIFYANAADRQDLKLFIDDAPEPAATFVGNSEDGVRL--FTLNSKG-GKIRI • :*.. * . .::: * :.: :.: * . . ::* * ::. Programové balíky •Existují programy pro pairwise alignment i pro MSA • •Využívají lokální nebo globální alignment nebo příp. kombinaci obou • •Neexistuje univerzální „nejlepší“ program – záleží na konkrétním použití [Package stamped 'FRAGILE', 'BIRDS', 'PLANTS', 'OCEANS', etc.] 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í dynamické programování •umožňují vložení mezer • •Needle – globální pairwise alignment, Needleman-Wunsch algoritmus •Water – lokální pairwise alignment, Smith-Waterman algoritmus emboss •A 1 MPTEFLYTSKIAAISWAATGGRQQRVYFQDLNGKIREAQRGGDNPWTGGS 50 B 1 -------------------------------------------------- 0 A 51 SQNVIGEAKLFSPLAAVTWKSAQGIQIRVYCVNKDNILSEFVYDGSKWIT 100 B 1 -------------------------------------------------- 0 A 101 GQLGSVGVKVGSNSKLAALQWGGSESAPPNIRVYYQKSNGSGSSIHEYVW 150 B 1 -------------------------------------------------- 0 A 151 SGKWTAGASFGSTVPGTGIGATAIGPGRLRIYYQATDNKIREHCWDSNSW 200 ..||..|:|:| |. :|: |.|..|||.|.|:|.::| B 1 --MQTAAISWGTT-PS------------IRV-YTANGNKITERCYDGSNW 34 A 201 YVGGFSASASAGVSIAAISW--GSTPNIRVYWQKGREELYEAAYGGSWNT 248 |.|.|: .||.:::|..| ||..:|||| B 35 YTGAFN---QAGDNVSATCWLSGSAVHIRVY------------------- 62 A 249 PGQIKDASRPTPSLPDTFIAANSSGNIDISVFFQASGVSLQQWQWISGKG 298 ..||.|..:|.| .|.| B 63 ---------------------------------ATSGGSTTEWCW-DGDG 78 A 299 WSIGAVVPTGTPAGW 313 |:.||. ||. B 79 WTRGAY--TGL---- 87 Globální alignment - Needle Lokální alignment - Water •A 155 TAGASFGSTVPGTGIGATAIGPGRLRIYYQATDNKIREHCWDSNSWYVGG 204 ||..|:|:| |. :|: |.|..|||.|.|:|.::||.|. B 3 TAAISWGTT------------PS-IRV-YTANGNKITERCYDGSNWYTGA 38 A 205 FSASASAGVSIAAISW--GSTPNIRVYWQKGREELYEAAYGGSWNTPGQI 252 |: .||.:::|..| ||..:|||| B 39 FN---QAGDNVSATCWLSGSAVHIRVY----------------------- 62 A 253 KDASRPTPSLPDTFIAANSSGNIDISVFFQASGVSLQQWQWISGKGWSIG 302 ..||.|..:|.| .|.||:.| B 63 -----------------------------ATSGGSTTEWCW-DGDGWTRG 82 A 303 A 303 | B 83 A 83 Lokálně podobné sekvence •Needle •1 -------------------------------ADSQTSSN----------- 8 • ..||.|.| •101 TFVKGQWKSVRGSAMHIDSYASLSAIWGTAAPSSQGSGNQGAETGGTGAG 150 • •9 -------RAGEFSIPPNTDFRAIFFANAAEQQHIKLFIGDSQEPAAYHK- 50 • |.|.|::||:..|......:||..|.|.::|.|..:|||..| •151 NIGGGGERDGTFNLPPHIKFGVTALTHAANDQTIDIYIDDDPKPAATFKG 200 • 51-------LTTRDGPREATLNSGNGKIRFEVSVNGKPSATDARLAPINGKK 93 • |.|: .|:||||::|..|..||:||...:|...| .|| •201 AGAQDQNLGTK------VLDSGNGRVRVIVMANGRPSRLGSRQVDI-FKK 243 • •94 SDGSPFTVNFGIVVSEDGHDSDYNDGIVVLQWPIG 128 • | .|||:.||||.|.|||||||.|.||:| •244 S-------YFGIIGSEDGADDDYNDGIVFLNWPLG 271 • •Water •9 RAGEFSIPPNTDFRAIFFANAAEQQHIKLFIGDSQEPAAYHK-------- 50 • |.|.|::||:..|......:||..|.|.::|.|..:|||..| •158 RDGTFNLPPHIKFGVTALTHAANDQTIDIYIDDDPKPAATFKGAGAQDQN 207 • •51 LTTRDGPREATLNSGNGKIRFEVSVNGKPSATDARLAPINGKKSDGSPFT 100 • |.|: .|:||||::|..|..||:||...:|...| .||| •208 LGTK------VLDSGNGRVRVIVMANGRPSRLGSRQVDI-FKKS------ 244 • •101 VNFGIVVSEDGHDSDYNDGIVVLQWPIG 128 • .|||:.||||.|.|||||||.|.||:| •245 -YFGIIGSEDGADDDYNDGIVFLNWPLG 271 • Globálně podobné sekvence •Needle •PA-IIL 1 ATQGVFTLPANTRFGVTAFANSSGTQTVNVLVNNETAATFSGQSTNNAVI 50 |.||||||||||.||||||||::.|||:.|||:|...|||:|..|::.:: •RS-IIL 1 AQQGVFTLPANTSFGVTAFANAANTQTIQVLVDNVVKATFTGSGTSDKLL 50 •PA-IIL 51 GTQVLNSGSSGKVQVQVSVNGRPSDLVSAQVILTNELNFALVGSEDGTDN 100 |:|||||| ||.:::||||||:||||||.|.||.|:||||:||||||||| •RS-IIL 51 GSQVLNSG-SGAIKIQVSVNGKPSDLVSNQTILANKLNFAMVGSEDGTDN 99 •PA-IIL 101 DYNDAVVVINWPLG 114 • ||||.:.|:||||| •RS-IIL 100 DYNDGIAVLNWPLG 113 • •Water •PA-IIL 1 ATQGVFTLPANTRFGVTAFANSSGTQTVNVLVNNETAATFSGQSTNNAVI 50 • |.||||||||||.||||||||::.|||:.|||:|...|||:|..|::.:: •RS-IIL 1 AQQGVFTLPANTSFGVTAFANAANTQTIQVLVDNVVKATFTGSGTSDKLL 50 •PA-IIL 51 GTQVLNSGSSGKVQVQVSVNGRPSDLVSAQVILTNELNFALVGSEDGTDN 100 • |:|||||| ||.:::||||||:||||||.|.||.|:||||:||||||||| •RS-IIL 51 GSQVLNSG-SGAIKIQVSVNGKPSDLVSNQTILANKLNFAMVGSEDGTDN 99 •PA-IIL 101 DYNDAVVVINWPLG 114 • ||||.:.|:||||| •RS-IIL 100 DYNDGIAVLNWPLG 113 BLAST algoritmus •BLAST (Basic Local Alignment Search Tool) • •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) • BLAST_algorithm Extension_process •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. • •Prohledání databázových sekvencí Je hledána shoda s nalezenými vysoce podobnými slovy. • •Rozšíření slov na segmenty 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, což rozšiřuje možnost nalezení vzdálenějších homologů. Query_word pic2 FASTA algoritmus •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). 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í. Příklad porovnání sekvencí GGCTTTCGG a AACGGCTTACG MSA „programy“ •Za posledních 15 let vzniklo pres 50 MSA programových balíků (Wallace, I. M., O'Sullivan, O., Higgins, 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 et al., 2002) •MUSCLE (Edgar, 2004) •Kalign (Lassmann, 2005) •… 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. 2.Sestavení příbuzenského stromu (similarity tree) 3. 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 LPPNTAFKAIFYANAADRQDLKLFIDDAPEPAATFVGNSEDGVRL--FTLNSKGGKIRIE LPPNIAFGVTALVNSSAPQTIEVFVDDNPKPAATFQGAGTQDANLNTQIVNSGKGKVRVV LPPHIKFGVTALTHAANDQTIDIYIDDDPKPAATFKGAGAQDQNLGTKVLDSGNGRVRVI :**: * . .::: * :.:::.* :*** . :. . ::* *::*. clustalX 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) Muscle-774345 Postup: 1.Sestavení matice pro každou dvojici sekvencí, určení jejich „vzdálenosti“ a sestavení matice vzdáleností (distance matrix) 2.Na základě distance matrix je sestaven první příbuzenský strom (tree1) 3.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 Algoritmus MUSCLE (podobne PRRP a MAFFT) 4.Přepočítání vzdáleností sekvencí na základě vzniklého MSA1 – tvorba druhé distance matrix (D2) 5.Na základě D2 sestaven vylepšený příbuzenský strom (tree2) 6.Progresivní alignment (viz bod 3) na základě tree2 – vytvoření druhého MSA 7. 7.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ů 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ší. T-Coffee http://www.tcoffee.org (Tree-based Consistency Objective Function for alignment Evaluation) •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 alignmentu je použití pozičně specifického skórovacího schématu (extended library) namísto substituční matice. cup_of_coffee T-Coffee 1)Provedení pairwise alignmentů pro všechny dvojice sekvencí pomocí globálního a pomocí lokálního alignmentu (dvě primární knihovny). 2)Jednotlivým pairwise alignmentům je přiřazena váha podle poměru počtu identických residuí k celkovému počtu residuí. 3)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. • 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. •Template-based alignment metody – využití známých homologních proteinů (srovnání dle jejich struktury nebo tvorba profilu homologních sekvencí) • •Výhoda: vyšší přesnost • Rozšíření konzistentního modelu Expresso •Je založeno na T-Coffee •Expresso: 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). 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í ▼Každý alignment potřebuje lidskou kontrolu !!! Zobrazit obrázek v plné velikosti image011 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 • Benchmark (srovnávací testy) BaliBASE – ukázka alignmentu •Perrodou et al. BMC Bioinformatics 2008 9:213 doi:10.1186/1471-2105-9-213 1471-2105-9-213-2-l 1471-2105-9-213-2-l Blackshield 2006 oznacil ProbCons jako nejlepsi na zaklade 6 benchmarkovych testu 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 •