Chemoinformatika a bioinformatika Sequence alignment Osnova 1. Struktura biomakromolekul - sekvence 2. Alignment a jeho typy 3. Užívané algoritmy 4. Multiple sequence alignment 5. Programové balíky 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 o r Nukleová kyselina Nukleotidy Esterová p u\ / o oh q/z^oh Polysacharid Monosacharidy Glykosidická <0h oh oh X o CM -l 1 3 ů I CD CO 5 1 o o -i- .oí 15 < pyrolysin >^ CL O selenocystein O 0 w prolin o i_ CL CL cystein w >^ O O methionin 0 tryptofan CL í_ 1- tyrozin s_ >^ 1- >- threonin i_ _£Z 1- 1- serin í_ 0 w w fenylalanin 0 JZ CL LL histidin w X X lysin w >^ _l X. arginin co i_ < úl glutamin O glutamová kys. O LU asparagin c w < Z asparagová kys. CL W < Q izoleucin 0 — leucin 0 _l valin > > alanin < < glycin O Třídění aminokyselin Aminokyseliny s podobnými vlastnostmi mohou plnit v proteinu stejné funkce - bývají vzájemně zastupitelné HoC O H3C OH Isoleucine CHo NH< Leucine non-polar charted Nukleové báze Nukleová báze Adenin NH2 NH ^0 Adenine Cytosine 1ST ^NH, adenin cytosin guanin thymin uracil A C G T U Nukleosid Ho Adenosin Nukleotid Adenosinmonofosfát AMP 0 II ho—p—o- 1 oh Nukleotid Adenosintrifosfát ATP 0 o o II II II ho—p—o—p—o—p—o- 1 I I oh 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 TVN FGI WS E DG H DS D YN DG IWL QWPIG primární (sekvence) terciární Predi _HS_i-N_i-N_ Pred i AA: Conf : Pred: Pred: AA: CCC CCEEC CCCCC CCCCC CEEEE CCCCC EEEEE EECCC CC □S Q EPAAY HKLTTRDGPREATLiN SGNGKIRFEV SVNGK PS 50 6Ů 70 30 CCEi HEEEE CCCCC CCCCC CEEEE EEEEC CCCCC CCCCC EE ATDARLAPINGKK S DGS P FTVNFGI WS EDGHDSDYNDGI 90 100 110 120 sekundární kvartem í Kvarterní struktura proteinů Homooligomer Homotetramer Heterooligomer 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é? mstpgaqqvlfrtgiaavnltnhlrwfqdvygsireslyegswangteknvignaklgspvaatskelkhirvytltegntlqefaydsgtgwyngglggakfq vapysriaavflagtdalqlriyaqkpdntiqeymwngdgwkegtnlggalpgtgigatsfrytdyngpsiriwfqtddlklvqraydphkgwypdlvtifdrapp rtaiaatsfgagnssiymriyfvnsdntiwqvcwdhgkgyhdkgtitpviqgsevaiiswgsfanngpdlrlyfqngtyisavsewvwnrahgsqlgrsalppa madsqtssnragefsippntdfraiffanaaeqqhiklfigdsqepaayhklttrdgpreatlnsgngkirfevsvngkpsatdarlapingkksdgspftvnfgiv vsedghdsdyndgivvlqwpig mlvivdavtllsaypeasrdpaaptvidgrhlywspgdaaqlghndsrlftglspgdqlhlretalalraevsvlfirfalkdagivapielevrdaatavpdaddll hpscrplkdhywrsdvlaagattctadfavcdrdgtvsgyfrwetsieiagsqpdtkqpgfkpssdrngnfslppntafkaifyanaadrqdlklfiddapepaa tfvgnsedgvrlftlnskggkirieasangrqsatdarlaplsagdtvwlgwlgaedgadadyndgivilqwpit mssvqtaatswgtvpsirwtanngkitercwdgkgwytgafnepgdnvsvtswlvgsaihirwastgttttewcwdgngwtkgaytatn 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 NGKPSATDARLAPINGKKSDGSPFTVNFGIWSEDGHDSDYNDGIWLQWPIG > BC2LD MLVIVDAVTLLSAYPEASRDPAAPTVIDGRHLYWSPGDAAQLGHNDSRLFTGLSPGDQLHLRETALALRAEVSVL FIRFALKDAGIVAPIELEVRDAATAVPDADDLLHPSCRPLKDHYWRSDVLAAGATTCTADFAVCDRDGTVSGYFR WETSIEIAGSQPDTKQPGFKPSSDRNGNFSLPPNTAFKAIFYANAADRQDLKLFIDDAPEPAATFVGNSEDGVRLF TLNSKGGKIRIEASANGRQSATDARLAPLSAGDTVWLGWLGAEDGADADYNDGIVILQWPIT >RSL MSSVQTAATSWGTVPSIRVYTANNGKITERCWDGKGWYTGAFNEPGDNVSVTSWLVGSAIHIRVYASTGTTTTE WCWDG NGWTKGAYTATN >gi|444369855|ref|ZP_21169562.11 fucose-binding lectin II [Burkholderia cenocepacia K56-2Valvano] MPLLSASIVSAPWTSETYVDIPGLYLDVAKAGIRDGKLQVILNVPTPYATGNNFPGIYFAIATNQGWADGCFTYSS KVPESTGRMPFTLVATIDVGSGVTFVKGQWKSVRGSAMHIDSYASLSAIWGTAAPSSQGSGNQGAETGGTGAG NIGGGGERDGTFNLPPHIKFGVTALTHAANDQTIDIYIDDDPKPAATFKGAGAQDQNLGTKVLDSGNGRVRVIVMA NGRPSRLGSRQVDIFKKSYFGIIGSEDGADDDYNDGIVFLNWPLG >gi|283806765|pdb|2WQ4|A Chain A MPLLSASIVSAPWTSQTYVDIPGLYLDVAKAGIRDGKLQVILNVPTPYATGNNFPGIYFAIATNQGWADGCFTYSS KVPESTGRMPFTLVATIDVGSGVTFVKGQWKSVRGSAMHIDSYASLSAIWGTAAPSSQGSGNQGAETGGTGAG NIGGGGKLAAALEIKRASQPELAPEDPEDVEHHHHHH 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 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 r -4 -3 0 0 -2 -1 -1 -1 0 1 2 v -2 -1 -1 -1 0 0 -2 -2 -2 -2 -2 m -5 -3 -2 -2 -1 -1 -3 -2 0 -1 -2 I -2 ^ -2 -1 -1 0 -2 -2 -2 -2 -2 l -6 -4 -3 -3 -2 -2 -4 -3 -3 -2 -2 f -4 -5 -5 -3 -4 -3 -6 -5 -4 -5 -2 y 0 -5 -5 -3 -3 -3 -4 -4 -2 -4 0 w -8 -7 -6 -2 -6 -5 -7 -7 -4 -5 -3 c G p s a t d e n q h CH, h,n CH, Valin 5 3 •2 0 •2 -3 •5 •4 •3 ,CH, HoNL HO^^O Izoleucin 6 2 4 0 2 6 2 4 2 5 3 2 4 2 6 4 -1 0 1 2 9 5 -2 -2 -1 -1 7 10 2 -6 -4 -5 -2 0 0 17 r V m i l f y w k Matrice BLOSSUM vypadá analogicky, liší se hodnoty. 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 r -4 -3 0 0 -2 -1 -1 -1 0 1 2 v -2 -1 -1 -1 0 0 -2 -2 -2 -2 -2 m -5 -3 -2 -2 -1 -1 -3 -2 0 -1 -2 I -2 -3 -2 -1 -1 0 -2 -2 -2 -2 -2 l -6 -4 -3 -3 -2 -2 -4 -3 -3 -2 -2 f -4 -5 -5 -3 -4 -3 -6 -5 -4 -5 -2 y 0 -5 -5 -3 -3 -3 -4 -4 -2 -4 0 w -8 -7 -6 -2 -6 -5 -7 -7 -4 -5 -3 c G p s a t d e n q h ch, h,n ch, Valin 5 3 •2 0 •2 -3 •5 •4 •3 6 •2 0 •2 -3 •4 •5 2 k r 4 2 6 4 2 5 2 4 2 6 1 0 1 2 9 2 -2 -1 -1 7 10 6 -4 -5 -2 0 0 17 V m i l f y w Matice BLOSUM 62 Ala 4 Arg - 1 5 As n - 2 0 6 Asp - 2 -2 1 6 Cys 0 -3 _ -3 9 Gin -1 1 0 0 . 3 5 Glu -1 0 0 2 -4 2 Gly Q -2 0 - 3 -2 His - 2 □ 1 - 3 0 lie -1 -3 -3 - 1 -3 Leu - 1 -2 -3 -4 - 1 -2 Lys - 1 2 0 - 3 ' Met - 1 -2 -3 - 1 C Phe - 2 -3 - 3 -3 - 2 -3 Pro -1 - 2 - 2 -3 - 1 Ser 1 -1 1 0 - 1 0 Thr 0 0 - 1 Trp -3 -3 -4 -4 - 2 -2 Tyr - 2 - 2 - 2 -3 - 2 Val 0 -3 . 3 -3 - 1 -2 Ala Arg As n Asp Cys Gin 5 -2 6 0 -2 8 -3 -4 -3 4 -3 -4 -3 2 ' - 2 - 1 - 3 - 2 (T - 2 -3 -2 1 2 - 1 5 -3 -3 - 1 0 0 -3 □ - 1 - 2 - 2 -3 -3 -1 -2 C □ -1 -2 -2 0 -1 -2 - 2 -1 -1 - 1 -3 -2 - 2 -3 -2 -1 - 2 -3 2 -1 - 2 - 1 - 2 -3 - 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 -7) - 2 - 2 2 7 -1 -2 -2 0 -3 -1 4 Phe Pro Ser Thr Trp Tyr Val GONNETova matice 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 ieho konci. 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: ATCTTCAGTGTTTCCCCTGTTTTGCCC-ATTTAGTTCGCTC 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 Ranqe of AllqnmentJ f-7~rx-^ ATTG TCÄÄAGA QTTGÄGC TGA TGCA T GGCAGA (VuTGA-JCTGACAAGGG TATCG \ Mismatch S= Scídentities, mismatches) - E (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 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 AAYYCCDDEEF 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 = 8 Příklad výpočtu AAYYCCDDEEF 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 = 32 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 32-11 =21 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. 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: M S A (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 nepřiložených sekvencí A B 0.92 A _ 0.92 A- C 0.65 0.79 - B ABC C Počet exaktně stejných shod dělená celkovou délkou sekvence (ignoruje mezery) 0.79 Progresivní multiple alignment • Používá ho většina programů • Vznik-1987 Feng, D.-F. and Doolittle, R.F. (1987) J. Mol. Evol. 25, 351-360. 1) sestavení příbuzenského stromu (guide tree) z nepřiložených sekvencí 2) tvorba párových alignmentů postupně podle příbuznosti (topologie guide tree) • Dnes obsahuje často iterativní smyčku 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í zvolené metody (nj, phylip, dist). dnd soubor □ ( ( PAIIL0.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 1j£ 7 niQT-ngflo^iQnr,+h = 114 2 vs. T UIS I =" 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) 114 ( ( ( PAIIL0.16435, RSIIL0.13654) :0.03384, ( ( BCLA:0.17899, BCLD:0.26633) :0.18717, BCLC:0.29707) :0.03484) :0.02264, CVIIL0.16563, .ph soubor paiil RSIIL cviil bclb bcla bcld bclc BCLB:0.26800); dst soubor 7 PAIIL 0.000 RSIIL 0.649 CVIIL 0.684 BCLA 0.930 BCLB 0.904 BCLC 0.939 BCLD 0.982 0.649 0.684 0.930 0.000 0.377 0.912 0.377 0.000 0.912 0.912 0.912 0.000 0.895 0.939 0.921 0.912 0.930 0.904 0.939 0.947 0.965 0.904 0.939 0.982 0.895 0.912 0.939 0.939 0.930 0.947 0.921 0.904 0.965 0.000 0.956 0.921 0.956 0.000 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 Paul rsiil cviil Phylogram b c lb bclc bcla bcld paul rsiil Cladogram cvii l bclb bcla bcld bclc Phylogram PhyiogenetJc Tree of Life Baetorli ArehiM Eucuyota .inm ^^^JJS^lj'ď^ffi^gfcŕh lij Ib^üJ JhSntl*-) ll'jr-.jr irľ. Cladogram 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 C CLUSTAL 2.0.10 multiple sequence alignment PAUL ------------------------------------------------------------ RSIIL ------------------------------------------------------------ CVIIL ------------------------------------------------------------ BCLB ---LVEKLPQYDVFVDIATIPYSFDVGSWQNKVKTDAAGEWACTVTWAGAPGVLPGAAA BCLC AIATNQGWADGCFTYSSKVPESTGRMPFTLVATIDVGSGVTFVKGQWKSVRGSAMHIDS BCLA ------------------------------------------------------------ BCLD LRETALALRAEVSVLFIRFALKDAGIVAPIELEVRDAATAVPDADDLLHPSCRPLKDHYW PAUL -----------------------------------------------------ATQGVFT RSIIL -----------------------------------------------------AQQGVFT CVIIL -----------------------------------------------------AQQGVFT BCLB KFGVGAWN----------------YFSKATPQPVQPAPVP--------TGGGERDGIFT BCLC YASLSAIWG----------------TAAPSSQGSGNQGAETGGTGAGNIGGGGERDGTFN BCLA -------------------------------------ADSQT---------SSNRAGEFS BCLD RSDVLAAGATTCTADFAVCDRDGTVSGYFRWETSIEIAGSQPDTKQPGFKPSSDRNGNFS PAUL LPANTRFGVTAFANSSGTQTVNVLVNNETA—ATFSGQSTNNAVIGTQVLNSGSSGKVQV RSIIL L PAN T S F GVTAFANAAN T Q TIQVLVDNWK—ATFTGSGTSDKLLGSQVLNSGS-GAIKI CVIIL LPARINFGVTVLVNSAATQHVEIFVDNEPR—AAFSGVGTGDNNLGTKVINSGS-GNVRV BCLB LPPNIAFGVTALVNSSAPQTIEVFVDDNPKPAATFQGAGTQDANLNTQIVNSGK-GKVRV BCLC LPPHIKFGVTALTHAANDQTIDIYIDDDPKPAATFKGAGAQDQNLGTKVLDSGN-GRVRV BCLA IPPNTDFRAIFFANAAEQQHIKLFIGDSQEPAAYHKLTTRDGPRE—ATLNSGN-GKIRF BCLD LPPNTAFKAIFYANAADRQDLKLFIDDAPEPAATFVGNSEDGVRL—FTLNSKG-GKIRI . "'BioEdit Sequence Alignment Editor Ed® File Edit Sequence Alignment View Accessory Application RNA World Wide Web Options Window Help & a y D:\SkolaWyuka\MSA dala\BCLlectins seq.aln EES Q g, jCourier New 3 D 3 total sequences Mode: | Select/Slide S election: 0 Position: Sequence Mask: None Numbering Mask: None Start ruler at: ■ + Bi£ffiB íl Ilili! PAUL RSIIL CVIIL BCLB BCLC BGLA BCLD Clustal C ons ---------SQPFTHDDLYALLQ—LAGNDAT VQ N DQ VLDRMRQFMTAG----------LVEKLPQYDVFVDIATIPYS DV SWGNKVKTD SEW CTVTW G PGVLPGAAAKFGVGAV PL L SAS IV SAP WT SETYVDIPGLYLDVAKAGIRDGKLQVILNVPTPYATGNNFPGIYFAIATNQGVVADGCFTYSSKVPESTGRMPFTL SYA3LSAI LUIVDAUTLL3AYPEA3RDPAAPTVIDGRHLYVV3PGDAAQLGHND3RLFTGL3PGDQLHLRETALALRAEVSVLFIRFALKDAGIVAPIELEVRDAATAUPDADDLLHP3CRPLKDHYWR3DVLAA Výchozí návrh * Jalview 2.3 File Tools Help Window P AUW-:: 4 R5U/Í-H3 CVSU1-113 BCLE/1-243 BCLCfi-S7i ECLQ/i-íee d:\skdlawyukawsa - da ta\bcl lectins seq.aln File Edit Select View Format Colour Calculate Web Service l pa l pa ■p p d f p pIjHaB 190 200 f g v a f a s g t v n f g V af a a N t i 'j f g v vlu 3 aat j|h| e f e v al v S a p e f g v al ha a n d i d f ra i F f a a e'j K f k a i F y a a d r d l K 210 220 'n n e a \. vi e r r / d n / d h .■dd i d d i s d i dd. a f s g q s a f t g sg aa fsg vg n n au i g k l l s n n l g an l n □ nlg e f - 1ybkl t t R Dg p r e -f v g n 3 e D g v r l - 230 _240 gss&Hv V In p kpaa i y i d d d p kpaa 1 F Q g ag Gl F KG AG Aul ap e paa q v l q v l kv i q i v kvl| A^M FiHI g s ■ g 3 ■ Q k ■ G n ■ G n ■ |k| g A i g n V v V i G eI u u I u u El| V i uma feu u i ea a Conservation Quality Consensus 7663 48667668844 40507050353- - 573747345245- -3600 54- 4 E'774768 ■ IM ■■! ^Mfc^J tlili tlppntafgvta+anaa+ td t i+vfvddepkpaatf + gagt + danlgtqulnsgs-gkuruqusang |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 MlOSS 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í alignment - Needle A 1 MPTEFLYTSKIAAISWAATGGRQQRVYFQDLNGKIREAQRGGDNPWTGGS 50 B 1 0 A 51 SQNVIGEAKLFSPLAAVTWKSAQGIQIRVYCVNKDNILSEFVYDGSKWIT 100 B 1 0 A 101 GQLGSVGVKVGSNSKLAALQWGGSESAPPNIRVYYQKSNGSGSSIHEYVW 150 B 1 0 A 151 SGKWTAGASFGSTVPGTGIGATAIGPGRLRIYYQATDNKIREHCWDSNSW 1*1*11 * 1 * 1 1 11111*1**1 200 B 1 —MQTAAISWGTT-PS------------IRV-YTANGNKITERCYDGSNW 34 A 201 YVGGFSASASAGVSIAAISW—GSTPNIRVYWQKGREELYEAAYGGSWNT 1 * * * * 1 * 1 1 1 1 248 B 35 1*1*1* * 1 1 * * * * 1 * * 1 11***1111 YTGAFN---QAGDNVSATCWL S GSAVHIRVY------------------- 62 A 249 PGQIKDASRPTPSLPDTFIAANSSGNIDISVFFQASGVSLQQWQWISGKG 298 B 63 **l 1*1***1*1 * 1 * 1 ---------------------------------ATSGGSTTEWCW-DGDG 78 A 299 WSIGAVVPTGTPAGW 313 B 79 1 * * 1 1 * 1 1 * WTRGAY—TGL----8 7 Lokální alignment - Water A 155 TAGASFGSTVPGTGIGATAIGPGRLRIYYQATDNKIREHCWDSNSWYVGG 1*1*1 * 1 * 1 1 11111*1**111 204 B 3 11**1*1*1 1* * 1 * 1*1**111*1*1*1***11*1* TAAISWGTT------------PS-IRV-YTANGNKITERCYDGSNWYTGA 38 A 205 FSASASAGVSIAAISW—GSTPNIRVYWQKGREELYEAAYGGSWNTPGQI * *** * 252 B 39 1* * 1 1 * * * * 1 * * 1 11***1111 FN---QAGDNVSATCWL S GSAVHIRVY----------------------- 62 A 253 KDASRPTPSLPDTFIAANSSGNIDISVFFQASGVSLQQWQWISGKGWSIG 302 B 63 **l 1*1***1*1 * 1 * 1 1 * * 1 -----------------------------ATSGGSTTEWCW-DGDGWTRG 82 A 303 A 303 B 83 A 83 Global vs. local alignment í Gap_pe:ial^y: 10.0 i l3ttĚr.d_pÉiialt7: O.E * Length: 3.57 ř Identity: $ Similarity: * Gaps: Í Score: ST.5 1 ifatTi.' rRT.n?iniij52 Pairwise 314 vs. 90 aa protein U/w (9.2*> Obsahuje repetice 33/357 ( 9.24} 3L0/357 (BG.Bl) Skore:57.5% EM30SS_ _001 : EM30SS_ _001 : e;:-:b;ss_ _001 I'- EM3GSS_ _001 - EM30SS_ _001 ll e::-:b;ss_ _001 35 _001 L22 EM30SS_ _001 =; EM3CSS_ JD01 b:-:b;ss 001 EM30SS_ _001 203 EM30SS_ _001 rl e:-:b;es_ _001 253 b:-:b;ss_ _001 EM30SS_ _001 303 EM30SS 001 rl ST E GAQQVL?KT GIAAVNLTHHLRVYFCDVYGSIRES LYEGSWANGTEKH VIGNAKLGS P V- - AATS KE1KH------IRVYT-----LTE----GN T LQ I - I I I I I I I I I I - I I I ---------S SVQTAATS-----H&TVPE IRVYT AHlT&fíITE3CÍÍ DGK--- EFAYD SGT GWYNGGLGGAKFQVAE Y SRIAAVF------------LAGT DA III- II I I - I - I --------gjYi----GA-------------FME PGDNVS VTEHIi VGE - A LQLRIYAQKPDNTIQEYM----------WHGDGWKEG----TNLGGALPG --- I -I I I -I- I I --I II IHIRVYA-----------STGrTTTEWCHIiGNGHTKGAYTArN------- TGI GATS FRYTDYNGPSIRIHFQTDDLKLVÜRAYD PHKGWYPDL VTI FDR a.PERTAIAAT SFGAGHS SIYMRIY FVNS DHTIHijVCtfDHGKGYHDKGT IT PVIiG S2VAI: SPSS FÄHNG ?DL RlYFÍÍTG" YISAVS EFffiNilAEGS w L 3 REAL?PA 314 50 ; B3 34 151 if 157 207 257 307 lfi/3£l (ll-Z*) 19/3Í1 (15.3*) 13/3Í1 CJ4.1ft) Skore:108% 1 aTPGAQQUXETťEGIAAVJniTiniUnTY^ 50 i-------------------------------------------------- a 51 VI GNAKL&a FV- - AiT 5-HZLKHIEVYTLTEGNTLQEEAYD3GTGinfNGG 37 I . I I I I I - . . . I I I I I - - - I - : - I - - : I I . I I I - I - 1--------55VQfIAAT5WGTVP5IEVYT51JHlSlL—ITERCWL—GEGKTTGA 40 93 LGGflEFŮVAETfSRIAiVETLAGTDALCERriraOEEDbíTIQEYMlfHGDGlfEÍE HI .......I : . . I : I . I : I ; - ; I ; I I ----I . . I ::. I : I : I I . : 41 nTEPSDHVaVTa-----^VGS-AIHIP^YA-STGTTTTElJCliDGrGirZK a a L43 G----Tm/JS^PCTGIGATSETiyTDlfHlSESritlHFQTDDLELVQRiTDP 193 I I I 34 GAYTATH------------------------------------------- 90 L94 HKGlTfPDCLVTinjRAPERTAIAATSE^ajGHSSIYHllI^ 243 91-------------------------------------------------- 90 !44 FDHGKGYHEKÍíI IT PUEQG5EVAI ISH&SFMJWGPDLRLYFQHGTYISAV 293 91-------------------------------------------------- 90 !94 aEFVFHHAHGaOSLGRaALBPA 314 91--------------------- 90 Nelze však spoléhat na zdánlivě dobrá řešení PLLSASIVSAPWTSETYVDIPGLYLDVAKAGIRDGKLQVILNVPTPYATGNNFPGIYFAIATNQGWADGCFTYSSKV PESTGRMPFTLVATIDVGSGVTFVKGQWKSVRGSAMHIDSYASLSAIWGTAAPSSQGSGNQGAETGGTGAGNIG GGGERDGTFNLPPHIKFGVTALTHAANDQTIDIYIDDDPKPAATFKGAGAQDQNLGTKVLDSGNGRVRVIVMANGR PSRLGSRQVDIFKKSYFGIIGSEDGADDDYNDGIVFLNWPLG ERDGTFNLPPHIKFGVTALTHAANDQTIDIYIDDDPKPAATFKGAGAQDQNLGTKVLDSGNGRVRVIVMANGRPSR LGSRQVDIFKKSYFGIIGSEDGADDDYNDGIVFLNWPLGPLLSASIVSAPWTSQTYVDIPGLYLDVAKAGIRDGKLQ VILNVPTPYATGNNFPGIYFAIATNQGWADGCFTYSSKVPESTGRMPFTLVATIDVGSGVTFVKGQWKSVRGSAM HIDSYASLSAIWGTAAPSSQGSGNQGAETGGTGAGNIGGGGKLAAALEIKRASQPELAPEDPEDVEHHHHHH 1 e::e;;j_ úú1 1 e::e;;j_ 1 e::e;;j_ úú1 51 e::e;;j_ úú1 1 e::e;;j_ úú1 Lul e::e;;j_ úú1 ii e::e;;j_ . — - L5L elie;* 5 00.1 f ŕ 001 201 e:cezh úul L36 e:cezh úul 1=^1 e:cezh úul LEĚ e:cezh úul l~l e:cezh úul 2sě e:cezh úul 2s4 51 GTLGTKVLDSGtTCKVFIVXVM^GElPaHXGaHC^DI FKK3YEGIIG5EĽGM] ---------------ELL3Ä3IV3Ä.PWIľaEmjDI PSLYĽDVARAGrEIl 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 DDY^Gr^LtWPLGELL3A3IV3AFVVT3^rY7DIESniYIJ^VJďAGIRII GMLÍ^riJSrraiEYÄTG^FPGITFAIÄTWaGWiDOCETYa SE7EE ETGE 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 GMLÍ^riJSrraiEYňTGJSmFPGIYFAIATWaGWADOCETYa S KYPE ETGR i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i ii II I I I I II GSGfc^G^TGGTGÍAGMIGGGGEPJjGrFNLPPHIKEXjVTÄLTHAAirDCIľ ID i i i i i i i i i i i i i i i i i i i i i g 3g:jiqgaz:tggtg!íghi gggg----------------------------- rYIDDDPBjPÄ^JFEJGÄJGÄQDQrnjGTTEVLDaGNGIl^plvi^HilíGRP 3PJ1GS i - i i: i - - i 1:1 -------KLASA----------LEI K-----------------PAS---- : : . i i . . i . : . : . -LAPEDPEDVEHKH- D 51' D IQ G .s; 1í5 1ž5 :_i :ží Lokálně podobné sekvence eedle 1 -------------------------------adsqtssn----------- 8 . . I I . I . I 101 tfvkgqwksvrgsamhidsyaslsaiwgtaapssqgsgnqgaetggtgag 150 9 -------ragefsippntdfraiffanaaeqqhiklfigdsqepaayhk- 50 I . I . I : : I I : . . I......: I I . . I . I . : : I . I . . : I I I . . I 151 niggggerdgtfnlpphikfgvtalthaandqtidiyidddpkpaatfkg 200 51 -------lttrdgpreatlnsgngkirfevsvngkpsatdarlapingkk 93 I . I : . I : I I I I : : I . . I . . I I : I I . . . : I . . . I | | 201 agaqdqnlgtk------vldsgngrvrvivmangrpsrlgsrqvdi-fkk 2 43 9 4 sdgspftvnfgivvsedghdsdyndgivvlqwpig 12 8 I . I I I : . I I I I . I . I I I I I I I . I . I I : I 244 s-------yfgiigsedgadddyndgivflnwplg 271 at e r 9 ragefs ippntdfraiffanaaeqqhiklfigdsqepaayhk-------- 50 158 rdgtfnlpphikfgvtalthaandqtidiyidddpkpaatfkgagaqdqn 207 51 lttrdgpreatlnsgngkirfevsvngkpsatdarlapingkksdgspft 100 I . I : . I : I I I I : : I . . I . . I I : I I . . . : I . . . I | | | 208 lgtk------vldsgngrvrvivmangrpsrlgsrqvdi-fkks------ 2 44 101 vnfgivvsedghdsdyndgivvlqwpig 12 8 . I I I : . I I I I . I . I I I I I I I . I . I I : I 245 -yfgiigsedgadddyndgivflnwplg 271 Globálně podobné sekvence Needle pa-iil 1 rs-iil 1 atqgvf tlpantrf gvtafanss gtqtvnvlvnne taatf s gqs tnnavi 5 0 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 : : . : : aqqgvftlpantsfgvtafanaantqtiqvlvdnvvkatftgsgtsdkll 5 0 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 atqgvftlpantrfgvtafans s gtqtvnvlvnne taatf s gqs tnnavi 5 0 rs-iil 1 aqqgvftlpantsfgvtafanaantqtiqvlvdnvvkatftgsgtsdkll 5 0 pa-iil 51 gtqvlnsgssgkvqvqvsvngrpsdlvsaqviltnelnfalvgsedgtdn 100 rs-iil 51 gsqvlnsg-sgaikiqvsvngkpsdlvsnqtilanklnfamvgsedgtdn 99 pa-iil 101 dyndavvvinwplg rs-iil 100 dyndgiavlnwplg 114 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) The BLAST Search Algorithm Query: query word (LV= 3) GS VE DTTG3Q3LAALLNKCKTP QGQRLVNQ1ÜI KQPLMDKNRIEERLH LVE ATVEMEL RQTLQEDL neighborhood words PQG 18 PEG 15 PRC 14 PKO 14 PNG 13 FDG 13 PHC 13 ma 13 FSG 13 PQN 12 tie... neighborhood score threshold (T = 13) Query; 325 SWJO-I^C^TPQGQIU.VHQilJIlí^LHIiKHHIEERĽHLVEA 36E +LA++L+ TP G F++ +W+ P+ B +■ ER 4- A 3bjet: 290 TlJtóÄKWTlMGSmi^WLHMPV^TWLLERuQTIGA 330 High-scoring Segment Pair (HSP) 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. Query sequence: PQGEFG Word 1 PQG Wofd 2: QGE Word 3: GEE Wocd4: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 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 or73 Blast Hits on the Query Sequence y YP_QC2232S17 lectin [Burfcholderia cenocepacia J2315] 5=4SB E=3.9e-173 Color kev for alignment scores =200 i 1 1 i 1 1 i i i i i i i i 1 40 bo 120 1g0 200 ^40 49999999999952 Vystup z BLASTu @ Download ^ GeriPept Graphics fucose-binding lectin II [Bunkriolderia multivorans ATCC BAA-247] Sequence I □: reflZP 15916739.11 Length: 274 Number of Matches: 1 fr See 1 more litlei's) Range 1: 31 to 274 Gemfept Graphics Score 443 -j ts( 1140] Expect Method 4e-155 Compositional matrix adju: Cjuery 2 QPFTHDDIYALLQLAGNDATÄVC Q FFT HDDIYALLQLAGNnA AVt Sbjct 31 Q P FT HDDIYALLQLAGNDARAVC Cjnery £2 SFDVIGSHQHKVKTDAAGEVVACT 5 FDV1GSHQNKVKI DfiAG-l-WACl Sbjct 51 S FDVGSHÜNKVKT DAAGQWACT 120 PAPVPTGGGERDGIFTIPPNIAI P GGGERDG4F IPPNIAI Sbjct 151 PDrATAGGGERDGVFNI PPN I AI 2 iisr y 1B0 LNTQIWSGKGKVRVVVTANGKI LNTQIVNSG GKVRVVVT NGKI Sbjct 211 LNTQIWSGNGKVRVVVTVNGKI Cjuery 240 WPLG 2 43 WPLG Sbjct 271 WPLG 2 74 3 Download " GeriPept Graphics sugar-binding lectin protein [Ralstonia solanacearum PSI07] Sequence ID: neflVP Drj375D856.1| Length: 114 Number of Matches: 1 See 3 morelitl&ts^ Range 1: 3 to 114 GenPfept Graphics T Neri Match Previous Hatch SCOrfi Expect Method Identities Positives (Laps 124bits(312) 2e-32 Compositional matrix adjust. 62/114( 54 77/113(68%) 3/113(2%) Query 132 Gl FT L P PNIAFGVTALVN5 S APQT IE VFVD DM PKPAÄTFQGAGT QDANLNTQIVNSGK-G 190 G4FTLP N FGVTA NSS QT4 V V H 4 AATF G T 4A 4 TQ44NSG G Sbjct 5 GVFT L PANTQ FGVT AFAN 5 S GT QTYNVTV--HNETAÄTFS GQSTHNÄVIGTQVLNSGSSG 62 cilery Sbjct 191 243 KVRVWTANGKP SKIGS RQVTJ IFHKIY FGLVG S EDGGDGDYNDGIAI1NWPLG KV4V V4 NG4PS 4 S QV 4 4 F LVGSEDG D DYND 4 44NWPLG 63 KYQVQVSVNGEP S DLV5 AQVILTNELN FALVG S EDGT DND YND AWVINWPLG 115 F ASTA 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> • • * 4-" 4-' ■ 4-" ■ U ■ 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 kriterií. 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) http://www.ebi.ac.uk/clustalw/ • V současné době nejužívanější program • První verze 1988 Higgins,D.G. and Sharp,P.M. (1988) CLUSTAL: a package for performing multiple sequence alignment on a microcomputer. Gene, 73, 237-244. • Dnes používané verze: Clustal W (Thompson et al., 1994) Clustal X (Jeanmougin et al., 1998) • Využívá progresivní alignment ClustalW: Jednotlivým sekvencím přiřazuje váhy (weight-W) podle četnosti zastoupení (čím více jsou si sekvence podobné, tím nižší mají váhu a naopak) a penalizuje přítomnost mezer v závislosti na jejich pozici (position-specific gap penalties) ClustalW2 - postup 1. Provedení pairwise alignmentů pro každou dvojici sekvencí a určení jejich podobnosti - v závislosti na množství neodpovídajících residuí a mezer 2. Sestavení příbuzenského stromu (similarity tree) 3. Kombinace alignmentů (viz. 1.) v pořadí dle příbuznosti - od nejvíce podobných k nejméně příbuzným (viz. 2.). Jednou vložené mezery jsou zachovány. Clustal W/Clustal X 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 IPPNTdFŔAIFFANAAEQQf LPPNTAFKAIFYANAADRQI LPPNIAFGVTALVNSSAPQ LPPHIKFGVTALTHAANDQ I ^LFIGDSQEPAAYHKLTTRDGaRE—ATLNSGNGKIRFE L Í\LFIDDAPEPAATFVGNSEDG\< ISVFVDDNPKPAATFQGAGTQD2 iblYIDDDPKPAATFKGAGAQDC • • ~k • ~k ~k ~k • ĽJ rl—ftlnskggkirie nlntqivnsgkgkvrvv nIgtkvldsgngrvrvi 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ý príbuzenský strom (tree2) Progresivní alignment (viz bod 3) na základě tree2 - vytvoření druhého M SA Refinement - rozdělení vzniklého stromu na dvě části a vytvoření M SA 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ů unaligned sequences f 1 k-mer counting : OPGMA Y~ T, 3 progressive alignment MSA1 k-me í distance matrix D1 TREE1 2 1 compute %idstrom MSAi MSA2 2.3 progressive ahgnmerst Kimura distance matrix DZ 22 UPGMA i kll^ 3.2 compute subtree profiles 3.3 re-align Profites m ľ a ^l==l 34 SP Kom oeííer p m s a3 NO. delete Yes. SäYB 3. J ctetete ŕdS* trom TREE2 giving 2 subtrees higure 2. This diagram summarizes the flow of the MUSCLE algorithm. There are three main stages; Stage 1 (draft progressive). Stage 2 i improved progressive) and Stage 3 (refinement!. A multiple alignment is available at the completion of each stage, at which point the 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. A = B ■ a- C ■ B. CluMalW Primary iibraiy (Gäiihal Pairwise. Alignment) a. li' A ■ O FS, CI- A-Ii ' B f.1 LaJigti Primary Library (Local I_Painvise Al ignment) I Weighting Signal Addition PRIMARY LIBRARY D EXTENSION EXTENDED LIBRARY J PROGRESSIVE 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 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í) Výhoda: vyšší přesnost Sequences T*mplatř-bas*d alignment 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 !!!