4/22/2009 Chemoinformatika a bioinformatika Sequence alignment Osnova 1. Struktura biomakromolekul - sekvence 2. Alignment a jeho typy 3. Užívané algoritmy 4. Multiple sequence alignment 5. Programové balíky 6. Benchmark- porovnávání alignmentů Struktura proteinů (NK) ADSQTSSNRAGEFSIPPNTDFRAIF FANAAEQQHIKLFIGDSQEPAAYHK LTTRDGPREATLNSGNGKIRFEVSV NGKPSATDARLAPINGKKSDGSPF TVNFGIVVSEDGHDSDYNDGIVVL QWPIG primární (sekvence) l^m tr*4- ---------f^k----------------------i—t---------1 '.--------- u Hat*»?« i.ttfie»™tiji mj^r. iFFT.r.m n M] «4 TO K -■- rm L i sekundárni terciární kvartér ní «í $ i tw* ■ i Wft fe Aminokyseliny ^ Qf Hf F I* ó> U> ii fr™ <*~ Ö> U1 0> ■»V wrV* ■mJtr"^ non-polar / charged /\ small v polar 4/22/2009 Alignment Srovnání (přiložení) dvou či více sekvencí (aminokyselinových, nukleotidových) na základě jejich vzájemné podobnosti. Pairwise alignment - dvě sekvence Multiple sequence alignment - více sekvencí Pair-wise alignment Srovnání dvou sekvencí Sekvence mohou být seřazeny v celé své délce (global alignment) nebo jen v určitém regionu (local alignment). Local alignment Hledá úseky dvou sekvencí, které si podle zvolených kritérií dobře odpovídají. Nesnaží se zahrnout celé sekvence, pokud si jejich některé části neopdovídají. Global alignment Vychází z předpokladu, že obě srovnávané sekvence jsou víceméně shodné v celé své délce. Alignment k sobě přikládá celé sekvence (od počátku do konce) a to včetně částí, které si nepříliš odpovídají. Algoritmy Téměř výhradně se užívají heuristické algoritmy- nalezení výsledku v dostatečně krátkém čase Vývoj algoritmů je prováděn v návaznosti na srovnávání výsledků s tzv. zlatým standardem - alignment na základě známé 3D struktur Vstupní data Sekvence AK (nt) v určitém formátu - dnes desítky formátů, mnohé obsahují krom sekvence i doplňující data Bližší např. http://emboss.sourceforge.net/docsAhemes/SequenceFormats.html FASTA formát >název popis dle vlastní vol by J SEKVENCESEKVENCESEKVENCESEKVENC ESEKVENCESEKVENCE 4/22/2009 Scoring matrix (skórovací matice) Dvě sekvence považujeme za příbuzné, vycházejí-li ze společného předka; pak dobu potřebnou k jejich evoluci můžeme odvodit z množství rozdílů mezi nimi z> Záměna aa je častější než inserce/delece. Pravděpodobnost změny jedné aminokyseliny na jinou je přímo úměrná podobnosti obou aminokyselin. Matice vzniká přiřazením hodnoty (pravděpodobnosti) jednotlivým dvojcím aminokyselin v závislosti na jejich vzájemné „zastupitelnosti" - pravděpodobnosti substituce Typy matic • PAM (Point Accepted Mutation) - založena na mutacích v rámci globálního alignmentu, tj. ve vysoce konzerovovaných i mutabilnlch oblastech. • BLOSSUM (Blocks Substitution Matrix) -je odvozena z vysoce konzervovaných oblasti neobsahujících mezery —> lepši pro lokální alignment. Je využívána v blastp, vhodná pro identifikaci neznámé nukleotidové sekvence. • GÖNNET - vytvořena 1992, postupným opakováním cyklu: pairwise alignment-nová matice-nový pairwise alignment - nová matice... • DNA identity matrix V rámci jednoho typu existuje vice jednotlivých matic založených na stejném principu, které se však liší konkrétními hodnotami a tedy i oblasti použiti (vysoce příbuzné nebo naopak velmi vzdálené sekvence). Matice PAM 250 c 12 G -3 5 P -3 -1 6 A -21112 T -200113 D -51-10004 E -50-100034 N -4 0-110 0212 Q -5-1 0-1 0-1 2 2 1 4 H -3-2 0-1-1-1 11 2 3 6 K -5-2-1 0-1 0 0 0 1 1 0 5 R -4-3 0 0-2-1-1-1 0 1 2 3 6 M I -5 -3 -2 -2 -1 -1-3-2 0-1-2 0 0 2 6 -2 -3 -2 -1 -1 0 -2 -2 -2 -2 -2-2-2 4 2 5 L F -6 -4 -3 -3 -2 -2 -4 -3 -3 -2-2-3-3 2 4 2 6 -4 -5 -5 -3 -4 -3 -6 -5 -4 -5 -2-5-4-1 0 1 2 9 Y 0 -5 -5 -3 -3 -3 -4 -4 -2 -4 0 -4 -5 -2 -2 -1 -1 7 10 W -8 -7 -6 -2 -6 -5 -7 -7 -4 -5 -3 -3 2 -6 -4 -5 -2 0 0 17 CGPSATDEWQHKRVMI L F Y W Matrice BLOSSUM vypadá analogicky, liší se hodnoty. 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. O 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", a to více než substituce. Čím nižší je penalizace mezer, tím lepší (dokonalejší) bude alignment, ovšem z biologického hlediska může jít o nesmysl. Jednotlivé programy obvykle penalizují přítomnost mezery (gap open) a také zvyšují penalizaci s délkou mezery (gap ext). Krátká mezera: ATCTTCAGTGTTTCCCCTGTTTTGCCcftlTTTAGTTCGCTC 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 ATCTTCAGTGTTTCCCCTGTTTTGCCCJlTTTAGTTCGCTC Dlouhá mezera: ATCTTCAGTGTTTCCCCTGTTTTGCCC....................ATTTAGTTCGCTC 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 ATCTTCAGTGTTTCCCCTGTTTTGCCCGCCCCCCCCCCCCCCCCCCCATTTAGTTCGCTC Skóre Každé dvojici sekvencí je ve výsledku přiřazeno číslo - skóre, které určuje míru jejich podobnosti Čím vyšší je skóre, tím vyšší je podobnost. Podle použité matice může být skóre i záporne. Multiple sequence alignment - MSA (mnohonásobné srovnáni) Multiple alignment slouží k: • Nalezení „diagnostického vzoru" (diagnostic patterns) na jehož základě jsou charakterizovány proteinové rodiny • Odhalení či dokázání homologie mezi novou sekvencí a sekvencemi v databázích • Určení vzájemné příbuznosti sekvenci v rámci skupiny -tvorba fylogenetických stromů • Predikci sekundární a terciární struktury nových proteinů • Navržení primem (oligonukleotidů) pro PCR Metody MSA Dynamické programování (dynamic programming) -rozšíření pairwise alignmentu Progresivní alignment (progressive sequence alignment) - nejčastěji používaný k vytvoření alignmentu; využívá fylogenetické informace Iterativní alignment (iterative sequence alignment) -odstraňuje problémy progresivního alignmentu pomocí opakování alignmentu pro podskupiny sekvencí Dynamické programování Simultánní alignment všech sekvencí - analogické pairwise alignmentu Programové balíky: MSA (Lipman et al., 1989) a DCA (Stoye et al., 1997), založené na Carrilově a Lipmanově algoritmu (1988) Využívá skórovací matice, ale vytváří n-rozměrný prostor (n = počet sekvencí) Extrémně náročný na výpočetní kapacity I při zjednodušení nepoužitelné pro více než cca 20 sekvencí Progresivní multiple alignment • Používá ho většina programů • Vznik-1987 Feng, D.-F. and Doolittle, R.F. (1987) J. Mol. Evol. 25, 351-360. 1) sestavení příbuzenského stromu (guide tree) z nepřiložených sekvencí Guide tree vs. phylogenetic tree • Guide tree je vypočítán na základě .dnd soubor matice vzdáleností (distance matrix) vytvořené podle skóre pairwise alignmentu. Výstupem je .dnd soubor. • Phylogenetic tree je vypočten na základě vytvořeného MSA. Vzdálenosti mezi sekvencemi jsou vypočteny a uloženy jako .ph soubor. Následně je možno je využít pro konstrukci fylogenetického stromu (soubory .nj, .ph, .dst) pomocí zvolené metody (nj, phylip, dist). ( ( PAIIĽ0.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 cc mpanson 1 vs. 2 DIST = 0.6491 length = 114 1 vs 3 DIST = 0 6842 length = 114 .nj 1 vs 4 DIST = 0 9298 length = 114 5 DIST = 0 9035 length = 114 Ivs 6 DIST = 0 7 DIST = 0 9386 9825 length = length = 114 114 soubor 2vs 3 DIST = 0 3//2 length = 114 2vs 4 DIST = 0 9123 length = 114 2vs 5 DIST = 0 8947 length = 114 2vs 2vs 6 DIST = 0 7 DIST = 0 9123 9386 length = length = 114 114 3vs 3vs 4 DIST = 0 5 DIST = 0 9123 9386 length = length = 114 114 . | |------ 2 3vs 7 DIST = 0 9474 length = 114 4vs 4vs 5 DIST = 0 6 DIST = 0 9211 9035 length = length = 114 114 ----1 4vs 7 DIST = 0 9649 length = 114 5vs 6 DIST = 0 9561 length = 114 l------------------------4 5vs 7 DIST = 0 9211 length = 114 J 6vs 7 DIST = 0 9649 length = 114 I------------------------6 Neighbor-j oining Method Saitou, N. and Nei, M. (1987) The Neighbor-jo A New Method for Reconstructing Phylogenet ning Method: 7 c 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) oins SEQ 3( 0.19912) Cycle 2 = SEQ: 1 0.34101) oinsNode 2( 0.13706) Cycle 3 = SEQ: 5( 0.44298) oins SEQ 7( 0.47807) Cycle 4 = SEQ: 4( 0.44518) oins SEQ 6( 0.45833) Cycle 5 (Last cycle, trichotomy): Node: 1 ( 0.12171)joi Node: 4( 0.01864)joi Node: 5( 0.02083) .ph soubor ( ( PAIIĽ0.34101, ( RSIIĽ0.17807, CVIIĽ0.19912) :0.13706) :0.12171, ( BCLA:0.44518, BCLC:0.45833) :0.01864, ( BCLB:0.44298, BCLD:0.47807) :0.02083); 7 PAUL RSIIL CVIIL BCLA BCLB BCLC BCLD .dst soubor 0.000 0.649 0.684 0.930 0.904 0.939 0.982 0.649 0.000 0.377 0.912 0.895 0.912 0.939 0.684 0.377 0.000 0.912 0.939 0.930 0.947 0.930 0.912 0.912 0.000 0.921 0.904 0.965 0.904 0.895 0.939 0.921 0.000 0.956 0.921 0.939 0.912 0.930 0.904 0.956 0.000 0.965 0.982 0.939 0.947 0.965 0.921 0.965 0.000 Phylogram a cladogram Phylogram (phylogeny tree) -je rozvětvený diagram (strom), který naznačuje fylogenezi (postupný vývoj). Délka jednotlivých větví je úměrná velikosti změny v průběhu evoluce. Cladogram - rovněž strom, v němž však všechny větve mají stejnou délku. Ukazuje tak sice „společné předky" pro jednotlivé sekvence, ale ne množství změn, jež od té doby prodělaly (evoluční dobu). Phylogram a cladogram Phylogram r 4 i i .. .- i Cladogram ( t ... I i 1----------™ i 4/22/2009 Progresivní multiple alignment • Používá ho většina programů • Vznik-1987 Feng, D.-F. and Doolittle, R.F. (1987) J. Mol. Evol. 25, 351-360. 1) sestavení příbuzenského stromu (guide tree) z nepřiložených sekvencí 2) tvorba párových alignmentů postupně podle příbuznosti (topologie guide tree) • Dnes obsahuje často iterativní smyčku Iterativní přístup (Gotoh, 1996; Notredame & Higgins, 1996) Vzniklý strom i alignment jsou následně optimalizovány do konvergence. Jinakjsou chyby vzniklé při prvním alignmentů (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 zobrazeni a/nebo editaci - Bioedit - JalView - CINEMA 2.1... - JavaShade Programové balíky Existují programy pro pairwise alignment i pro MSA Využívají lokální nebo globální alignment nebo přip. kombinaci obou Neexistuje univerzální „nejlepší" program - záleží na konkrétním použití Pairwise alignment „programy" Oblasti použití: • Přímé porovnání dvou sekvencí Vyhledávání podobných sekvencí v databázích Needle & Water vytvořeny 1970 Needleman S.B. and Wunsch 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í dynamic programming, umožňují vložení mezer Needle-globální pairwise alignment, Needleman-Wunsch algoritmus Water-lokální pairwise alignment, Smith-Waterman algoritmus C ;i obalně podobné sekve ince Needle PA-IIL i ATQGVFTLPAWTRFGVTAFAWSSGTQTVWVLVWWETAATFSGQSTWWAVI 50 RS-IIL i AQQGVFTLPAWTSFGVTAFAWAAWTQTIQVLVDWVVKATFTGSGTSDKLL 50 PA-IIL bl GTQVLWSGSSGKVQVQVSVWGRPSDLVSAQVILTWELWFALVGSEDGTDW 100 RS-IIL 51 GSQVLWSG-SGAIKIQVSVWGKPSDLVSWQTILAWKLWFAMVGSEDGTDW 99 PA-IIL lul DYWDAVVVIWWPLG 114 RS-IIL 100 DYWDGIAVLWWPLG 113 Water PA-IIL 1 ATQGVFTLPAWTRFGVTAFAWSSGTQTVWVLVWWETAATFSGQSTWWAVI 50 RS-IIL 1 AQQGVFTLPAWTSFGVTAFAWAAWTQTIQVLVDWVVKATFTGSGTSDKLL 50 PA-IIL bl GTQVLWSGSSGKVQVQVSVWGRPSDLVSAQVILTWELWFALVGSEDGTDW 100 RS-IIL 51 GSQVLWSG-SGAIKIQVSVWGKPSDLVSWQTILAWKLWFAMVGSEDGTDW 99 PA-IIL 101 DYWDAVVVIWWPLG 114 RS-IIL 100 DYWDGIAVLWWPLG 113 1 nkálnp nnrlnhnp spIo/p nee Needle PA-IIL 0 BCLB 1 SQPFTHDDLYALLQLAGWDATAVQAWGDQAVLDRMRQFMTAQLVEKLPQY 50 PA-IIL 0 BCLB 51 DVFVDIATIPYSFDVGSWQWKVKTDAAGEVVACTVTWAGAPGVLPGAAAK 100 PA-IIL 22 BCLB 101 FGVGAVVWYFSKATPQPVQPAPVPTGGGERDGIFTLPPWIAFGVTALVWS 150 PA-IIL 23 SGTQTVWVLV—WWETAATFSGQSTWWAVIGTQVLWSGSSGKVQVQVSVW 70 BCLB 151 SAPQTIEVFVDDWPKPAATFQGAGTQDAWLWTQIVWSG-KGKVRVVVTAW 199 PA-IIL 71 GRPSDLVSAQVILTWELWFALVGSEDGTDWDYWDAVVVIWWPLG 114 BCLB 200 GKPSKIGSRQVDIFKKTYFGLVGSEDGGDGDYWDGIAILWWPLG 243 Water PA-IIL 4 GVFTLPAWTRFGVTAFAWSSGTQTVWVLV—WWETAATFSGQSTWWAVIG 51 BCLB 132 GIFTLPPWIAFGVTALVWSSAPQTIEVFVDDWPKPAATFQGAGTQDAWLW 181 PA-IIL 52 TQVLWSGSSGKVQVQVSVWGRPSDLVSAQVILTWELWFALVGSEDGTDWD 101 BCLB 182 TQIVWSG-KGKVRVVVTAWGKPSKIGSRQVDIFKKTYFGLVGSEDGGDGD 230 PA-IIL 102 YWDAVVVIWWPLG 114 BCLB 231 YWDGIAILWWPLG 243 BLAST algoritmus Heuristický algoritmus jehož základem je hledání slov (několikapísmenných sekvencí), s dostatečnou podobností (poskytují dostatečně vysoké skóre v substituční matici) The BLAST Search Algorithm qiiíľy.vfdin i- 'jratTTCJ'JlLLkiUB.'J. J 1*^1.1 j%[ ^— rartlhrtthold r0. u f ľ - 1 J> H:gh-í! «ťig Styru-r! P jii |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) • Porovnání slov na základě substituční matice algoritmus BLAST hledá na základě vloženého skóre slova, která jsou podobná každému slovu v zadané sekvenci. Vyhovující slova jsou následně uspořádána. • Prohledání databázových sekvencí Je hledána shoda s nalezenými vysoce podobnými slovy. • Rozšíření slov na segmenty „ Přesné shody slov s databázovými sekvencemi jsou rozšiřovány oběma směry. To pokračuje dokud skóre pro tuto dvojici sekvencí je dostatečně vysoké. Novější verze BLASTu (BLAST2) márnj. níže nastavenu hladinu pro hledání podobných slov, coz rozšiřuje možnost nalezení vzdálenějších homologů. r PQtihHi •W**i CEF Vri l HKJ e K P P Q G L F - :, ;■ f e <■ v ^LMudü -\- : FASTA algoritmus FastA algoritmus nejprve provádí rychlé prohledání pro nalezení odpovídajících sekvencí, následuje _ přesnější porovnání zadané sekvence s databázovou sekvencí. Na rozdíl od algoritmu BLAST jsou zde tolerovány mezery. Proces: Obě porovnávané sekvence tvoří horizontální a vertikální osu grafu. Následně jsou jednotlivá slova z jedné sekvence porovnávána se slovy sekvence druhé. Odpovídající páry pak vytvoří sadu bodů. Body na úhlopříčce signalizují významnou shodu (či podobnost) v daném úseku. Cílem je nalezení nejdelšího shodného úseku (úseku s nejvyšším skóre). V dalších krocích jsou zahrnuty konzervativní změny pro nejlepší úseky z prvního prohledání. Program pak vyhledává možnost spojení více takových úseku (může mezi nimi byt mezera, či jsou na různých diagonálách) a tyto spojené úseky jsou posouzeny z hlediska zadaných kriterií aacggcttacg Příklad porovnání sekvencí GGCTTTCGG a AACGGCTTACG MSA „programy" Za posledních 10 let vzniklo pres 50 MSA programových balíků (Wallace, I. M., 0'Sullivan, O., Higgins, D. G. and Clustal W (Thompson et al., 1994) Clustal X (Thompson et al., 1997) Dialign2 (Morgenstern, 1999) T-Coffee (Notredame et al., 2000) MAFFT(Katohetal., 2002) MUSCLE (Edgar, 2004) Kalign (Lassmann, 2005) Clustal http://www.ebi.ac.uk/clustalw/ • V současné době nejužívanější program • První verze 1988 Higgins, D.G. and Sharp, P.M. (1988) CLUSTAL: a package for performing multiple sequence alignment on a microcomputer. Gene, 73, 237-244. • Dnes používané verze: Clustal W (Thompson et al., 1994) Clustal X (Jeanmougin et al., 1998) • Využívá progresivní alignment ClustalW: Jednotlivým sekvencím přiřazuje váhy (weight -W) podle četnosti zastoupení (čím více jsou si sekvence podobné, tím nižší mají váhu a naopak) a penalizuje přítomnost mezer v závislosti na jejich pozici (position-specific gap penalties) ClustalW2 - postup 1. Provedení pairwise alignmentů pro každou dvojici sekvencí a určení jejich podobnosti - v závislosti na množství neodpovídajících residuí a mezer 2. 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í „konzervovanost" každého sloupce: * - identické residuum ve všech sekvencích - silně konzervovaný sloupec - slabě konzervovaný sloupec IPPNTqFílAIFFANAAEQQKIXLFIGDSQEPAAYHKLTTRDGER]]—ATLNSGNGKIRFE LPPNTAFKAIFYANAADRQI L LPPNIAFGVTALVNSSAPQ' LPPHIK ľ( rVTALTHAANDQ' :lfiddapepaatfvgnsedg\/r: i ]vfvddnpkpaatfqgagtqdan: I3IYIDDDPKPAATFKGAGAQDQN jGTKVLDSGNGRVRVI .--FTLNSKGGKIRIE ,NT QIVN S GKGKVRVV 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: • Sestaveni matice pro každou dvojici sekvenci, určeni jejich „vzdálenosti" a sestaveni matice vzdálenosti (distance matrix) • Na základě distance matrix je sestaven první příbuzenský strom (treel) • Skládáni sekvenci v pořadí dle treel od větvi ke kmenu - v každém rozvětveni je vytvořen profil, který při dalším porovnáváni nahrazuje původní sekvence - výsledkem je první MSA Algoritmus MUSCLE (podobne PRRP a MAFFT) Přepočítáni vzdálenosti sekvenci na základě vzniklého MSA1 -tvorba druhé distance matrix (D2) Na základě D2 sestaven vylepšený príbuzenský strom (tree2) Progresivní alignment (viz bod 3) na základě tree2 - vytvorení druhého MSA Refinement - rozděleni vzniklého stromu na dvě části a vytvorení MSA pro každou z nich. Pokud je výsledný alignment lepší, je zachován. Toto se opakuje do konvergence (žádná další změna nevede k lepšímu výsledku) nebo do určeného počtu kroků v- ; Ihťrc are Éreí dub Mif-fv Slip I ItfcaTl pcfre^v^L Š inipuvitJ pragre---i\ ľ i uihl ^ij^l 1 i re li &j tmu I. A nulaplí J.ifn ,'..j|.,l'l. p ih, . .«ipLihhii cí cv_| snp, p uhi.h prinl Ihr Stynrnľ 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, M U M MALS, MAFFT, aj. Vychází z nejlepších možných aliqnmentů 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/Projects_home_page/t_coffee_home_page (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 Provedeni pairwise alignmentů pro všechny dvojice sekvenci pomoci globálního a pomoci lokálního alignmentů (dve primární knihovny). Jednotlivým pairwise alignmentům je přiřazena váha podle poměru počtu identických residui k celkovému počtu residul. 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 dale použita pro vlastni progresivní alignment. =— ""= ! i = 1 Ž^ŽZ ■-_ ^ f ■ ■ ľ ■■ 11 1. ■■■■■■ 1 ¥ f i ■■ i ■-. i ■ 1 i •: : ■: ■. 1 f 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 i 4P T MTCH i IW modelu Template-based alignment