IV121 Vybrané aplikace informatiky v biologii -Přednáška 4 Stringologie IV121 Vybrané aplikace informatiky v biologii Stringologie a podobnost řetězců Základní pojmy Základní algoritmy Algoritmus využívající nalýzu prohledávaného řetězce Hledání opakování Tandemové opakování Palindromy Srovnávání dvou sekvencí Vylepšení pro maximálne k chyb Bu rrows-Wheeler transform Katedra informačních technologií Masarykova Univerzita Brno Jaro 2012 Stringologie 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 Oblast zájmu IV121 Vybrané aplikace informatiky v biologii -Přednáška 4 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í Vylepšení pro maximálne k chyb Bu rrows-Wheeler transform Historie IV121 Vybrané aplikace informatiky v biologii -Přednáška 4 1960 Trie (prefixový strom 1968 Radixový strom 1973 Suff ixový strom 1988 DAWG 1990 Skiplist 1991 Sufixové pole 1994 BW transformace 1995 On/line konstrukce uffixového stromu 2000 FM-index Rtiingologie Úvod Základní pojmy /řv t g t c a . Srovnávání dvou sekvencí Vylepšení pro maximálne k chyb Burrows-Wheeler transform Složitost: O(mn) Algoritmus Rabin-Karp IV121 Vybrané aplikace informatiky v biologii -Přednáška 4 a c g t a t c a gaaatcgc Stringologie Úvod Základní pojmy Základní algoritmy Algoritmus využívající analýzu hledaného motivu Algoritmus využívající nalyzu prohledávaného řetězce Hledání opakování Tandemové opakování Palindromy Srovnávání dvou sekvencí Vylepšení pro maximálne k chyp Bu rrows-Wheeler transform 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) Knuth-Morris-Pratt algorithm IV121 Vybrané aplikace informatiky v biologii -Přednáška 4 actgtgtatgaaatcgc —> g t g c c t T T T x máme v motivu předchozí výskyt g, tg nebo gtg? actgtgtatgaaatcgc + 3 ^ gtgcct Stringologie Základní pojmy Základní algoritmy Algoritmus využívající nalýzu prohledávaného řetězce Hledání opakovaní Tandemové opakování Palindromy Srovnáváni dvou sekvencí Vylepšení pro maximálně k chyb Bu rrows-Wheeler transform Složitost konstrukce: 0(\\abeceda\\.m) hledání: O(mn) (v praxi ale blíže k O(n)) Boyer-Moore IV121 Vybrané aplikace informatiky v biologii -Přednáška 4 a c t g t g t a t gaaatcgc —> g a t c a t x t T ^ máme v motivu další t ? actgtgtatgaaatcgc +l^gatcat kde máme v motívu další výskyt suffixu at ? 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\\.m) hledání: O(mn) (v praxi ale blíže k O(n)) Stringologie Základní pojmy Základní algoritmy Algoritmus využívající nalýzu prohledávaného řetězce Hledání opakování Tandemové opakování Palindromy Srovnávání dvou sekvencí Vylepšení pro maximálně k chyb Bu rrows-Wheeler transform Automat pro hledání řetězce aba IV121 Vybrané aplikace informatiky v biologii -Přednáška 4 b a 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í Vylepšení pro maximálne k chyb Bu rrows-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 4 e 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í nalyzu prohledávaného řetézce Hledání opakování Tandemové opakování Palindromy Srovnávání dvou sekvencí Vylepšení pro maximálne k chyp Bu rrows-Wheeler transform Složitost konstrukce: naivní 0(m3); optimální 0(\\abeceda\\.m) hledání: O(n) Suffixový strom pro řetězec dabdac IV121 Vybrané aplikace informatiky v biologii -Přednáška 4 Stringologie Úvod Základní pojmy /nkladní 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í Vylepšení pro maximálně k chyb Burrows-Wheeler translorm Kompaktní suffixový strom pro řetězec aaabbbc IV121 Vybrané aplikace informatiky v biologii -Přednáška 4 Stringologie Základní pojmy Základní algoritmy Algoritmus využívající nalýzu prohledávaného řetězce Hledání opakování Tandemové opakování Palindromy Srovnávání dvou sekvencí Vylepšení pro maximálně k chyb Bu rrows-Wheeler transform (b) Konstrukce: O(n.logn) Hledání: 0(m.\\abeceda\\+W) DAWG IV121 Vybrané aplikace informatiky v biologii -Přednáška 4 Stringologie A - B i -L D J — E - C N * E - S —| O L -A -T abject abjection abjections abjectly abjectness ablate ablated ablation ablations Základní pojmy Základní algoritmy Algoritmus využívající nalýzu prohledávaného řetězce Hledání opakování Tandemové opakování Palindromy Srovnávání dvou sekvencí Vylepšení pro maximálne k chyb Bu rrows-Wheeler transform 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 4 Stringologie Úvod Základní pojmy Základní algoritmy Algoritmus využívající anatyzu hledaného motivu Algoritmus využívající natyzu prohledávaného řetézce Hledání opakování Tandemové opakování Palindromy Srovnávání dvou sekvencí Vylepšení pro maximálne k chyp Burrows-Wheeler transform 4 & * < = > 4 Outline IV121 Vybrané aplikace informatiky v biologii -Přednáška 4 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 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í Vylepšení pro maximálne k chyb Burrows-Wheeler transform Srovnávání dvou sekvencí 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 IV121 Vybrané aplikace informatiky v biologii -Přednáška 4 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í Vylepšení pro maximálne k chyb Burrows-Wheeler transform i □ ► 4 ff ► < -e ► < š ► -šl= -O^O- Nejdelší společný prefix dvou pozic t g c a g a a g c a g a tcctgacg IV121 Vybrané aplikace informatiky v biologii -Přednáška 4 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í Vylepšení pro maximálne k chyb Burrows-Wheeler transform Složitost naivního algoritmu 0(n3) i □ ► 4 (5 ► < ► 4 = > -šl= -O^O- Posuzování tandemových opakování pomocí suffixových stromů, příp. polí (t=dabdac) 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 4 ► konstrukce stromu: 0(n./ogn) ► hledání lep pro dvě konkrétní pozice 0(n./ogn) ► 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í cpaknvání Tandemově opakováni Palindromy Srovnáváni dvou sekvencí Vylepšení pro maximálně k chyb Bu rrows-Wheeler transform Složitost: 0(n.(/ogn)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í t g c a a c g g a a I 8 g c t t c t t c t t c g a a g a g t c a t g a act c g g c T 9* Složitost naivního algoritmu 0(n3) IV121 Vybrané aplikace informatiky v biologii -Přednáška 4 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áni Palindromy Srovnávání dvou sekvencí Vylepšení pro maximálně i: chyb Bu rrows-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) 4 □ ► 4 S ► 4 ^ ► 4 = * _š|= Využití DP pro identifikaci palindromů IV121 Vybrané aplikace informatiky v biologii -Přednáška 4 Stringologie Základní pojmy Základní algoritmy □ match a match a+1 mismatch b + 1 insertion k c + 1 deletion Algoritmus využívající nalyzu prohledávaného řetězce Hledání opakování Tandemové opakování Palindromy Srovnávání dvou sekvencí Vylepšení pro maximálne k chyp Bu rrows-Wheeler transform b) Využití SA a LCP k rychlému postupu po diagonále Longest Common Prefix Neighboring cells with worse scores a) Suffix Array Height Array Cartesian Tree IV121 Vybrané aplikace informatiky v biologii -Přednáška 4 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í Vylepšení pro maximálne k chyb Bu rrows-Wheeler transform b) Outline IV121 Vybrané aplikace informatiky v biologii -Přednáška 4 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 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í Vylepšení pro maximálne k chyb Bu rrows-Wheeler transform Srovnávání dvou sekvencí DP - Needleman-Wunsch Vylepšení pro maximálně k chyb Burrows-Wheeler transform 4 S ► 4 = * 4 = * -šl = -00.0 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 4 Stringologie Úvod Základní pojmy Základni algoritmy Algoritmus využívaj i ci analýzu liledanétiD motivu Algoritmus využívající nalýzu prohledávaného řetězce Hledání opakování Tandemové opakování Pallndromy Srovnávání dvou sekvencí Vylepšení pro maximálně k chyb liurrows-Wheeler transform Složitost: O(kn) (naproti O(mn)) Tabulka pro algoritmus dynamického programování IV121 Vybrané aplikace informatiky v biologii -Přednáška 4 Stringologie Úvod Základní pojmy Základní algoritmy (A) I S A L I G N E D -4 » -s»- 12»- 1ó»- 20»-24»- 28»- 32»- 3ó T -4 -1 -3* -7»- 11»- 15*-19»- 23»- 27»- 31 ML H -5 -2 -5 -9»- 13»-17»- 18»- 22»- 26 V *>» I -1 2 -4 -6 -3 -3 -5* -9»- 13»- 17»- 21 | ."V *v "S N S -16 -S 0 » -4 -5 -5 -5* -8»- 12»- 16 | 1 >» L -2 0 12 -*JL. -1 0 -3 -7 » -8 - 11 »- 1 5 ■s. I -2 4 -8 -5 4 * D * -4» -a»- lí i 1 t N -2 8 20 - -9 -3 0 4 6 » 2 -ŕ -2 1 * •v * *** E -32 - 24 - 16 - 13 -7 -4 □ 4 11 » (B) THIS-LI-NE- II I I II --ISALIGNED Algoritmus využívající nalýzu prohledávaného ŕetézce Hledání opakovaní Tandemové opakování Palindromy Srovnávání dvou sekvencí Vylepšení pro maximálne k chyb Bu rrows-Wheeler transform i □ ► 4 (5 ► < -e ► < ► -šl= -O^O- Využití SA a LCP k rychlému postupu po diagonále IV121 Vybrané aplikace informatiky v biologii -Přednáška 4 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í Vylepšení pro maximálne k chyb Bu rrows-Wheeler transform Složitost: 0(k2) (viz pou/vzit/'i pro palindromy) i □ ► 4 (5 ► < ► 4 = > -šl= -O^O- BWT - Burrows-Wheeler transform IV121 Vybrané aplikace informatiky v biologii -Přednáška 4 Transformation Input All Rotations Sorting All Rows in Alphabetical Taking Output Order by their first letters Last Column Last Column i "BANANA^ i j @" BANANA j i A@"BANAN j NAS"BANA i ANAS"BAN i j NANAS"BA ; I ANANAS"B i i BANANAS" j ANANA@"B i ANAS"BAN AS"BANAN j BANANAS" NANA@"BA i NAS"BANA "BANANAS 6"BANANA ANANA@"B ANAS"BAN AS"BANAN BANANAS" NANAS"BA NAS"BANA "BANANAS S"BANANA "BANANAS i BNN"AASA 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í Vylepšení pro maximálne k chyb Burrows-Wheeler transform BWT IV121 Vybrané aplikace informatiky v biologii -Přednáška 4 Inverse Transformation Input Add 1 BNN"AA@A Sort 1 Add 2 BA NA NA AB AN AN