Chemoinformatika a bioinformatika Sequence alignment 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. Biomakromolekuly 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á or 0 ' ^nh "y ^nh 0 r Nukleová kyselina Nukleotidy Esterová p u\ / // V>H V 0 °h q// oh Polysacharid Monosacharidy Glykosidická oh oh ^^Bo^A.o-r^o. oh Roy» V-oh Aminokyseliny H H H2N"' Glycine O Me h OH H2N Alanine OH H2N Mettaonine O HjN OH Valine O U q ^ Koh „OH Aspartic Acid 0 OH Oj H2ItS< ,OH Glutamic Acid 0 H2N Leucine O HjN H2N-Tryptophan Ö OH H H? N OH Serine O H2N OH Threonine O H2N Asparagine O H2lsľ Glutamine O H Proline O H?N Lysine O H2N Hisudine O 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 Ne Asp As n Glu Gin Arg Lys His Phe Ser Thr Tyr Trp Met Cys Pro Sec Pyr G A V L 1 D N E Q R K H F S T Y W M C P U 0 Třídění aminokyselin Aminokyseliny s podobnými vlastnostmi mohou plnit v proteinu stejné funkce - bývají vzájemně zastupitelné CH3 O O H3C OH H3C OH NH2 Isoleucine CH3 NH2 Leucine al i jihni i c =- r s ■ = ■ 11 |io tar Nukleové báze NH, N. V VlH' 'N NH2 N NH O 4 -I \c N. V N H Adenine Cytosine N' NH2 Guanine o HoC> o 'NH X) Thymine NH NH X) Uracil adenin cytosin guanin thymin uracil A C G T U Nukleová báze Adenin N NH Nukleosid Ho^ Adenosin N < N ,0. Nukleotid Adenosinmonofosfát AMP H OH OH 0 11 N < M P—0—i N o 1 OH W OH OH Nukleotid Adenosintrifosfát ATP 0 0 0 II II II HO—P—O—P—O—P—O—i 1 I I OH OH OH N V N O. W OH OH 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ů 1 1 2x4 (pro hexosu) vzájemných vazeb Struktura proteinů (NK) ADSQTSSNRAGEFSIPPNTDFRAIF FANAAEQQHIKLFIGDSQEPAAYHK LTTRDGPREATLNSGNGKIRFEVSV NGKPSATDARLAPINGKKSDGSPF TVNFGIVVSEDGHDSDYNDGIVVL QWPIG primární (sekvence) terciární Pred: -&-,—- >- Pred: CCCCCEECCCCCCCCCCCCEEEECCCCCEEEEEEECCCCC AA: DSQEPAAYHKLTTRDGPR EATLN SGNGKIRFEV SVNGKPS 50 60 70 80 Pred: -Ozz^-1 >-■ Pred: CCHHEEEECCCCCCCCCCCEEEEEEEECCCCCCCCCCCEE AA: ATDARLAPINGKKSDGSPFTVNFGIWS EDGHDSDVNDGI 90 100 110 120 sekundární kvartérní Kvartérní struktura proteinů Homooligomer Heterooligomer Homotetramer AB5 toxin Jsou sekvence stejné, podobné či zcela odlišné? ATGTCTACTCCTGGAGCACAGCAAGTCCTCTTCCGCACCGGAATTGCCGCGGTCAACTCAACCAACCATCTCCGTGTTTACTTCCAGGATGTCTATGGCAG TATTCGCGAGAGTCTCTACGAGGGCAGCTGGGCTAACGGCACCGAAAAGAACGTTATCGGCAATGCTAAGCTTGGCAGCCCTGTGGCCGCGACTTCTAAG GAGCTGAAGCATATCCGTGTCTACACCCTCACTGAAGGAAACACCCTACAGGAGTTCGCCTACGACTCCGGAACCGGATGGTACAACGGCGGGCTGGGC GGTGCAAAGTTCCAAGTCGCACCCTACTCTCGCATTGCTGCCGTGTTCCTAGCCGGAACAGATGCATTGCAGTTGCGAATCTATGCACAGAAGCCAGATAA CACAATCCAGGAGTATATGTGGAACGGCGATGGCTGGAAGGAGGGCACCAACCTGGGAGGTGCTCTCCCCGGCACTGGAATCGGAGCCACCTCCTTCCG CTATACCGACTACAATGGCCCAAGCATCCGGATCTGGTTCCAAACTGACCTCAAACTCGTCCAAAGAGCCTACGACCCGCACAAAGGCTGGTACCCGGAC CTCGTCACCATCTTTGACAGGGCACCGCCACGTACGGCCATTGCAGCCACCAGCTTTGGAGCCGGCAACAGTTCCATCTACATGCGTATCTACTTTGTCAA TTCGGACAACACTATCTGGCAGGTCTGCTGGGACCACGGCAAGGGCTATCACGACAAGGGAACCATCACCCCAGTCATTCAGGGCTCGGAGGTCGCCATT ATCAGCTGGGGCAGTTTCGCCAATAACGGGCCGGATCTGCGTCTGTACTTTCAGAATGGAACATACATTAGTGCTGTGAGCGAGTGGGTTTGGAATCGGG CACATGGGTCGCAGTTGGGCAGAAGTGCTCTTCCTCCTGCTTGA ATGGCTGATTCTCAAACGTCATCCAACCGCGCCGGCGAATTCTCGATTCCGCCGAATACCGATTTCCGCGCGATTTTCTTCGCGAATGCCGCCGAGCAACA GCACATCAAATTGTTCATCGGCGACAGCCAGGAACCCGCCGCGTATCACAAGCTGACGACGCGCGACGGCCCGCGCGAAGCCACGCTGAATTCCGGCAA CGGCAAGATCCGTTTCGAGGTGTCGGTGAACGGCAAGCCGTCGGCGACCGACGCGCGTCTCGCGCCGATCAACGGCAAGAAGTCGGACGGCTCGCCGT TCACGGTCAACTTCGGGATCGTCGTGTCGGAAGACGGCCACGACAGCGACTACAACGACGGCATCGTCGTGCTCCAGTGGCCGATCGGCTGA ATGCTGGTGATTGTGGATGCCGTTACCCTGCTGAGCGCCTATCCGGAAGCCAGCCGTGATCCGGCCGCCCCGACCGTGATTGATGGTCGCCACCTGTATG TTGTTAGCCCGGGCGATGCCGCGCAGCTGGGCCATAACGATAGCCGTCTGTTTACCGGTCTGAGCCCGGGTGATCAGCTGCATCTGCGCGAAACCGCGC TGGCGCTGCGCGCGGAAGTGAGCGTGCTGTTTATTCGCTTTGCCCTGAAAGATGCCGGCATTGTTGCCCCGATCGAACTGGAAGTGCGTGATGCCGCCAC CGCCGTTCCGGATGCGGATGATCTGCTGCATCCGAGCTGTCGTCCGCTGAAAGATCATTATTGGCGCAGCGATGTGCTGGCGGCGGGCGCGACCACCTG TACCGCCGATTTTGCGGTGTGCGATCGTGATGGCACCGTGAGCGGTTATTTTCGTTGGGAAACCAGCATTGAAATTGCGGGCAGCCAGCCGGATACCAAA CAGCCGGGCTTTAAACCGAGCAGCGATCGCAATGGCAACTTTAGCCTGCCGCCGAATACCGCCTTTAAAGCGATCTTCTATGCGAACGCGGCGGATCGTC AGGATCTGAAACTGTTTATTGATGATGCGCCGGAACCGGCCGCCACCTTTGTGGGTAACAGCGAAGATGGTGTGCGTCTGTTTACCCTGAATAGCAAAGGT GGTAAAATTCGTATTGAAGCGAGCGCGAACGGCCGTCAGAGCGCGACCGATGCCCGTCTGGCGCCGCTGAGCGCGGGCGATACCGTGTGGCTGGGCTG GCTGGGCGCGGAAGATGGTGCCGATGCGGATTATAATGATGGCATTGTTATTCTGCAGTGGCCGATTACCTAA ATGTCGAGCGTTCAAACCGCTGCCACTTCGTGGGGAACCGTACCGTCGATCCGTGTGTACACGGCCAATAATGGCAAGATCACCGAGCGATGCTGGGACG GGAAGGGGTGGTACACCGGTGCCTTCAACGAGCCCGGCGATAACGTCTCCGTAACCAGCTGGCTGGTCGGCAGCGCGATCCATATCCGCGTCTATGCAA GCACCGGCACCACGACCACGGAGTGGTGCTGGGACGGCAACGGCTGGACCAAGGGCGCCTACACCGCCACGAACTGA ATGCCGCTGCTGAGCGCCAGTATCGTGAGCGCGCCGGTGGTGACCAGCGAAACCTATGTGGATATTCCGGGCCTGTATCTGGATGTTGCGAAAGCCGGTA TCCGTGATGGCAAACTGCAGGTTATCCTGAATGTGCCGACCCCGTATGCGACGGGCAATAACTTTCCGGGTATTTATTTTGCGATCGCCACCAACCAGGGC GTGGTGGCGGATGGTTGCTTTACGTATAGTAGCAAAGTGCCGGAAAGTACGGGCCGTATGCCGTTTACCCTGGTTGCGACCATTGATGTGGGTAGCGGTG TTACCTTCGTGAAAGGTCAGTGGAAATCTGTTCGCGGCTCTGCGATGCATATTGATAGCTATGCAAGCCTGAGTGCGATTTGGGGCACCGCGGCACCGAGT TCTCAGGGTTCTGGTAACCAGGGTGCGGAAACGGGTGGCACCGGTGCCGGTAATATTGGTGGCGGCGGTGAACGTGATGGCACCTTTAATCTGCCGCCG CATATTAAATTCGGTGTTACCGCGCTGACCCACGCGGCGAACGATCAGACCATTGATATTTATATTGATGATGATCCGAAACCGGCAGCCACCTTTAAAGGC GCGGGCGCGCAGGATCAGAACCTGGGTACCAAAGTGCTGGATTCTGGCAATGGCCGTGTTCGCGTTATCGTTATGGCGAACGGCCGTCCGAGCCGCCTG GGTTCTCGTCAGGTGGATATTTTTAAAAAATCTTATTTCGGTATTATTGGCTCTGAAGATGGTGCGGATGATGATTATAACGATGGCATCGTGTTTCTGAACT GGCCGCTGGGCTAA ATGCCGCTCCTGAGCGCCAGTATCGTGAGCGCGCCGGTGGTGACCAGCCAAACCTATGTGGATATTCCGGGCCTGTATCTGGATGTTGCGAAAGCCGGTA TCCGTGATGGCAAACTGCAGGTTATCCTGAATGTGCCGACCCCGTATGCGACGGGCAATAACTTTCCGGGTATTTATTTTGCGATCGCCACCAACCAGGGC GTGGTGGCGGATGGTTGCTTTACGTATAGTAGCAAAGTGCCGGAAAGTACGGGCCGTATGCCGTTTACCCTGGTTGCGACCATTGATGTGGGTAGCGGTG TTACCTTCGTGAAAGGTCAGTGGAAATCTGTTCGCGGCTCTGCGATGCATATTGATAGCTATGCAAGCCTGAGTGCGATTTGGGGCACCGCGGCACCGAGT TCTCAGGGTTCTGGTAACCAGGGTGCGGAAACGGGTGGCACCGGTGCCGGTAATATTGGTGGCGGCGGTAAGCTTGCGGCCGCACTCGAGATCAAACGG GCTAGCCAGCCAGAACTCGCCCCGGAAGACCCCGAGGATGTCGAGCACCACCACCACCACCACTGA Jsou sekvence stejné, podobné či zcela odlišné? MSTPGAQQVLFRTGIAAVNLTNHLRVYFQDVYGSIRESLYEGSWANGTEKNVIGNAKLGSPVAATSKELKHIRVYTLTEGNTLQEFAYDSGTGWYNGGLGGAKFQ VAPYSRIAAVFLAGTDALQLRIYAQKPDNTIQEYMWNGDGWKEGTNLGGALPGTGIGATSFRYTDYNGPSIRIWFQTDDLKLVQRAYDPHKGWYPDLVTIFDRAPP RTAIAATSFGAGNSSIYMRIYFVNSDNTIWQVCWDHGKGYHDKGTITPVIQGSEVAIISWGSFANNGPDLRLYFQNGTYISAVSEWVWNRAHGSQLGRSALPPA MADSQTSSNRAGEFSIPPNTDFRAIFFANAAEQQHIKLFIGDSQEPAAYHKLTTRDGPREATLNSGNGKIRFEVSVNGKPSATDARLAPINGKKSDGSPFTVNFGIV VSEDGHDSDYNDGIVVLQWPIG MLVIVDAVTLLSAYPEASRDPAAPTVIDGRHLYVVSPGDAAQLGHNDSRLFTGLSPGDQLHLRETALALRAEVSVLFIRFALKDAGIVAPIELEVRDAATAVPDADDLL HPSCRPLKDHYWRSDVLAAGATTCTADFAVCDRDGTVSGYFRWETSIEIAGSQPDTKQPGFKPSSDRNGNFSLPPNTAFKAIFYANAADRQDLKLFIDDAPEPAA TFVGNSEDGVRLFTLNSKGGKIRIEASANGRQSATDARLAPLSAGDTVWLGWLGAEDGADADYNDGIVILQWPIT MSSVQTAATSWGTVPSIRVYTANNGKITERCWDGKGWYTGAFNEPGDNVSVTSWLVGSAIHIRVYASTGTTTTEWCWDGNGWTKGAYTATN MPLLSASIVSAPVVTSETYVDIPGLYLDVAKAGIRDGKLQVILNVPTPYATGNNFPGIYFAIATNQGVVADGCFTYSSKVPESTGRMPFTLVATIDVGSGVTFVKGQW KSVRGSAMHIDSYASLSAIWGTAAPSSQGSGNQGAETGGTGAGNIGGGGERDGTFNLPPHIKFGVTALTHAANDQTIDIYIDDDPKPAATFKGAGAQDQNLGTKVL DSGNGRVRVIVMANGRPSRLGSRQVDIFKKSYFGIIGSEDGADDDYNDGIVFLNWPLG MPLLSASIVSAPVVTSQTYVDIPGLYLDVAKAGIRDGKLQVILNVPTPYATGNNFPGIYFAIATNQGVVADGCFTYSSKVPESTGRMPFTLVATIDVGSGVTFVKGQW KSVRGSAMHIDSYASLSAIWGTAAPSSQGSGNQGAETGGTGAGNIGGGGKLAAALEIKRASQPELAPEDPEDVEHHHHHH Alignment Srovnání (přiložení) dvou či více sekvencí (aminokyselinových, nukleotidových) na základě jejich vzájemné podobnosti. 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 WLAKALKYLMETAQASSISTELARHHPRAVDAKRKSEMKRKTAMWLAKALKYLMETAQASSISTELARHHPRAVDAKRKSEMKRKTAM WLAKALKYLMETAQASSISTELARHHPRAVDAKRKSEMKRKTAMWLAKALKYLMETAQASSISTELARHHPRAVDAKRKSEMKRKTAM Multiple sequence alignment - více sekvencí WLAKALKYLMETAQASSISTELARHHPRAVDAKRKSEMKRKTAMWLAKALKYLMETAQASSISTELARHHPRAVDAKRKSEMKRKTAM WLAKALKYLMETAQASSISTELARHHPRAVDAKRKSEMKRKTAMWLAKALKYLMETAQASSISTELARHHPRAVDAKRKSEMKRKTAM WLAKALKYLMETAQASSISTELARHHPRAVDAKRKSEMKRKTAMWLAKALKYLMETAQASSISTELARHHPRAVDAKRKSEMKRKTAM WLAKALKYLMETAQASSISTELARHHPRAVDAKRKSEMKRKTAMWLAKALKYLMETAQASSISTELARHHPRAVDAKRKSEMKRKTAM WLAKALKYLMETAQASSISTELARHHPRAVDAKRKSEMKRKTAMWLAKALKYLMETAQASSISTELARHHPRAVDAKRKSEMKRKTAM WLAKALKYLMETAQASSISTELARHHPRAVDAKRKSEMKRKTAMWLAKALKYLMETAQASSISTELARHHPRAVDAKRKSEMKRKTAM Pair-wise alignment • Srovnání dvou sekvencí • Sekvence mohou být přiloženy v celé své délce (global alignment) nebo jen v určitém regionu (local alignment). 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í. 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í. 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ých 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 Bhzsi napr. http://emboss.sourceforge.net/docs/themes/SequenceFormats.html • F ASTA formát >název(upopis dle vlastní volby)J SEKVENCESEKVENCESEKVENCESEKVENCES EKVENCESEKVENCEJ POVINNÉ VOLITELNÉ >AFL MSTPGAQQVLFRTGIAAVNLTNHLRVYFQDVYGSIRESLYEGSWANGTEKNVIGNAKLGSPVAATSKELKHIRVYT LTEGNTLQEFAYDSGTGWYNGGLGGAKFQVAPYSRIAAVFLAGTDALQLRIYAQKPDNTIQEYMWNGDGWKEGT NLGGALPGTGIGATSFRYTDYNGPSIRIWFQTDDLKLVQRAYDPHKGWYPDLVTIFDRAPPRTAIAATSFGAGNSS IYMRIYFVNSDNTIWQVCWDHGKGYHDKGTITPVIQGSEVAIISWGSFANNGPDLRLYFQNGTYISAVSEWVWNR AHGSQLGRSALPPA >BC2LA MADSQTSSNRAGEFSIPPNTDFRAIFFANAAEQQHIKLFIGDSQEPAAYHKLTTRDGPREATLNSGNGKIRFEVSV NGKPSATDARLAPINGKKSDGSPFTVNFGIVVSEDGHDSDYNDGIVVLQWPIG > BC2LD MLVIVDAVTLLSAYPEASRDPAAPTVIDGRHLYVVSPGDAAQLGHNDSRLFTGLSPGDQLHLRETALALRAEVSVL FIRFALKDAGIVAPIELEVRDAATAVPDADDLLHPSCRPLKDHYWRSDVLAAGATTCTADFAVCDRDGTVSGYFR WETSIEIAGSQPDTKQPGFKPSSDRNGNFSLPPNTAFKAIFYANAADRQDLKLFIDDAPEPAATFVGNSEDGVRLF TLNSKGGKIRIEASANGRQSATDARLAPLSAGDTVWLGWLGAEDGADADYNDGIVILQWPIT >RSL MSSVQTAATSWGTVPSIRVYTANNGKITERCWDGKGWYTGAFNEPGDNVSVTSWLVGSAIHIRVYASTGTTTTE WCWDGNGWTKGAYTATN >gj14443698551ref|ZP_21169562.11 fucose-binding lectin II [Burkholderia cenocepacia K56-2Valvano] MPLLSASIVSAPVVTSETYVDIPGLYLDVAKAGIRDGKLQVILNVPTPYATGNNFPGIYFAIATNQGVVADGCFTYSS KVPESTGRMPFTLVATIDVGSGVTFVKGQWKSVRGSAMHIDSYASLSAIWGTAAPSSQGSGNQGAETGGTGAG NIGGGGERDGTFNLPPHIKFGVTALTHAANDQTIDIYIDDDPKPAATFKGAGAQDQNLGTKVLDSGNGRVRVIVMA NGRPSRLGSRQVDIFKKSYFGIIGSEDGADDDYNDGIVFLNWPLG >gi|283806765|pdb|2WQ4|A Chain A MPLLSASIVSAPVVTSQTYVDIPGLYLDVAKAGIRDGKLQVILNVPTPYATGNNFPGIYFAIATNQGVVADGCFTYSS KVPESTGRMPFTLVATIDVGSGVTFVKGQWKSVRGSAMHIDSYASLSAIWGTAAPSSQGSGNQGAETGGTGAG NIGGGGKLAAALEIKRASQPELAPEDPEDVEHHHHHH Jak ale poznám dobré přiložení? MAM—UZDOST—STAROSTISHAMIZ—NOSTIRATOLESTI MAMRA—DOSTZESTARO--------ZITNO---------STI 1 MAMUZDOST—STAROSTISHAMIZNOSTIRATOLESTI 37 1 MAMRADOSTZESTAR-------O-Z----1 — TNO-STI 24 1 MAMUZDOST—STAROSTISHAMIZNOSTIRATOLESTI 37 1 MAMRADOSTZESTAROZITNO---------------STI 2 4 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 Skórování proteinového přiložení Substituční matice (a z nich odvozeny skórovací matice) Reflektuje fyzikálně chemické vlastnosti jednotlivých aminokyselin ale zároveň i pravděpodobnost, že dojde k substituci konkrétní aminokyseliny za jinou konkrétní v průběhu evoluce. Počet přiložených reziduí s Celkové délky podobnými vlastnostmi obou sekvencí Substituční matice víceméně dva typy: 1. založené na záměnnosti genetického kódu nebo vlastností aminokyselin 2. odvozené z empirických studií aminokyselinových substitucí (přesnější) Nejvíce používané jsou empirické matrice PAM a BLOSUM 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 matrice s 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 matic 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). PAM - Point Accepted Mutation Vytvořila Margaret Dayhoff roku 1978. Zahrnuje pravděpodobnost záměny jedné aminokyseliny v druhou během evoluce Předpokládá, že každá další mutace nezávisí na předchozí. Odvozena z globálního alignmentu 71 rodin proteinů (Podobnost sekvencí v rodině > 85%) • vysoká spolehlivost alignmentu • vysoká pravděpodobnost, že záměna aminokyseliny je dána jedinou mutací Vypočtena pravděpodobnost s jakou jedna AA se změní na jakoukoliv jinou PAM1 Byla vypočtena na základě 1572 změn v aminokyselinovém složení v 71 proteinových rodinách PAM1 reflektuje průměrnou záměnu 1% všech aminokyselinových pozic PAM250 (20% identita) je odvozena od PAM1 její 250-tinásobnou multiplikací (250 mutací na 100 aminokyselin) Vyšší číslo PAM matrice znamená větší evoluční vzdálenost PAM matice A R N D A 9867 2 9 10 R 1 9913 1 0 N 4 1 9822 36 D 6 0 42 9859 C 1 1 0 0 PAM250 matrice Positive score - frequency of substitutions is greater than would have occurred by random chance. C s T 9 -1 -1 4 1 5 small, polar Zero score - frequency is equal to that expected by chance. P A G -3 0 -3 -1 -1 1 0 0 -2 7 -1 -2 4 0 6 small, nonpolar Negative score - frequency is less than would have occurred by random chance. N -3 1 0 -2 -2 0 6 D E -3 -4 0 -1 0 -1 -1 -1 -2 -1 -1 -2 i 0 6 2 5 polar or acidic Q -3 0 -1 -1 -1 -2 0 0 2 5 ^ H R -3 -3 -1 -2 -1 -1 -2 -2 -2 -1 -2 -2 1 ■ 0 ■ -1 -2 0 0 0 8 1 0 5 basic K -3 0 -1 -1 -1 -2 0 ■ -1 1 1 -1 2 5 M 1 -1 -1 -1 -1 -2 -1 -2 -3 -1 -1 -3 -4 -2 ■ -3 -3 -3 -2 -3 0 -2 -3 -3 -1 -1 -3 -3 5 1 large, hydrophobic L V -1 -2 -1 -3 -1 -4 -3 -4 -3 -2 -3 -2 -2 2 2 4 -1 -2 0 -2 0 -3 -3 -3 -2 -2 -3 3 2 1 3 1 4 F Y -2 -2 -2 -2 -2 -2 -4 -3 -2 -2 -3 -3 -3 -2 -3 -3 -3 -2 -3 -1 -1 2 -3 -3 -2 -2 0 -1 - 00-16 aromatic -1 -1-1 3 7 W -2 -3 -2 -4 -3 -2 -4 -4 -3 -2 -2 -3 -3 -1 - -3 -2-3 1 2 11 C S T P A G N D E Q H R K M I L V F Y W • Pozor na zjednodušení v matici PAM: - Mutace AA je nezávislá na předchozích mutacích v téže pozici (Markov process requirement). - Pouze matice PAM1 byla "změřena", všechny ostatní jsou extrapolace (tj. jsou založeny na stejném modelu). - Všechna místa podléhají mutacím rovnoměrně. - Mutace nezávisí na okolních residuích. - Krátkodobé a dlouhodobé vlivy na evoluci sekvencí jsou stejně účinné. - PAM matice je založená na proteinových sekvencích dostupných v roce 1978 (bias vzhledem k malým globulárním proteinům) • Nová generace Dayhoff-type - např. PET91 BLOSUM (Blocks Amino Acid Substitution) • 1992, Henikoff and Henikoff • database BLOCKS - používá koncept „bloků" k identifikaci proteinových rodin • sekvenční motiv - konzervovaný aminokyselinový úsek spojený se specifickou funkcí proteinu • sekvenční blok - spárované motivy ze stejné proteinové rodiny bez mezer • BLOSUM matrice byly vytvořeny na základě substitučních vzorů více než 2 000 bloků (< 60 residuí) z 500 skupin proteinů • nebere v potaz evoluci • BLOSUM62 - znamená, že ke konstrukci matrice byly použity proteiny s průměrnou identitou 62%. a - c = 4 • výskyt každého páru AA v každém a - e = 2 sloupci každého bloku je sečten c - e = 2 . čísla získána ze všech bloků slouží a - a = i pro výpočet BLOSUM matricí c - C = 1 Matice BLOSUM 62 Ala 4 Arg - 1 b As n - 2 C 6 Asp - 2 -2 1 6 Cys 0 -3 -3 }■ Gin - 1 ' ■:■ Ĺ _ % 5 Glu - 1 C o 2 -4 2 Gly 0 - 2 o _ x - 2 His - 2 C 1 _ x 0 He - 1 -3 _ "í -3 -1 -3 Leu - 1 - 2 -3 -4 -1 - 2 Lys - 1 2 0 -3 ' Met -1 - 1 2 -3 - 1 C Phe - 2 -3 _ "í -3 -2 -3 Pro -1 -2 -2 -3 Ser 1 1 C - 1 C Thr □ 0 - 1 Trp -3 -3 -4 -4 -2 -2 Ty r - 2 -2 -2 - 3 -2 - 1 Val 0 -3 - 3 - 1 - 2 Ala Arg As n As p Cys Gin 5 - 2 6 0 - 2 8 -3 -4 -3 4 -3 -4 -3 2 1 - 2 - 1 -3 -2 5 - 2 -3 - 2 1 2 - 1 5 -3 -3 - 1 □ č -3 :j - 1 -2 - 2 -3 -3 - 1 2 č C - 1 - 2 2 0 -1 - 1 2 - 2 -1 - 1 - 1 - 3 2 - 2 -3 -2 _ "í - 1 -2 -3 2 - 1 -2 - 1 2 -3 -3 -2 1 Glu Gly His lie Leu Lys Met 6 -4 7 - 2 - 1 4 - 2 - 1 1 5 1 -4 -3 - 2 11 3-3-2-2 2 7 -1 -2 -2 0 -3 -1 4 Phe Pro Ser Thr Trp Tyr Val Číslování BLOSUM jde v obráceném pořadí oproti PAM - čím menší číslo, tím odlišnější sekvence byly použity Pam40 Short highly similar alignments 70-90 PAM 160 Detecting members of a protein family 50-60 PAM250 Longer alingments of more divergent sequences -30 BLOSUM90 Short highly similar alignments 70-90 BLOSUM80 Detecting members of a protein family 50-60 BLOSUM62 Most effective in finding all potential similarities 30-40 BLOSUM30 Longer alingments of more divergent sequences <30 Similarity column gives range of similarities that the matrix is able to best detect Odlišné substituční matice jsou pro odlišné účely BLOSUM 30 BLOSUM 62 BLOSUM 45 PAM 1 PAM 120 PAM 250 Les s dlvergent < > More divergent more stringent less stringent BLOSUM matrice pracují obvykle lépe než PAM pro lokální vyhledávání podobností (Henikoff & Henikoff, 1993) Pro porovnání blízce příbuzných proteinů by se měla používat nižší čísla PAM a vyšší BLOSUM, pro vzdálenější vyšší čísla PAM a nižší BLOSUM Pro prohledávání databází je nejběžnější BLOSUM62 Jak statisticky významné je skóre? Pokud je podobnost dostatečně významná lze usuzovat na společné evoluční vztahy. Ale co je DOSTATEČNĚ? Závisí na typu sekvence a její délce • Pravděpodobnost, že dvě rezidua v nepříbuzných sekvencích jsou identické? 25% v NA, 5% v proteinech • Vliv délky sekvence - Čím kratší sekvence, tím větší je šance, že alignment je dán náhodnou shodou. Čím delší, tím je méně pravděpodobné, že je stejná úroveň podobnosti výsledkem náhody. - Kratší sekvence vyžadují vyšší cut-off pro zjištění příbuznosti než u delších sekvencí. 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- 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). Krátká mezera: atcttcagtgtttcccctgttttgcccIatttagttcgctc atcttcagtgtttcccctgttttgcccgatttagttcgctc Dlouhá mezera: ^^^^^^^^^^^^^^ atcttcagtgtttcccctgttttgccc--------------------atttagttcgctc atcttcagtgtttcccctgttttgcccgcccccccccccccccccccatttagttcgctc Skóre Každé dvojici sekvencí je ve výsledku přiřazeno číslo - skóre, které určuje míru jejich podobnosti [Range of Alignment AT TG TCÄAAGA uT'TGÄG'CTGA TGCA T GGCAGA QAfTGA-CTGACAAGGGTATCG S= Zŕidentities, mismatches) - £ (gap penalties) Score = Max(S) Čí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 AAEECCDDEEF 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 na úrovni jednotlivých aa pro nesprávně přiložené sekvence: aaeeccddeef aaddkkkefgg 4+4+2+2-3-3-1+2-3-2-3 = -1 Příklad výpočtu AAEECCDDEEF 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 aaeeccdd--eef aa----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. aaeeccdd--eef aa----ddkkkefgg -10-1-1-1 -10-1 = -24 Celkové skóre 32 - 24 = 8 Příklad výpočtu AAEEYYDDEEF AADDFFKEFGG 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 aaeeyydd--eef aa----ddffkefgg 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. aaeeyydd--eef aa----ddffkefgg -10-1-1-1 -10-1 = -24 Celkové skóre 32 - 24 = 6 Příklad výpočtu AAEEYYDDEEF AADDFFKEFGG 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 aaeeyyddeef aaddff--kefgg 4+4+2+2+3+3 +1+5+6 = 30 Naopak, pro každou mezeru (-) je dána penalizace: první výskyt zleva -10, každá následující -1. aaeeyyddeef aaddff--kefgg -10-1 = -11 Celkové skóre 30-11 =19 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í primem (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í nepodobně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í 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) na základě distanční matice (distance matrix) z jednotlivých sekvencí A B c 0.92 0.65 0.79 B A B C Počet exaktně stejných shod dělená celkovou délkou sekvence (ignoruje mezery) 0.92 0.79 Progresivní multiple alignment A B C 0.92 0.79 Nejdříve provede pairwise alignment A a B Pak přidá sekvenci C do předešlého alignmentu (inzerce mezer, pokud je potřeba) 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 alignmentů. Výstupem je .dnd soubor. NEMÁ fylogenetický význam 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í zvolene metody (nj, phylip, dist). .dnd soubor ( ( PAULO. 16435, RSIIĽ0.13654) :0.03384, ( CVIIĽ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 DIST - length 3>igth = 114 2 vs. 3 DIST = 0.3772 = 114 2 vs. T UISI = TT.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 ■nj soubor 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 Cycle Cycle Cycle 1 2 3 4 = SEQ = SEQ = SEQ = SEQ 2 ( 0.17807) joins SEQ 1 ( 0.34101) joins Node 5 ( 0.44298) joins SEQ 4( 0.44518) joins SEQ 3( 2( 7( 6( 0.19912) 0.13706) 0.47807) 0.45833) Cycle 5 (Last cycle, trichotomy): Node: 1 ( 0.12171) joins Node: 4 ( 0.01864) joins Node: 5 ( 0.02083) dst soubor PAUL 0.000 0.649 0.684 RSIIL 0.649 0.000 0.377 CVIIL 0.684 0.377 0.000 BCLA 0.930 0.912 0.912 BCLB 0.904 0.895 0.939 BCLC 0.939 0.912 0.930 BCLD 0.982 0.939 0.947 0.930 0.904 0.939 0.982 0.912 0.895 0.912 0.939 0.912 0.939 0.930 0.947 fc^O 0.921 0.904 0.965 0.921 0.000 0.956 0.921 0.904 0.956 0.000 0.965 0.965 0.921 0.965 0.000 Fylogram a kladogram • Fylogram (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. • Kladogram - 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). Fylogram a kladogram Paul rsiil cviil Fylogram bclb bclc bcla bcld Kladogram paul rsiil cvii l bclb bcla bcld bclc Fylogram a kladogram Phylogenetic Tree of Life Paul Bacteria Archaea Spirochetes ProteobacterB Cyanotiaotsre RiTKtanyces Green Fiarnentaus bacterB Eucaryota Entamoebaie ^.'Vl6 Anrnals molds RSIIL cviil Flagellar? Trchornonads Microsporia a Dp lorn on ads bclb bclc bcla bcld paul RSIIL Kladogram CVIIL bclb bcla bcld bclc Výstup - .aln soubor CLUSTAL 2.0.10 multiple sequence alignment PAUL RSIIL CVIIL BCLB BCLC BCLA BCLD ---LVEKLPQYDVFVDIATIPYSFDVGSWQNKVKTDAAGEVVACTVTWAGAPGVLPGAAA AIATNQGVVADGCFTYSSKVPESTGRMPFTLVATIDVGSGVTFVKGQWKSVRGSAMHIDS LRETALALRAEVSVLFIRFALKDAGIVAPIELEVRDAATAVPDADDLLHPSCRPLKDHYW PAUL RSIIL CVIIL BCLB BCLC BCLA BCLD -----------------------------------------------------ATQGVFT -----------------------------------------------------AQQGVFT -----------------------------------------------------AQQGVFT KFGVGAVVN----------------Y FS KAT PQP VQ PAP VP--------TGGGE RDGI FT YASLSAIWG----------------TAAPSSQGSGNQGAETGGTGAGNIGGGGERDGT FN -------------------------------------ADSQT---------SSNRAGEFS RSDVLAAGATTCTADFAVCDRDGTVSGYFRWETSIEIAGSQPDTKQPGFKPSSDRNGNFS PAUL RSIIL CVIIL BCLB BCLC BCLA BCLD LPANTRFGVTAFANSSGTQTVNVLVNNETA—ATFSGQSTNNAVIGTQVLNSGSSGKVQV L PANT S FGVTAFANAANT QTIQVLVDNVVK—ATFTGSGTSDKLLGSQVLNSGS-GAIKI LPARINFGVTVLVNSAATQHVEIFVDNEPR—AAFSGVGTGDNNLGTKVINSGS-GNVRV LPPNIAFGVTALVNSSAPQTIEVFVDDNPKPAATFQGAGTQDANLNTQIVNSGK-GKVRV LPPHIKFGVTALTHAANDQTIDIYIDDDPKPAATFKGAGAQDQNLGTKVLDSGN-GRVRV IPPNTDFRAIFFANAAEQQHIKLFIGDSQEPAAYHKLTTRDGPRE—ATLNSGN-GKIRF LPPNTAFKAIFYANAADRQDLKLFIDDAPEPAATFVGNSEDGVRL—FTLNSKG-GKIRI ' Bio Edit Sequence Alignment Editor File Edit Sequence Alignment View Accessory Application RNA World Wide Web Options Window Help / D:\SkolaWyuka\MSA - dataUCLlectins seq.aln y g I Courier New ~Ž\ B 8 total sequences Mode: I Select / Slide ^1 Selection:0 Pn-r-ihni-T Sequence Mask: None Numbering Mask: None ď i d I I S «»[+ gili f | I ;.;■■■[*¥ Si Si©mi[h ? Scroll . speed slow ^ ^ fast PAUL R SI IL C VIIL BCLB BCLC BCLA BCLD Clustal Cons ■ I T T T T I T T T T | T T T T | T T T T | T T T T | T T T T | T T T T | T T T T | T T T T | T T T T | T T T T | T T T T | T T T T | T T T T | T T T T | T T T T | T T T T | T T T T | T T T T | T T T T | T T T T | T T T T | T T T T | T T T T | I 10 20 30 40 50 (30 70 80 90 1GG 110 120 ---------SQPFTHDDLYALLQ--LAGNDATAVQAN DQAVLDRMRQFMTAQ----------LVEKLPQYDVFVDIATIPYSFDVGSWQNKVKTDAAGEVVACTVTWA APGVLPGAAAKFGVGAV P L L S A SIV SAP V VT S E TY VDIP GL YL D VAKAGIRD GKL Q VIL N VP T PYAT GNNFPGIYFAIAT NQGVVAD GC F T Y S S K VP E S T GRMP F T L VATIDVGSGVTF VKGQWK S VRG SAMHID SYA S L SAI LVIVDAVTLL SAYP EA S RD PAAP T VID RHLYVVSP D QL HNDSRLFT LSP DQLHLRETALALRAEVSVLFIRFALKDA IVAPIELEVRDAATAVPDADDLLHPSCRPLKDHYWRSDVLAA J-L Výchozí návrh * Ja I view 2.3 File Tools Help Window D:\SkolaWyuka\MSA - data\BCLlectins seq. a In File Edit Select View Format Colour Calculate Web Service 200 210 s0g t gum PASU1-111 RSttU 1-113 CVIIU1-113 SCLB/1-213 BCLC/1-271 3CLA/1-128 BCLD/1-25S . PARSlR iL P A g F G V L P A r I N F G V L P P I a F G V N L P P H I k F G U P pBHd F RA i |a F k A I H I p p[ ™l p p[ Énvlvnn eHa ■ quluJnvuk■ aA e q j H i kl aA dR0Dl k l AH t s A a T0H V E i FVDlNEPR I E VF V D D N P KP a A I D I V I 0 D D P KPAA f V D D V,DD f i C| f i DD 220 s g q sHn n Av| tg SgHsBkL lg - a f s g v g g d n n l g f 'j g a g Q dan l h f kg ag a'l ľj.j h l g a f ; au f 1 sq e paaybkl t t r d g p r e a p e p a auf v gnsedgvrl 2-10 g g - g a i j i j V G NV™V™I GgV j vvv G j V0V i VMj-G j i gH i j V I VMA j f e vHv 3i e A0A Conservation Quality Coníeníus :+ 7663 180076 38 641 4 £> 5 £> 7 9 5 9 3 5 3 - - 5 7 3 7 4 7 3 4 5 2 4 5 - - 3 6 9 9 54- 407 7 47 6 tlppntafgvta+anaa+ td t i + vfvddepkpaatf + gagt + danlgtqvlnsgs - gkvrvqvsang Sequence position 247 5,460428 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í Pairwise alignment „programy" Oblasti použití: • Přímé porovnání dvou sekvencí • Vyhledávání podobných sekvencí v databázích •širíírríTtS Needle & Water • vytvořeny 1970 Needleman S.B. and Wunsch CD. (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 Globálně podobné sekvence Needle PA-IIL RS-IIL 1 ATQGVFTLPANTRFGVTAFANSSGTQTVNVLVNNETAATFSGQSTNNAVI 50 1*1 I I I I I I I I 1*1 I I I I I I 1***1 I 1**1 I 1*1***1 I ]• 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 RS-IIL 1 ATQGVFTLPANTRFGVTAFANSSGTQTVNVLVNNETAATFSGQSTNNAVI 50 1*1 I I I I I I I I 1*1 I I I I I I 1***1 I 1**1 I 1*1***1 I ]• AQQGVFTLPANTSFGVTAFANAANTQTIQVLVDNVVKATFTGSGTSDKLL 50 PA-IIL 51 GTQVLNSGSSGKVQVQVSVNGRPSDLVSAQVILTNELNFALVGSEDGTDN 100 RS-IIL 51 GSQVLNSG-SGAIKIQVSVNGKPSDLVSNQTILANKLNFAMVGSEDGTDN 99 PA-IIL 101 DYNDAVVVINWPLG RS-IIL 100 DYNDGIAVLNWPLG 114 113 Lokálně podobné sekvence eedle 1 -ADSQTSSN- 101 TFVKGQWKSVRGSAMHIDSYASLSAIWGTAAPSSQGSGNQGAETGGTGAG -RAGEFSIPPNTDFRAIFFANAAEQQHIKLFIGDSQEPAAYHK- 151 NIGGGGERDGTFNLPPHIKFGVTALTHAANDQTIDIYIDDDPKPAATFKG 51 -------LTTRDGPREATLNSGNGKIRFEVSVNGKPSATDARLAPINGKK 201 AGAQDQNLGTK- -VLDSGNGRVRVIVMANGRPSRLGSRQVDI-FKK 94 SDGSPFTVNFGIVVSEDGHDSDYNDGIVVLQWPIG 128 244 S-------YFGIIGSEDGADDDYNDGIVFLNWPLG 271 ater 9 RAGEFSIPPNTDFRAIFFANAAEQQHIKLFIGDSQEPAAYHK- 15 8 RDGTFNLPPHIKFGVTALTHAANDQTIDIYIDDDPKPAATFKGAGAQDQN 51 LTTRDGPREATLNSGNGKIRFEVSVNGKPSATDARLAPINGKKSDGSPFT 2 0 8 LGTK------VLDSGNGRVRVIVMANGRPSRLGSRQVDI-FKKS- 101 VNFGIVVSEDGHDSDYNDGIVVLQWPIG 128 245 -YFGIIGSEDGADDDYNDGIVFLNWPLG 271 8 150 50 200 93 243 50 207 100 244 Global vs. local alignment ť urS.p_psTis.l-ty: 10.0 í l3tt£r.d_p£r.altiv 0 . č ť # Length: 357 # Identity: 33/3&"7 < 9. í Similarity: 33/357 ( 9.2%! # Gaps: 310/357 (Se.8%) # Score: £"?.£ = ± Ihti : Pairwise 314 vs. 90 aa protein » = a„ Obsahuje repetice Skore:57.5 EtE0SS_ jDOl : EtE0SS_ jDOl : EtE0SS_ jDOl i: EtE0SS_ _íi01 : EtE0SS_ jDOl -.4 EtE0SS_ jDOl 3ž EtE0SS_ _€01 122 EtE0SS_ jDOl l Ť EtE0SS_ jDOl 153 EtEOSS €01 = : EtE0SS_ jDOl 203 EtE0SS_ jDOl Et-ECS£_ _DQ1 253 EtE0SS_ jDOl = : EtE0SS_ jDOl 303 EHBOSS 001 rl ST E GACJGVL FET GI AAVNLTHHLRVYFCjDVYGS IRES LYEGSWAHGTEKN VIGNAKLGS EV—AATS KELKH------IRVYT-----LTE----GNTLQ I -I I I I I I I I I I - I I I ---------S SVQTAATS-----WST VE 3 IRVYTAHKC-KI TERCií DGK--- EFAYD SGT GWYNGG1GGAKFCJVAEY SRIAAVF------------LAGT DA III. II I I . I - I --------SWYT----GA-------------EHE PGDNVSVTSHLVGS - A i; i z-.z Y.-.w : ::r z ;zyk----------7:: 21 o-t: ;;e-:-----r :tl s ? s ... I -I I I -I-1 I --I II i:-::;.".-::.-.-----------bz-^zzz-zz^z-7z^c-^zv.z^z:íz:-~::------- TGI GATS FRYTDYNGPSIRIWFGTDDLEO.VQRAYLiPHKGWYPDLVTI FDR APERT AI AAT SFGAG1TS SIYMRIY YVNS DNTIWGVCWDHGKGYHDKGT IT PVIQGSEVAIISWGS FANNGPDLRIYFĚNGTÍISAYSEWYWNRAHGSĚLG RSALEPA 314 ------- rl' lť/321 (11-26) 19/321 (15-2S) 13/321 Skore:108 = : : : : ■ 3 č: ■ -. : 121 = i ■e : 157 i: 207 i: 257 = : ! = ť 307 = : i: I.I I I I I - - : - - I I I I I - - - I - : - I - - : I I - I I I - I -- 3 ÜT 5WGTYP S lEVTfTílHHGK-ITERjClf D-GKG1Í YZGA I : - - I : I - I : I = - = I =1 I ----I - - I : - I : I : I I - : -HLirtJS-ArHIinníA-STGTTTTEWOTDiaJGlíZK I I 314 ž: : S" 4: ?: 24i ?: Nelze však spoléhat na zdánlivě dobrá řešení PLLSASIVSAPVVTSETYVDIPGLYLDVAKAGIRDGKLQVILNVPTPYATGNNFPGIYFAIATNQGVVADGCFTYSSKV PESTGRMPFTLVATIDVGSGVTFVKGQWKSVRGSAMHIDSYASLSAIWGTAAPSSQGSGNQGAETGGTGAGNIG GGGERDGTFNLPPHIKFGVTALTHAANDQTIDIYIDDDPKPAATFKGAGAQDQNLGTKVLDSGNGRVRVIVMANGR PSRLGSRQVDIFKKSYFGIIGSEDGADDDYNDGIVFLNWPLG ERDGTFNLPPHIKFGVTALTHAANDQTIDIYIDDDPKPAATFKGAGAQDQNLGTKVLDSGNGRVRVIVMANGRPSR LGSRQVDIFKKSYFGIIGSEDGADDDYNDGIVFLNWPLGPLLSASIVSAPVVTSQTYVDIPGLYLDVAKAGIRDGKLQ VILNVPTPYATGNNFPGIYFAIATNQGVVADGCFTYSSKVPESTGRMPFTLVATIDVGSGVTFVKGQWKSVRGSAM HIDSYASLSAIWGTAAPSSQGSGNQGAETGGTGAGNIGGGGKLAAALEIKRASQPELAPEDPEDVEHHHHHH □ 01 i e: :=;.'.'_ ůůi 1 □ 01 i e: :=;.'.'_ důl IL e: :e ůůi 1 □ 01 101 e: :=;.'.'_ důl Ir e: :e důl 151 e::=;e.'_ důl :i důl LI. e::e;í b_ důl lir e::=;e.'_ důl LIL e::e;3í_ důl 1e6 e: :=;.'.'_ důl L~L e: :e důl 236 e::e;^í důl 2e4 -PLL3Ä3IV3ÄPWT3E IYyTC ^ SZ.YLĽ7AKAGIRU 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 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 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 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 i I i i I i I I i I I i I I i I I i i i - I i : i - - I -TTľTT- : —PAS---- e: : 100 £5 150 = 5 zoo LÍŽ 25 Ľ le5 271 235 2e2 : : . | | . . | . : . : . -LAEEDPEmíEHHH- BLAST algoritmus BLAST (Basic Local Alignment Search Tool) The BLAST Search Algorithm 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) query word (W= 3) GueĽF: GS VE DTTCSCSLAALLNKCKTP (JGQRL VNQUI KOPLI© Klí E IE E Fl. LH LVE A?VEEAELRQTLQEDL neighborhood words PQG 16 PEG IS PRC- 14 PKO H PHO 13 PDG 13 PHG 13 Hl G 13 PSG 13 f.!>. 12 PUN 12 eft... neighborhood score threshold (T =13) OufiĽy: 325 S L A AL LNKC KTPQ CQEL VWQUIKQPLHD KHP IE ER.I2-] LVE * 3 d 5 +LA++L.+ TP (j r++ +U+ P+ D + ER + A Sto j et: 290 TL A5VLĎC TVTPMGS EílLKRULHHPVEDTRV LLERQQT IG A 330 High-scoring Segment Pair (HSP) Tvorba k-písmenných slov ze vstupní sekvence pro proteiny typicky 3-písmenných (v prípade DNA 11 -písmenných) Query sequence: PQGEFG Word 1:PQG 'ord 2: QGE Porovnání slov na základě substituční matice 4w. algoritmus BLAST hledá na základě vloženého skóre slova, která jsou podobná L*jword3:GEF každému slovu v zadané sekvenci. Vyhovující slova jsou následně uspořádána. word4 EFG • 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 sequence: R P P Q G L F Database sequence: D P PEG V V U, Exact match is scanned. Score:-2 7 7 2 6 1 -1 HSP Optimal accumulated score = 7+7+2+6+1 = 23 Vystup z BLASTu Distribution of 73 Blast Hits on the Query Sequence g YP_QC2232S17 lectin [Burfcholderia cenocepacia J2315] 5=4SS E=3.9e-173 Color kev for alignment scores <40 40-50 EO-200 >=20C I 1 1 1 1 1 1 1 40 HO 120 1G0 200 240 *** Vystup z BLASTu SI Download ~ GenPept Graphics fu cose-bin ding lectin II [Burkholderia multi varans ATCC BAA-247] Sequence ID: reflZP 1591S73S. 11 Length: 274 Number of Matches: 1 See 1 mors litlei's) Range 1: 31 to 274 Ga-Pcpt Sraph =s Sc&re Expect Method 443 brt5(114D] 4e-155 Compositional matrix adju: 2 QPFT HDDLYALLQLAGNDATAVir. QPFTHDDLYALLQLAGNDA AV{ Sbjct 31 QPFT HDDLYALLQLAGNDAKÄV1C 62 5 FDVGSWQNKVKT D AAGEWAC1 S FDVT5SWÜNKVKT D AAG4WAC7] Sbjct il 5 FDVGSWQNKVICI D AAGQWAC1 120 PAPVPTGGGERDGIFT1PPNIAI P GGGERDG+F LPPNIAI Sbjct 151 PDTArAGGGERDGYFNlPPNIAI leo LNTQIVNSGKGIOTRVVVTANGKI LNTQIVNSG GEVUVWT NGKI Sbjct 211 LNTQIVNSGrtfGKVRVVVTVNGKI ZiZ-'■] 240 WPLG 2 43 Sbjct 271 WPLG 2 74 H Download ^ GenPept Graphics sugar-binding lectin protein [Ralstonia solanacearurn PSI07] Sequence ID: reflYP 00375P856.1I Length: 114 Number of Matches: 1 t* See 3 more lltlefs"! Range 1: 3 to 114 GenPept Graphics "Evi:?l5 Match Störe Expect Method Identities- POa-itivea Saps 124 hjts(312) 2e-32 Compositional matrix adjust. 62/114(54%) BQ/114(7Q%) Z/114(116) Query Sbjct Query Sbjct 130 RDGI FT L P PHI AFGVTALWS S APQTIEVTTVEDH PKPAATFQGAGT QDANLHT QIVNSGK 4 G4FTLP H FGVTA N44 QTI4V VTJ4 K ATF G4GT D L 4Q4-I-NSG4 3 QQGVFT L PANTH FGVTAFANAAMT QTIKVLVTJNVW—ATFS GSGT SDKLLG S QVLNSGR 190 GKVRVWT ANGKPSKIGSRQVDIFEKT YFGLVGSE DGGDGDYHDGIAILCTWPLG 243 G V44 V4 HGKPS 4 3 Q 4 K F 4VGSED D DYHDGIA4LHHPLG 61 GAVQIQVSVHGKPSDLVSH'QTILAHKLNFAMVGSE DS SDHDYHDGI AVLIThTLG 114 IBS c I @ Download ~ GenPept Graphics fu cose-bin ding lectin PA-IIL [Pseud om etnas aerjginosa ATCC 25324] Sequence ID: reflZP 15615365.11 Length: 115 Number of Hatches: 1 > See 1 more title is^ Range 1: 5 to 115 GenPept Graphics T Netft Match A Prev =ls MaTch See-re Expect Method Identities Pü-aitivea Gaps 117 bit5(294) 7e-3Q Compositional matrix adjust. 61/113(54%) 77/113(6S%) 3/113(2%) Query 132 Gl FT L P PNIAFGVTALVNS S APQTIE VFVTJ DH PKPAATFQGAGT QDANLNTQIVNSGK-G 190 G+FTLP N FGVTA NSS QT4 V V H 4 AATF G T 4A 4 TQ44NSG G Sbjct 5 GVFT L P ANTQ FGVTAFANS S GT QTYNVTV--HNETAATFS GQSTNNAVIGTQVLNSGSSG 62 Query 191 KVRWVTANGKP S KI GS RQVIi IFKKT Y FGLVG S EDGGDGD YNDGI AI 1NWPLG 2 43 KV4V V4 NG4PS 4 S QV 4 4 F LVGSEDG D DYND 4 44NWPLG Sbjct €3 KVUVQVSVNGRP S DLVS AQVILTNEIN FA1VG S EDGT DNDYNDAYWINWPLG 115 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říčce signalizují významnou shodu (či podobnost). Cílem je nalezení nejdelšího shodného úseku (úseku s nejvyšším skóre). a a c g g c t t a c g • u • * -p • -p ■ u ■ • u< ■ 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 kriter í. Příklad porovnání sekvencí GGCTTTCGG a AACGGCTTACG MSA „programy" • Za posledních 15 let vzniklo pres 50 MSA programových balíku (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.clustal.org/ 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: C ustal W (Thompson et al., 1994) Clustal X (Jeanmougin et al., 1998) Clustal Q (Sievers et al., 2011) 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) Clustal - 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říbuznosti - od nejvíce podobných k nejméně příbuzným (viz. 2.). Jednou vložené mezery jsou zachovány. Clustal - výstup 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 IPPNTC LPPNT£ LPPNI£ LPPHIK FI FI F( F( LAIFFANAAEQQI CAIFYANAADRQI ^VTALVNSSAPQ^ jVTALTHAANDQ^ fr )L 'I 'I tvLFIGDSQEPAAYHKLTTRDGE FID D A P E PAAT F VGN S E D G\, ĽVFVDDNPKPAATFQGAGTQD^ ľ>I YIDDDPKPAATFKGAGAQDC R] r: n: n: :—ATLNSGNGKIRFE j—FTLNSKGGKIRIE jNTQIVNSGKGKVRVV jGTKVLDSGNGRVRVI • • • • • *k • • • • • • • • • *k • *k *k *k • • • • • • • 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: 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 (treel) 3. 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ů 1.1 fí-mer counting "i=5> unaligned sequences 1.2 \/ t UPGMA V" 1.3 progressive alignment MSA1 k-mer distance matrix D1 TREE1 2.1 compute %idsfrom MSA1 MSA2 J 2.3 progressive 22UPGMA alignment | ^^^^ Kimm distance matrix D 2 c3 j c^A 3.2 compute subtree profiles 3.3 to-aügn MSA profiles 3.4 SP i — score better? No, delete Ye$. M S A3 3. í tfetete ecťge from TREE2 giving í subtrees repeat Fi^urt 2. This diagram summarizes cht? flow of the MUSCLH algorithm. There are three main slaves: Stage 1 (draft progressive), Stage 2 (improved progressive) and Stage 3 (refinement). A multiple alignment is a vail ah It? at the comp]t?tion of each stagt?4 at which point tht? algorithm may terminate. 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 alignmentů je použití pozičně specifického skórovacího schématu (extended library) namísto substituční matice. T-Coffee 1) Provedení pairwise alignmentů pro všechny dvojice sekvencí pomocí globálního a pomocí lokálního alignmentů (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 globálním a lokálním alignmentů, 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. c K_ . - riustalW Primary Library (GlfirKil Pairwise. Alignment) A -B ■ A C ft . <::■ ■v li' íl Lalign Pii maty Library (Local I_Pairwise AI ígnroent) I Weighting Signal Addition PRIM A ti V UE5RAKY D EXTENSION EXTENDED LIBRARY PROGRESSIVE ALIGNMENT A R 1. Clustal Q Provedení pairwise alignmentů urychleno použitím modifikovaného algoritmu mBed - převedení sekvencí na n-rozměrný vektor a následný alignment vektorů 2. Sestavení příbuzenského stromu (similarity tree) 3- Sestavení alignmentů užitím přesného algoritmu HHalign (využití skrytých Markovových modelů). Určen pro obsáhlé alignmenty. V roce 2011 přiloženo 190 000 sekvencí během několika hodin. Zlepšení přesnosti -strukturní informace • Sekvence s vyšší homologií (>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 - využití známých homologních proteinů (srovnání dle jejich struktury nebo tvorba profilu homologních sekvencí) Sequences Templates Structure based Alignment PIUW templates Template to sequence alignment Výhoda', vyšší přesnost Tem a kite based alignment of the sequences Primary Library 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í T Alignment - přiložení sekvencí (2 nebo více) na základě podobnosti T Využití pro hledání příbuznosti sekvencí, tvorba profilů proteinových rodin, aj. T Ř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í T Každý alignment potřebuje lidskou kontrolu !!! 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 et al., 1998]. OxBench [Raghava etal., 2003] PREFAB [Edgar, 2004] Benchmark (srovnávací testy) Existují i specificky zaměřené benchmarkové sety, např. IRMBASE [Subramanian etal, 2005] -náhodné (nepřiložitelné) sekvence s vloženými motivy. Slouží k testování metod pro lokální alignment BAIiBASE [Thompson era/., 1999] contains eight reference sets, each dealing with a different type of alignment problem. Ref1 deals with test cases containing small numbers of equidistant sequences, and is funher subdivided by percent identity. Ref2 alignments contain "orphan", or unrelated, sequences. Ref3 test cases contain a pair of divergent subfamilies, with less than 25% identity between the two groups. Ref4 is concerned with long terminal extensions, while Ref5 test cases contain large internal insertions and deletions. Test sets from References 6-8 deal with problems like transmembrane regions, inverted domains, and repeat sequences. In previous versions of BAIiBASE, test cases were confined to homologous regions. In practice, the boundaries of such regions may be unknown. The current version [Thompson ef a/., 20C5] now also provides duplicate test cases comaining full-length sequences. Only the first five reference sets are used here, as they have been corrected and verified in the latest release. OxBench [Raghava era/., 2003] comprises 3 related datasets. Test cases in the MASTER set deal with isolated domains derived exclusively from sequences of known structure. The FULL set was generated from suitable MASTER test cases, using full-length sequence data. High scoring homologous sequences were added :o each MASTER test case to generate the EXTENDED set. The results from this third set, however, are not used here. It was found that some of the test cases in the EXTENDED set proved too large for some programs, and aborted due to excessive memory requirements. Of the 276 test cases selected from EXTENDED, T-COFFEE returned 235 alignments, and Align-m was only able to align 107, using a single processor wi:h 4GB of RAM. PREFAB [Edgar, 2004] test cases are generated by taking a pairwise alignment of sequences of known 3D structure, and adding up to 24 high scoring hornologues for each sequence. Accuracy is assessed on the structural alignment of the original pair alone. SAB mark [Van Walle ef a/., 2005] is divided into two subsets. Each test group in the SUPERFAMILY set represents a SCOP superfamily, whose sequences are 25-50% identical. Each test group in the TWILIGHT set represents a common SCOP fold and sequences are 0-25% identical. In addition, these two subsets are also provided with nonhomologous (false positive) sequences included within each group. Instead of a single alignment acting as a reference, SABmark provides multiple pairwise references (breach test, and it is the average score from each of these references tha: is taken here as a score for each test case. IRMBASE [Subramanian era/., 2005] test cases contain a number of simulated motifs [Stoye era/., 1998] inserted into otherwise random {unalignable) sequences, and as such is entirely different to the other benchmarks used in this study. Test cases are designed to examine whether a method can detect isolated motifs within sequences, and so are tailored to a local alignment approach. HOMSTRAD [Mizuguchi ef a/., 1996] is a database exclusively based on protein structures derived from the PDB, arranged into homologous protein families. It was not specifically designed as a benchmark database, although it is regularly employed as such. BaliBASE - ukazka alignmentu P22736/1-S98 Q2TUT9/1-S92 P41829/1-619 Q61JK2/1-376 Q93WF8/1-340 095 WGy 1-448 096562/1-435 P49866/1-666 Q4H3D3/1-512 Q3UP4S/1-416 Q59IV9/1-549 Q23Ciyi-54d Q15QJ1/1-548 Q95WQ4/1-380 Q2PK0y 1-462 Q3iSQ8/1-d26 Q5U64y 1-526 340 SGCJOFFBTV iGCKGF FKRTI iGCKGF FKRTVQ iGCKGF FKRTVQ Joels ffBt vol EGCKGFFKRTV EGC^GFF DGCKGFF K3CKGFF ►GClOFF iocr JCKAFFI JCKAFFI joc|aff| jGCSGFF EGCKGFF 8 IQG SIQG 8 I OG S IrS-ISIsHMHsIBI tvr|-dltytcrd GCBGF FHS I QQK i qyrpctk GCKGF FRRSI0|-NMiytchr 350 NAKYICLA NAQYVCLQ NSKYTCAG NSKYTCAO QLHYTCVE QLEYTCKO NRKYSCLG NHGYTCRF NHQYGCRF SHVY8CRF HNDYICPA HNDYI CPA HNDYMCPA 360 NKDCP AKNCV NKTCP NKNCP NMSCQ --DGNCEVNOIS --KRHCDT - -ARNCVV --SRNCTV --SROCVV - -TNGCTI - -TNQCT - -TNGCTI TNOKONCPV -TKGCIV -NQOCSI -DKNiVr 370 380 R NRCQFClFG CLAVGMV NRCHYC FQ CLKVGMV SRCQYClYO CLEVGMV FQ FQ FN NGCRSO NRCQY NRCQY NRCQY rd......SLKGR HG......SLSGR OG......SLSOR ed......RAPGG E|......RTPOG FQBCVQVGMKPEAVQDETLK- - KERKDY CLAQGMLfCEAV SRCQYC IRCQFO NRCQYC NRCQYC NOCRYC LRiCFKAOMK NOCRYC LR CFRAGMK nqcrycIlr CFRAGMKl LR CYEVGMVl LR CFEVGMM CYEVGMMl CFEVTMN clntgmki AVOMS FEVGMS CLEVGMV CLSLGML 400 -slkgrI 410 grlpskpk 420 cqlnehg jAVQNE...........323 Iavqne........... javqne........... |cg8|re-rc0y-riv-r |cgt|re-rcoy-riv- - )gv|k|-rg-r-vlr • javqhergpr- -SSTLRi gspaevt 33Is...... t...... t...... M- qI rggi........ LKE-AQERMEIA avqee...........|q|gre - • reocdses AVlFORVPK.......|e|AK I LAAMQ- SVNA 8v|njo}rnkk......k|et8kqe......... R.R. ■ Conservation l 4-1214 1 2 - - - 3 4 2 21 4 34 36 3 •: •: •: • 24........... I 21 2000 Perrodou et al. BMC Bioinformatics 2008 9:213 doi:10.1186/1471 -2105-9-213 RGRLPSKPK ELM instance true positive H»K«=Mai: false negative "false positive rnrrkscqa Table 1: Programs used in this investigation. Method Align_m (2.3) [Van Walle et al., 2004] ClustalW (1.3) [Thompson et al.. 1994] Dialign2 (2.2) [Morgenstern, 1999] Di align -t {0.1.3) [SLibra nan ian st al., 2DC5] MAFFT {5.531) [Katohetal.,2002] FFTNS FFTHSi NWNS OVERVIEW ht1p://bioinformalics. vu b. a c. be/soft ware/soft wa re. html Local, specialised far highly divergent sequences. htlp://www. e bi. a c. u k/clu sta I w/ Global, progressive alignment package. http^/bibiserv.techfah .un i-biel efeld.de/dialign/ Local, aligns segments of sequences rather than individual residues. http://dialign-t.gobics.de/ Local, progressive alignment. Recent re-implementation of Dialign2. htlp://www. bioph y s. Ky oto-u .ac.jp/- katoh/programs/alig n/mafft/ Suite of alignment programs: Global, uses Fas: Fourier Transform to generate tree. As FFTNS, but wi:h iteration step to refine alignment. Global, uses traditional Needleman-'Wunsch algorithm. NWNSi As NWNS, but with iteration step to refir FINSi Local, itera:ive: uses local pairwise aligr Blackshield 2006 oznacil ProbCons jako nejlepsi na zaklade 6 benchmarkovych testu GINSi Global, iterative, uses global pairwise alignment information. MUSCLE (3.6) [Edgar, 2004] http://www. drive 5. convmu sc le/ Global, iterative, progressive alignment program that uses Log Expectation as scoring func:ion. ProbCons (1.09) [Do et al., 2005] httpi//prob con s. Stanford. edu/ Global, uses posterior-probabilities from HMMs and pairwise alignment consistency. PCMA (2.0) [Peietal.,2003] ftp :!t\o le. swmed. edu/p ub/PC MA/ Global, switches alignment strategies dependent on sequence data. ClustalW is used to align highly similar sequences and to form pre-aligned groups. T-COFFEE is used to align the more divergent groups. PDA (v2) [Lee et al., 2002] http://www. bioinformatics. u cla.edu/poa/ Local; uses Partial Order graphs. T-COFFEE (1.37) [Notredame et al., 2000] http://igs-se rver. en rs-m rs.fr/- cno:red/Proje cts_ho me_page/ :_coffee_home_page. htm I Combines both global and local methods; uses consistency. 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 n>Regjlar Progressive Ali^nTnirril Strategy ►SegA GARFIELD THE LAST FAT CAT S*-W«fchi-lwi SaoB GAtiF LtLLi 'i'k£----FAST CAT prim wetehl = tirfl SooC SAP.FTF.'.n TFEE V3FY FAST CAT * S»qB GARFIELD THE FAST CAT „.._, ,.„,„,,, _ ,„„ g^jH------- THE FA-T CAT R " SeqC GARFIELD THE VERY FAST CAT |.rLm Weicht -MO SwijD------- TUR----FA-T CAT HEju - urn c)fcxte.ndijd Library for scul anJ suq2 Extended Library SaqA garfield the last fat cat mum in m in SatiB SAKKIKJj" tse FAST CAT _l_ I>yrtamic Programming GARFIELD THE LAST FA-T CAT StttjB GARFIELD THE----FAST CAT Figure 2, The library extension, (a) Progressive alignment. hour sequent*-, have been designed. The tree indicates the order in which the sequences are aligned when using a progressive method such as ClustalVV. The resulting align merit is shown, with the word CAT misaligned, (b) Primary library. Each pair of sequences is aligned using ClustalVV. In these alignments, each pair of aligned residues is associated with a weight equal to the average identity among matched residues within the complete alignment (mismatches are indicated in bold type), (c) Library extension for a pair of sequences. The three possible alignments of sequence A and B are shown (A and B, A and B through C, A and B through Dj. These alignments are combined, as explained in the text, to produce the position specific library. This library is resolved by dynamic programming to give the correct alignment. The thickness of the lines indicates the strength of the weight. 5»ija ::;Afi?rF.:,3 the 11111111 Ml SoaB GARFIELD THE LAST FAT CAT Nil III FAST CAT S^qA OARFIELD THE LAST FAT CAT llllllll iii Mil ii \ tt\ SfiOC GAKI-'lELD THE VERY FAST CAT iiiiiiii 111 mi ii Snqfl GARFIELD THE FAST CAT Wflptll = 77 Seal GARFIELD THE iii S»qD THE 111 S«KJB GAXFI2LD THE T AST FAT CAT III III fat cat I IN \\\ FAST CAT Method Score Templates Validation Values Server PreFab HOMSTRAD ClustalW [14] Matrix — 61.30 [12] — htt p://www. ebi.ac.uk/clustalw/ Kalign Matrix — 63.00 [IS] — htt p://m sa. eg b. ki. se/ MUSCLE [6] Matrix — 60.00 [16] 45.0 [9] http://www.drive5.com/muscle/ T-Coffee [10] Consistency — 69.97 [12] 44.0 [9] htt p://www.t c of fee. □ rg/ ProbCons [7] Consistency — 70.54 [12] — http://probcons.stanford.edu/ MAFFT [8] Consistency — 72.20 [12] — htt p://al i g n. g en o m e.j p/mafft/ M-Coffee [12] Consistency — 72.91 [12] — htt p://www.t c of fee. o rg/ MUMMALS [16] Consistency — 73.10 [16] — http://prodata.swm ed.edu/mumm a Is/ DbClustal [24] Profiles — — http://bips.u-strasbg.fr/PipeAlign/ PRALINL [9] Matrix Profi les — 502 [9] http://zeus,cs.vu.nl/programs/pralin eww w/ P ROMA LS [16] Consistency Profi les 79.00 [16] — http://prodata.swmed.edu/promals/ SP EM [23] Matrix Profi les 77.00 [23] — http://sparks.informatics.iupui.edu/Softwares-Services_files/spem.htm Lxpresso [13] Consistency Structures — 71.9 [ll]a htt p://www.t c of fee. o rg/ T-Lara [29] Consistency Structures — — htt ps://w ww .mi.fu-berlin,de/w/LiSA/ Validation values were compiled from several sources, and selected for comparability. PreFab validations were made using PreFab version 3. HOMSTRAD validations were made on data sets having less tlan 30% identity, The source of each value is indicated by the accompanying reference citation. 'The Expresso value comes from a slightly more demanding subset of HOMSTRAD (HOM39) made of sequences less than 25% identical. dol:10.1 3 71 /jou rnal. p cbi .00301 23.t001