IV121 Vybrané aplikace informatiky v biologii -Přednáška 6 IV121 Vybrané aplikace informatiky v biologii 3D počítačová grafika Katedra informačních technologií Masarykova Univerzita Brno Stringologie Úvod Základní pojmy Základní algoritmy Algoritmus využívající analýzu hledaného motivu Algoritmus využívající nalýzu prohledávaného řetězce Hledání opakování Tandemové opakování Palindromy Srovnávání dvou sekvencí DP - Needleman-Wunsch Vylepšení pro maximálně k chyb Burrows-Wheeler transform Jaro 2018 Tento projekt je spolufinancován Evropským sociálním fondem a státním rozpočtem České republiky. EVROPSKÁ UNIE INVESTICE DO ROZVOJE VZDELÁVANÍ Outline Stringologie Uvod Základní pojmy Základní algoritmy Algoritmus využívající analýzu hledaného motivu Algoritmus využívající nalýzu prohledávaného řetězce Tandemové opakování Palindromy DP - Needleman-Wunsch Vylepšení pro maximálně k chyb Burrows-Wheeler transform Oblast zájmu IV121 Vybrané aplikace informatiky v biologii -Přednáška 6 ► historie ► pojmy a objekty zájmu ► operace s řetězci ► vzdálenost a podobnost ► datové struktury ► vyhledávání řetězců ► praktické aplikace Stringologie Úvod Základní pojmy Základní algoritmy Algoritmus využívající analýzu hledaného motivu Algoritmus využívající nalýzu prohledávaného řetězce Hledání opakování Tandemové opakování Palindromy Srovnávání dvou sekvencí DP - Needleman-Wunsch Vylepšení pro maximálně k chyb Burrows-Wheeler transform □ S" Historie IV121 Vybrané aplikace informatiky v biologii -Přednáška 6 Fredkin 1960 Trie (prefixový strom Morrison 1968 Radixový strom Weiner 1973 Suffixový strom Appel & Jacobsen 1988 DAWG Pugh 1990 Skiplist Manber & Myers 1991 Sufixové pole Burrows & Wheeler 1994 BW transformace Ukkonen 1995 On/line konstrukce suff. stromu Ferragina&Manzini 2000 FM-index Stringologie Úvod Základní pojmy Základní algoritmy Algoritmus využívající analýzu hledaného motivu Algoritmus využívající nalýzu prohledávaného řetězce Hledání opakování Tandemové opakování Palindromy Srovnávání dvou sekvencí DP - Needleman-Wunsch Vylepšení pro maximálně k chyb Burrows-Wheeler transform Podrobné informace IV121 Vybrané aplikace informatiky v biologii -Přednáška 6 M AlgoríDuns TDaHime CrodiemorE IKojciecli Butler Stringologie Úvod Základní pojmy Základní algoritmy Algoritmus využívající analýzu hledaného motivu Algoritmus využívající nalýzu prohledávaného řetězce Hledání opakování Tandemové opakování Palindromy Srovnávání dvou sekvencí DP - Needleman-Wunsch Vylepšení pro maximálně k chyb Burrows-Wheeler transform Podrobné informace IV121 Vybrané aplikace informatiky v biologii -Přednáška 6 Hans-Joachim Bockenhauer ■ Oírk BongarU Algorithmic Aspects of Bioinformatics Springer Stringologie Úvod Základní pojmy Základní algoritmy Algoritmus využívající analýzu hledaného motivu Algoritmus využívající nalýzu prohledávaného řetězce Hledání opakování Tandemové opakování Palindromy Srovnávání dvou sekvencí DP - Needleman-Wunsch Vylepšení pro maximálně k chyb Burrows-Wheeler transform Základní pojmy IV121 Vybrané aplikace informatiky v biologii -Přednáška 6 abeceda {e, a, c, g, t} řetězec/sekvence aaggtacgcgt podsekvence aaggtacgcgt podřetězec aaggtacgcgt prefix gtacg cgt gt t suffix cgt at gtacg Stringologie Úvod Základní pojmy Základní algoritmy Algoritmus využívající analýzu hledaného motivu Algoritmus využívající nalýzu prohledávaného řetězce Hledání opakování Tandemové opakování Palindromy Srovnávání dvou sekvencí DP - Needleman-Wunsch Vylepšení pro maximálně k chyb Burrows-Wheeler transform □ S? Základní operace IV121 Vybrané aplikace informatiky v biologii -Přednáška 6 konkatenace x=cggat y=att x.y=cggatatt průnik x=cggat y=att Over(x,y)=at Sjednocení x=cggat y=att (x,y)=cggatt projekce x=cnggatx Z= (e, a, c, g, t) ľl^ (x) =cggat oddělení (zprava/zleva) x=cggat x/t=cgga odstranění (zprava/zleva) x=cggat x-=-a=cggt Stringologie Úvod Základní pojmy Základní algoritmy Algoritmus využívající analýzu hledaného motivu Algoritmus využívající nalýzu prohledávaného řetězce Hledání opakování Tandemové opakování Palindromy Srovnávání dvou sekvencí DP - Needleman-Wunsch Vylepšení pro maximálně k chyb Burrows-Wheeler transform □ S" Datové struktury pro práci s řetězci ► seznam (prostý, skip-list) ► strom (trie, Radixový strom, suffixový strom,metrický strom) ► acyklický graf (DAWG, GAD DAG) ► transformovaná pole (invertovaný soubor, suffixové pole, transf. Burrows-Wheeler, FM-index) ► automaty Míry podobnosti řetězců IV121 Vybrané aplikace informatiky v biologii -Přednáška 6 ► ► ► ► ► ► ► ► Editační a podobné vzdálenosti Hammingova Levenshtein Damerau-Levenshtein ► Jaro-Winkler Podobnost na bázi n-gramů ► Jaccardův index, Diceův koeficient kosinová vzdálenost vzájemná informace Lee-ův koeficient Inverzní číslo Soundex Počet spol. n-gramů nebo slov LCS (nejdelsi spol. podřetězec) ► ► Stringologie Úvod Základní pojmy Základní algoritmy Algoritmus využívající analýzu hledaného motivu Algoritmus využívající nalýzu prohledávaného řetězce Hledání opakování Tandemové opakování Palindromy Srovnávání dvou sekvencí DP - Needleman-Wunsch Vylepšení pro maximálně k chyb Burrows-Wheeler transform Algoritmy pro práci s řetězci IV121 Vybrané aplikace informatiky v biologii -Přednáška 6 Stringologie Úvod Základní pojmy Základní algoritmy Algoritmus využívající analýzu hledaného motivu Algoritmus využívající nalýzu prohledávaného řetězce ► vyhledávání vzorů v jedněm řetězci ► vyhledávání vzorů ve více řetězcích (LCR LCS, SCS) ► vyhledávání přibližných vzorů ► komprese (slovníková, statistická) Hledaní opakovaní Tandemové opakování Palindromy Srovnávání dvou sekvencí DP - Needleman-Wunsch Vylepšení pro maximálně k chyb Burrows-Wheeler transform □ s Výskyt sekvenčních motivů v genomech a databázích Cílem je zjistit všechny pozice delšího řetězce, na kterých se vyskytuje kratší řetězec ► přesný výskyt ► přibližný výskyt ► vzdálenost (k-NN, podobnostní práh) ► vzorec (RE) řetězec t dlouhý (n), např genomová sekvence motiv p krátký (m), např cgcggctggtggctcg Naivní algoritmus IV121 Vybrané aplikace informatiky v biologii -Přednáška 6 actgtgtatgaaatcgc i..n —> t g t c a 1. .m -y Stringologie Úvod Základní pojmy Základní algoritmy Algoritmus využívající analýzu hledaného motivu Algoritmus využívající nalýzu prohledávaného řetězce Hledání opakování Tandemové opakování Palindromy Srovnávání dvou sekvencí DP - Needleman-Wunsch Vylepšení pro maximálně k chyb Burrows-Wheeler transform Složitost: O(mn) Algoritmus Rabin-Karp IV121 Vybrané aplikace informatiky v biologii -Přednáška 6 1. .n actgtgtatgaaatcgc ->* t g t c a h(1..m) = h(i..i+m-1) Porovnávání znaků je nahrazeno porovnáváním hodnot vhodné "hešovací"funkce. Např: hodnota ASCII znaků v prvočíselné bázi (101) Složitost: O(mn) Stringologie Úvod Základní pojmy Základní algoritmy Algoritmus využívající analýzu hledaného motivu Algoritmus využívající nalýzu prohledávaného řetězce Hledání opakování Tandemové opakování Palindromy Srovnávání dvou sekvencí DP - Needleman-Wunsch Vylepšení pro maximálně k chyb Burrows-Wheeler transform Knuth-Morris-Pratt algorithm IV121 Vybrané aplikace informatiky v biologii -Přednáška 6 ctgtgtatgaaatcgc Stringologie Úvod Základní pojmy Základní algoritmy Algoritmus využívající analýzu hledaného motivu Algoritmus využívající nalýzu —>* g t g c c t prohledávaného řetězce -j" -j" -j" X Hledání opakování Tandemové opakování Palindromy máme v motívu předchozí výskyt g, t g nebo gtg? J j -> -> -i -i Dp Need|eman_Wunsch actgtgtatgaaatcgc Burrows-Wheeler transform + 3—gtgcct Složitost konstrukce: 0{\\abeceda\\.vr\) hledání: O(mn) (v praxi ale blíže k O(n)) Boyer-Moore IV121 Vybrané aplikace informatiky v biologii -Přednáška 6 a c t g t g t a t gaaatcgc —>* g a t c a t x t t <- máme v motívu další t ? actgtgtatgaaatcgc + 1 —>* gat cat kde máme v motívu další výskyt suffixu a t ? a c t g t g t a t gaaatcgc +3 ^ g a t cat Realizujeme krok, který je větší Složitost konstrukce: 0{\\abeceda\\.\n) hledání: O(mn) (v praxi ale blíže k O(n)) Stringologie Úvod Základní pojmy Základní algoritmy Algoritmus využívající analýzu hledaného motivu Algoritmus využívající nalýzu prohledávaného řetězce Hledání opakování Tandemové opakování Palindromy Srovnávání dvou sekvencí DP - Needleman-Wunsch Vylepšení pro maximálně k chyb Burrows-Wheeler transform Automat pro hledání řetězce aba IV121 Vybrané aplikace informatiky v biologii -Přednáška 6 Stringologie Úvod Základní pojmy Základní algoritmy Algoritmus využívající analýzu hledaného motivu Algoritmus využívající nalýzu prohledávaného řetězce Hledání opakování Tandemové opakování Palindromy Srovnávání dvou sekvencí DP - Needleman-Wunsch Vylepšení pro maximálně k chyb Burrows-Wheeler transform Automat vytvořen z motivu p postupně čte symboly z řetězce m. Koncový stav automatu dosáhneme po načtení celého hledaného motivu. t=bababaa p=aba IV121 Vybrané aplikace informatiky v biologii -Přednáška 6 € 0 b 0 ba 1 bab 2 baba 3 babab 2 bababa 3 bababaa 1 Stringologie Úvod Základní pojmy Základní algoritmy Algoritmus využívající analýzu hledaného motivu Algoritmus využívající nalýzu prohledávaného řetězce Hledání opakování Tandemové opakování Palindromy Srovnávání dvou sekvencí DP - Needleman-Wunsch Vylepšení pro maximálně k chyb Burrows-Wheeler transform Složitost konstrukce: naivní 0(at73); optimální 0(\\abeceda\\.\n) hledání: O(n) Suffixový strom pro řetězec dabdac IV121 Vybrané aplikace informatiky v biologii -Přednáška 6 Stringologie Úvod Základní pojmy Základní algoritmy Algoritmus využívající analýzu hledaného motivu Algoritmus využívající nalýzu prohledávaného řetězce Hledání opakování Tandemové opakování Palindromy Srovnávání dvou sekvencí DP - Needleman-Wunsch Vylepšení pro maximálně k chyb Burrows-Wheeler transform Kompaktní suffixový strom pro řetězec aaabbbc IV121 Vybrané aplikace informatiky v biologii -Přednáška 6 Stringologie Úvod Základní pojmy Základní algoritmy Algoritmus využívající analýzu hledaného motivu Algoritmus využívající nalýzu prohledávaného řetězce Hledání opakování Tandemové opakování Palindromy Srovnávání dvou sekvencí DP - Needleman-Wunsch Vylepšení pro maximálně k chyb Burrows-Wheeler transform 00 Konstrukce: O(n.iogn) Hledání: 0(m.l|ajbeceda||+k) DAWG IV121 Vybrané aplikace informatiky v biologii -Přednáška 6 A - B - L - A -T abject abjection abjections abjectly abjectness ablate ablated ablation Stringologie Úvod Základní pojmy Základní algoritmy Algoritmus využívající analýzu hledaného motivu Algoritmus využívající nalýzu prohledávaného řetězce Hledání opakování Tandemové opakování Palindromy Srovnávání dvou sekvencí DP - Needleman-Wunsch Vylepšení pro maximálně k chyb Burrows-Wheeler transform ablations Sufixové pole - ukazovatele na polohy suffixů seřazené lexikograficky Dlouho bylo považováno za méně kvalitní datovou strukturu, protože neobsahuje přímo informace o společných prefixech. Ty lze vsak spočítat do lep pole (least common prefix) tak, že konstrukce pole i stromu má stejnou složitost. t = dabdac sa(t) = 6,1,4,2,5,0,3 rank(t) = 5,1,3,6,2,4,0 lcp(t) = 0,0,1,0,0,0,2 6 0 1 0 abdac 4 1 ac 2 0 bdac 5 0c 0 0 dabdac 3 2 dac IV121 Vybrané aplikace informatiky v biologii -Přednáška 6 Stringologie Úvod Základní pojmy Základní algoritmy Algoritmus využívající analýzu hledaného motivu Algoritmus využívající nalýzu prohledávaného řetězce Hledání opakování Tandemové opakování Palindromy Srovnávání dvou sekvencí DP - Needleman-Wunsch Vylepšení pro maximálně k chyb Burrows-Wheeler transform Outline Úvod Základní pojmy Základní algoritmy Algoritmus využívající analýzu hledaného motivu Algoritmus využívající nalýzu prohledávaného řetězce Hledání opakování Tandemové opakování Palindromy DP - Needleman-Wunsch Vylepšení pro maximálně k chyb Burrows-Wheeler transform Tandemová a palindromická opakování nesou biologický i praktický význam palindrom možná sekundární struktura DNA nebo RNA tandem regulace genů, telomery, identifikace jedinců z DNA Nejdelší společný prefix dvou pozic IV121 Vybrané aplikace informatiky v biologii -Přednáška 6 tgcagaagcagatcctgacg t t Stringologie Úvod Základní pojmy Základní algoritmy Algoritmus využívající analýzu hledaného motivu Algoritmus využívající nalýzu prohledávaného řetězce Hledání opakování Tandemové opakování Palindromy Srovnávání dvou sekvencí DP - Needleman-Wunsch Vylepšení pro maximálně k chyb Burrows-Wheeler transform Složitost naivního algoritmu 0(a?3) Posuzování tandemových opakování pomocí suffixových stromů, příp. polí (t=dabdac) IV121 Vybrané aplikace informatiky v biologii -Přednáška 6 Stringologie Úvod Základní pojmy Základní algoritmy Algoritmus využívající analýzu hledaného motivu Algoritmus využívající nalýzu prohledávaného řetězce Hledání opakování Tandemové opakování Palindromy Srovnávání dvou sekvencí DP - Needleman-Wunsch Vylepšení pro maximálně k chyb Burrows-Wheeler transform lcp(1,4)=? Nalezneme větve označené 1 a 4 lcp(1,4)=da Hledání tandemových opakování IV121 Vybrané aplikace informatiky v biologii -Přednáška 6 ► konstrukce stromu: 0(n./ogn) ► hledání lep pro dvě konkrétní pozice O(n.togn) ► Prohledávání sekvence Stringologie Úvod Základní pojmy Základní algoritmy Algoritmus využívající analýzu hledaného motivu Algoritmus využívající nalýzu prohledávaného řetězce Hledání opakování Tandemové opakování Palindromy Srovnávání dvou sekvencí DP - Needleman-Wunsch Vylepšení pro maximálně k chyb Burrows-Wheeler transform Složitost: 0(n.(/ogA7)2+p) Palindromy - nejdelší společný prefix mezi originální a komplementární sekvencí umožňuje urychlení hledání podobně jako pro tandemové opakování i 8 tgcagaag a c g t c t t cttctgtctgacg cgaagacagactgc t 9* Složitost naivního algoritmu 0(a?3) IV121 Vybrané aplikace informatiky v biologii -Přednáška 6 Stringologie Úvod Základní pojmy Základní algoritmy Algoritmus využívající analýzu hledaného motivu Algoritmus využívající nalýzu prohledávaného řetězce Hledání opakování Tandemové opakování Palindromy Srovnávání dvou sekvencí DP - Needleman-Wunsch Vylepšení pro maximálně k chyb Burrows-Wheeler transform Složitost naivního algoritmu O(nlp) (pro omezenou vzdálenost a délku) Složitost s použitím suffixových struktur O(n) Využití DP pro identifikaci palindromů IV121 Vybrané aplikace informatiky v biologii -Přednáška 6 I P P i S S i s s i m m i s s i s s i p p i 0 0 0 0 1 0 0 X 1 0 0 1 X 0 0 1 1 2 1 0 0 x 1 2 3 2 0 0 1 X 1 2 3 0 0 1 1 1 1 2 3 0 0 x 1 1 1 2 2 3 0 0 1 x 1 1 1 2 2 0 1 1 2 1 1 2 1 1 2 3 match b c d d = min a a+1 b + 1 c + 1 match mismatch insertion deletion Stringologie Úvod Základní pojmy Základní algoritmy Algoritmus využívající analýzu hledaného motivu Algoritmus využívající nalýzu prohledávaného řetězce Hledání opakování Tandemové opakování Palindromy Srovnávání dvou sekvencí DP - Needleman-Wunsch Vylepšení pro maximálně k chyb Burrows-Wheeler transform a) b) Využití SA a LCP k rychlému postupu po diagonále i P P i s s i s s i m m i s s i s s i p p i 0 0 0 0 1 0 0 \ 1 0 0 1 0 0 1 1 2 1 0 0 \ N 2 3 2 0 0 1 E- s S 2 3 0 0 1 S S \ N 1 2 3 0 0 s- \ \ N \ L \ s \ s 2 2 3 0 0 1 s- s \ v1 s s s 2 2 0 1 1 2 1 2 1 2 3 —► Longest Common Prefix - -► Neighboring cells with worse scores a) Suffix Array Height Array Cartesian Tree IV121 Vybrané aplikace informatiky v biologii -Přednáška 6 Stringologie Úvod Základní pojmy Základní algoritmy Algoritmus využívající analýzu hledaného motivu Algoritmus využívající nalýzu prohledávaného řetězce Hledání opakování Tandemové opakování Palindromy Srovnávání dvou sekvencí DP - Needleman-Wunsch Vylepšení pro maximálně k chyb Burrows-Wheeler transform b) Outline Úvod Základní pojmy Základní algoritmy Algoritmus využívající analýzu hledaného motivu Algoritmus využívající nalýzu prohledávaného řetězce Tandemové opakování Palindromy Srovnávání dvou sekvencí DP - Needleman-Wunsch Vylepšení pro maximálně k chyb Burrows-Wheeler transform Výpočet omezeného počtu buněk v tabulce DP Stačí počítat 2k+1 diagonál bez ohledu na délku sekvencí IV121 Vybrané aplikace informatiky v biologii -Přednáška 6 Stringologie Úvod Základní pojmy Základní algoritmy Algoritmus využívající analýzu hledaného motivu Algoritmus využívající nalýzu prohledávaného řetězce Hledání opakování Tandemové opakování Palindromy Srovnávání dvou sekvencí DP - Needleman-Wunsch Vylepšení pro maximálně k chyb Burrows-Wheeler transform Složitost: O(kn) (naproti O(mn)) Tabulka pro algoritmus dynamického programování (A) i s A L I G N E D 0 -4 -8*- 12 *- 16*- 20*- 24*- 28*- 32*- 36 Y T -4 -1 -3* -7 *- 11*- 15*- 19*- 23*- 27*- 31 4 4^ N* H -8 -5 -2 -5 13*- 17*- 18*- 22*- 26 4 I -12 -4 -6 -3 -3 -5* -9*- 13*- 17*- 21 1 4 S -16 -8 0 * -4 -5 -5 -5* -8*- 12*- 16 1 4 L -20 - 12 -1 0 -3 -7 * -8 - 11 *- 15 1 4 4 I -24 - 16 -8 -5 1 4 * 0* -4* -8*- 12 4 4 4 4 N -28 - 20 - 12 -9 -3 0 4 6 * 2 * -2 1 4 4 4 4 4^ N E -32 - 24 - 16 - 13 -7 -4 G 4 11 * 7 (B) THIS-LI-NE---ISALIGNED IV121 Vybrané aplikace informatiky v biologii -Přednáška 6 Stringologie Úvod Základní pojmy Základní algoritmy Algoritmus využívající analýzu hledaného motivu Algoritmus využívající nalýzu prohledávaného řetězce Hledání opakování Tandemové opakování Palindromy Srovnávání dvou sekvencí DP - Needleman-Wunsch Vylepšení pro maximálně k chyb Burrows-Wheeler transform □ S1 Využití SA a LCP k rychlému postupu po diagonále Složitost: 0(/c2) (viz pou/vzit/'i pro palindromy) IV121 Vybrané aplikace informatiky v biologii -Přednáška 6 Stringologie Úvod Základní pojmy Základní algoritmy Algoritmus využívající analýzu hledaného motivu Algoritmus využívající nalýzu prohledávaného řetězce Hledání opakování Tandemové opakování Palindromy Srovnávání dvou sekvencí DP - Needleman-Wunsch Vylepšení pro maximálně k chyb Burrows-Wheeler transform BWT - Burrows-Wheeler transform IV121 Vybrané aplikace informatiky v biologii -Přednáška 6 Transformation Input All Rotations Sorting All Rows in Alphabetical Order by their first letters Taking Last Column Output Last Column _--------------i I ^BANANA@ i j (T BANANA ; j AťTBANAN ; Í NAťTBANA j ; ANAÍTBAN Í ■ NANAť^BA : I ANANAS B : j BANANA^ j i____ ____ _i ; ANANAS B J AN A^ BAN I A^ BAN AN ! BANANA^ | ! NANA(TBA i ; NA^BANA ; : ABANANA@ : J @ABANANA j i _ _____ ____ ____ ____ _____i _--------------1 Í ANANAÍTB Í j ANAíTBAN ; A(T BANÁN ; i BANANAS j ; NANAÍTBA Í ; NAÍ^BANA : : ^BANANAg : (T BANANA j i__ _____ __i j ^BANANA@ ; ■"--------------1 j BNN^AAfaA i Stringologie Úvod Základní pojmy Základní algoritmy Algoritmus využívající analýzu hledaného motivu Algoritmus využívající nalýzu prohledávaného řetězce Hledání opakování Tandemové opakování Palindromy Srovnávání dvou sekvencí DP - Needleman-Wunsch Vylepšení pro maximálně k chyb Burrows-Wheeler transform BWT IV121 Vybrané aplikace informatiky v biologii -Přednáška 6 Inverse Transformation Input BNN^AA^A Add 1 Sort 1 B N N A A @ A A A A B N N Add 2 BA NA NA ^B AN AN