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 motívu 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álne k chyb Bu rrows-Wheeler transform Jaro 2012 INVESTICE DO ROZVOJE VZDĚLÁVÁNÍ 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 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álne k chyb Bu rrows-Wheeler transform Historie IV121 Vybrané aplikace informatiky v biologii -Přednáška 6 1960 Trie (prefixový strom 1968 Radixový strom 1973 Suffixový 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 /řvdacir ab:r'tmy Algoritmus využívající nalyzu 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 Bu rrows-Wheeler transform Podrobné informace IV121 Vybrané aplikace informatiky v biologii -Přednáška 6 5880 Podrobné informace 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 motívu Algoritmus využívající nalýzu orohledavanelv: irJň?i:'.i Hledání cp-iknvání Tandemové opakováni Palindromy Srovnáváni dvou sekvencí DP - Needleman-Wunsch Vylepšení pro maximálne k chyb Burrows-Wheeler transform Hans Joachim Bockenhaue* ■ Dirk Bongartz Algorithmic Aspects of Bioinformatics Ö Springer 15 S -00.0 Základní pojmy IV121 Vybrané aplikace informatiky v biologii -Přednáška 6 Stringologie Úvod Základni pojmy Základni algoritmy abeceda {e,a,c,g,t} řetězec/sekvence aaggtaegegt podsekvence aaggtaegegt podřetězec aaggtaegegt prefix gtacgcgtgtt suffix egtatgtaeg Algor Im.,:- vy..í vajici natýzu prohledá váného řetězce Hledáni opakování Tandemové opakováni Palindromy Srovnáváni dvou sekvencí DP - Needleman-Wunsch Vylepšeni pro maximálně k chyb Bu rr o ws-W heeler transtorm 1 -0■ t g t c a , Srovnáváni dvou sekvencí DP - Needleman-Wunsch Vylepšení pro maximálně k chyb Burrows-Wheeler transform Složitost: O(mn) 1 -00,0 Algoritmus Rabin-Karp IV121 Vybrané aplikace informatiky v biologii -Přednáška 6 act .„ ->• t g t a t c a gaaatcgc 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áni dvou sekvencí DP - Needleman-Wunsch Vylepšení pro maximálně k chyb Bu rrows-Wheeler transform 1 -00,0 Knuth-Morris-Pratt algorithm IV121 Vybrané aplikace informatiky v biologii -Přednáška 6 Stringologie Základní pojmy Základní algoritmy actgtgtatgaaatcgc Algoritmus využivajic' y C[ t C[ C C t prohledávaného řetéí ■j* ■j* ■j* X Hledání opakování Tandemové opakov Palindromy Srovnávání dvou sekvencí DP - Needleman-Wunsch máme v motivu předchozí výskyt g, tg nebo gtg ? actgtgtatgaaatcgc + 3 ^ gtgcct s-W heeler transform Složitost konstrukce: 0(\\abeceda\\.m) hledání: O(mn) (v praxi ale blíže k O(n)) 1 -O0.O 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 j 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^gatcat 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í DP - Needleman-Wunsch 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 6 b a 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í DP - Needleman-Wunsch 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. 1 -O0.O t=bababaa p=aba IV121 Vybrané aplikace informatiky v biologii -Přednáška 6 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í nalýzu prohledávaného řetězce Hledání opakování Tandemové opakování Palindromy Srovnáváni dvou sekvencí DP - Needleman-Wunsch Vylepšení pro maximálne k chyb Bu rrows-Wheeler transform Složitost konstrukce: naivní 0(m3); optimální 0(\\abeceda\\.m) hledání: O(n) 1 -O0.O Suffixový strom pro řetězec dabdac IV121 Vybrané aplikace informatiky v biologii -Prednáška 6 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 Hledání opaknvání 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í 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álne k chyb Bu rrows-Wheeler transform (b) Konstrukce: O(n.logn) Hledání: 0(m.\\abeceda\\+W) 4 □ ► 4 & * 4 5 ► < 5 ► 1 -O0.O DAWG IV121 Vybrané aplikace informatiky v biologii -Přednáška 6 A - B i -L D J — E - C N * E - S —| O L -A -T abject abjection abjections abjectly abjectness ablate ablated ablation ablations Stringologie Úvod 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í DP - Needleman-Wunsch 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 Outline 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 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 Bu rrows-Wheeler transform Srovnávání dvou sekvencí DP - Needleman-Wunsch Vylepšení pro maximálně k chyb Burrows-Wheeler transform 1 -O0.O 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 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álne k chyb Bu rrows-Wheeler transform 1 -00,0 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 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álne k chyb Burrows-Wheeler transform Složitost naivního algoritmu 0(n3) 1 -O0.O 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álne k chyb Bu rrows-Wheeler transform lcp(1,4) Nalezneme větve označené 1 a 4 lcp(1,4)=da Hledání tandemových opakování IV121 Vybrann aplikace informatiky v biologii -Přednáška 6 Stringologie Úvod Základní pojmy Základní algoritmy ► konstrukce stromu: 0(n./ogn) ► hledání lep pro dvě konkrétní pozice 0(n./ofifn) ► Prohledávání sekvence Algoritmus využívající nalyzu prohledávaného ŕetéľce Hledání opakování Tandemové opakování Palindromy Srovnávání dvou sekvencí DP - Needle man-Wunsch Vylepšení pro maximálně k chyb Burrows-Wheeler Iranslorm 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 g t c t t c g a a g t c t g a c g a c a g a c t g c t 9* Složitost naivního algoritmu 0(n3) IV121 Vybrané aplikace informatiky v biologii -Přednáška 6 Stringologie Úvod Základní pojmy Základní algoritmy Algoritmus využivajici analýzu hledaného motivu Algoritmus využivajici nalýzu prohledávaného ŕetézce Hledání opakování Tandemové opakováni Palindromy Srovnávání dvou sekvencí DP - Needleman-Wunsch Vylepšení pro maximálne k 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 5 ► < 5 ► 1 -O0.O Využití DP pro identifikaci palindromů IV121 Vybrané aplikace informatiky v biologii -Přednáška 6 □ match a match a+1 mismatch b + 1 insertion k c + 1 deletion Stringologie Úvod Základní pojmy Základní algoritmy Algoritmus využívající analýzu hledaného motívu 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álne k chyb Bu rrows-Wheeler transform b) 1 -00,0 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 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álne k chyb Bu rrows-Wheeler transform b) 1 -00,0 Outline 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 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álne k chyb Burrows-Wheeler transform Srovnávání dvou sekvencí DP - Needleman-Wunsch Vylepšení pro maximálně k chyb Burrows-Wheeler transform 1 -O0.O 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 Uvod Základní pojmy Základní algoritmy Algoritmus využívajíci analýzu hledaného motivu Algoritmus využívající nalýzu prohledávaného řetězce Hledání opakování Tandemové opakováni 3a1 rcircmy Srovnávání dvou sekvencí DP-Needleman-Wunsch Vylepšení pro maximálně k chyb Bu rrows-Wheeler transform Složitost: O(kn) (naproti O(mn)) 1 -O0.O Tabulka pro algoritmus dynamického programování IV121 Vybrané aplikace informatiky v biologii -Přednáška 6 Stringologie Úvod Základní pojmy Základní algoritmy (A) I S A L I G N E D -4 * -8*- 12*- 16*- 20*- 24*- 28*- 32*- 3ó T -4 -1 -3* -7*- 11*- 15*- 19*- 23*- 27*- 31 4 H -5 -2 -5 -9*- 13*- 17*- 18*- 22*- 26 V *>» Z -1 2 -4 -6 -3 -3 -5* -9 *- 13*- 17*- 21 | ."V *v N «S S -16 -S 0 * -4 -5 -5 -5* -8*- 12*- 16 | 1 >» S L -2 0 12 -1 0 -3 -7 * -8 - 11 *- 1 5 # v I -2 4 -8 -5 4 * D * -4* -8*- lí 1 t N N -2 8 20 - -9 -3 0 4 6 * 2 -ŕ -2 1 * •v *N E -32 - 24 - 16 - 13 -7 -4 c 4 11 * (B) THIS-LI-NE- II II II --ISALIGNED 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álne k chyb Bu rrows-Wheeler transform Využití SA a LCP k rychlému postupu po diagonále 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álne k chyb Bu rrows-Wheeler transform Složitost: 0(k2) (viz pou/vzit/'i pro palindromy) 1 -O0.O BWT - Burrows-Wheeler transform IV121 Vybrané aplikace informatiky v biologii -Přednáška 6 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živajici analýzu hledaného motivu Algoritmus využivajici nalýzu prohledávaného ŕetézce Hledání opakování Tandemové opakováni Palindromy Srovnávání dvou sekvencí 's-Wheeler transform 1 -00,0 BWT IV121 Vybrané aplikace informatiky v biologii -Přednáška 6 Add 1 Inverse Transformation Input BNN"AA@A Sort 1 Add 2 BA NA NA AB AN AN