VYSOKÉ UČENÍ TECHNICKÉ V BRNĚ

VYSOKÉ UČENÍ TECHNICKÉ V BRNĚ Fakulta informačních technologií

doc. Ing. Jan Holub, Ph.D.

Stringologie, komprese dat a biologie Stringology, data compression and biology TEZE PŘEDNÁŠKY K PROFESORSKÉMU JMENOVACÍMU ŘÍZENÍ V OBORU Výpočetní technika a informatika

Brno 2014

KLÍČOVÁ SLOVA Komprese dat, stringologie, vyhledávání, úplný index, autoindex, DNA, aminokyselina, bioinformatika.

KEYWORDS Data compression, stringology, pattern matching, fulltext index, self-index, DNA, aminoacid, bioinformatics.

© Jan Holub, 2014 ISBN 978-80-214-4917-6 ISSN 1213-418X

Obsah Prˇedstavenı´ autora

4

1

´ vod U

2

Stringologie 2.1 Prˇesne´ vyhleda´vańı´ . . . . . . . . . . . . . . . . . . . . ´ plny´ index . . . . . . . . . . . . . . . . . . . . . . . . 2.2 U 2.3 Prˇiblizˇne´ vyhleda´vańı´ . . . . . . . . . . . . . . . . . . . 2.4 Autoindex . . . . . . . . . . . . . . . . . . . . . . . . . 2.5 Dalsˇ´ı proble´my stringologie . . . . . . . . . . . . . . . 2.6 Proble´my stringologie rˇesˇene´ autorem a jeho ty´mem . . . 2.6.1 Algoritmy prˇesne´ho vyhleda´vańı´ . . . . . . . . . 2.6.2 Simulace NKA pro prˇiblizˇne´ vyhleda´vańı´ . . . . 2.6.3 Neurcˇite´ rˇeteˇzce . . . . . . . . . . . . . . . . . 2.6.4 Implementace kompaktnı´ho sufixove´ho automatu

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

7 7 9 10 11 12 13 13 13 13 13

Komprese dat 3.1 Statisticke´ metody . . . . . . . . . . . . . . . . . . . 3.2 Slovnı´kove´ metody . . . . . . . . . . . . . . . . . . 3.3 Kontextove´ metody . . . . . . . . . . . . . . . . . . 3.4 Proble´my komprese dat rˇesˇene´ autorem a jeho ty´mem 3.4.1 Komprese prˇirozene´ho textu . . . . . . . . . 3.4.2 Porovnańı´ kompresnıćh metod . . . . . . . .

3

4

5

5

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

14 14 15 15 16 16 17

Biologie 4.1 Sekvenovańı´ genomu˚ . . . . . . . . . . . . . . . . . . 4.2 Komprese podobnyćh sekvencı´ . . . . . . . . . . . . . 4.3 Proble´my bioinformatiky rˇesˇene´ autorem a jeho ty´mem 4.3.1 Vyhleda´vańı´ v genomech . . . . . . . . . . . . 4.3.2 Komprese podobnyćh sekvencı´ . . . . . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

18 18 19 19 19 20

Za´veˇr

22

Literatura

23

Abstrakt

31

Abstract

31

3

Prˇedstavenı´ autora Jan Holub (narozen 26. 9. 1971 v Praze) vystudoval Fakultu elektrotechnickou (FEL) CˇVUT v Praze, obor Vy´pocˇetnı´ technika (1990–1996). Pote´ pokracˇoval v internı´ formeˇ doktorske´ho studia na te´zˇe fakulteˇ a v roce 2000 zı´skal titul Ph.D. v oboru Informatika a vy´pocˇetnı´ technika. V roce 1999 nastoupil na katedru pocˇ´ıtacˇu˚ CˇVUT FEL jako odborny´ asistent. V roce 2008 se habilitoval na CˇVUT FEL v oboru Vy´pocˇetnı´ technika a informatika. V roce 2009, soucˇasneˇ se vznikem Fakulty informacˇnıćh technologiı´ (FIT) CˇVUT v Praze, byl jmenovań vedoucı´m katedry teoreticke´ informatiky (2009–2012) a za´rovenˇ i prodeˇkanem pro vneˇjsˇ´ı vztahy (2009–2012) na noveˇ vznikle´ fakulteˇ. Absolvoval neˇkolik odbornyćh sta´zˇ´ı v zahranicˇ´ı. Jednalo se zejmeńa o dveˇ sta´zˇe celkem na 3 meˇsıće na Universite´ de Marne-la-Valleé, Francie, v letech 1998 a 1999, dvouty´dennı´ sta´zˇ na School of Computing, Curtin University, Perth, Austra´lie, v roce 1999, rocˇnı´ postdoktorskou sta´zˇ na McMaster University, Hamilton, Ontario, Kanada, v letech 2002–2003 a meˇsıćˇnı´ sta´zˇ na McMaster University, Hamilton, Ontario, Kanada, v roce 2007. Odborny´mi za´jmy jsou teorie konecˇnyćh automatu˚, stringologie a komprese dat. Jan Holub je autorem nebo spoluautorem vıće nezˇ 28 recenzovanyćh konferencˇnıćh cˇlańku˚, vıće nezˇ 10 cˇlańku˚ v cˇasopisech a jedne´ kapitoly v knize. Jeho praće majı´ vıće nezˇ 100 citacı´ (bez autocitacı´) ve Web of Science spolecˇnosti Thomson Reuters a dalsˇ´ıch 43 ve Scopusu. Byl 4 kra´t zvany´m rˇecˇnı´kem na konferencıćh a workshopech. Zatı´m pu˚sobil 15 kra´t jako editor sbornı´ku mezina´rodnı´ konference, a 9 kra´t jako editor specia´lnı´ho cˇ´ısla zahranicˇnı´ho cˇasopisu (v 7 prˇ´ıpadech impaktovane´ho). Vedl jednu bakala´rˇskou a 20 diplomovyćh pracı´, z nichzˇ 6 zı´skalo cenu deˇkan za vynikajıćı´ diplomovou praći. Jan Holub vede veˇdeckouvy´zkumnou skupinu Prague Stringology Club na FIT CˇVUT v Praze. Recenzoval mnoho cˇlańku˚ pro mezina´rodnı´ cˇasopisy a konference ale take´ rˇadu projektu˚ cˇeskyćh i zahranicˇnıćh grantovyćh agentur. Sa´m zı´skal 4 na´rodnı´ (FRVSˇ, GACˇR) a jeden zahranicˇnı´ grant (NSERC, Kanada). Po dveˇ funkcˇnı´ obdobı´ (2009–2011, 2011–2013) pu˚sobil v hodnotıćı´m panelu P202 Informatika Grantove´ agentury CˇR. Jan Holub kazˇdorocˇneˇ od jejı´ho vzniku v roce 1996 spoluporˇa´da´ mezina´rodnı´ konferenci Prague Stringology Conference (od roku 2006 jako prˇedseda programove´ho vy´boru), ktera´ je indexovańa ve Scopusu a Web of Science spolecˇnosti Thomson Reuters. Da´le byl cˇlenem 17 programovyćh vy´boru˚ dalsˇ´ıch mezina´rodnıćh konferencı´ (naprˇ. CIAA, CPM, FSMNLP, IWOCA, SPIRE), z toho jednou jako prˇedseda (CIAA). V letech 2010–2012 pu˚sobil jako cˇlen poroty a v letech 2013–2014 jako prˇedseda souteˇzˇe Czech ACM Chapter & Slovakia ACM Chapter Student Project of the Year (ACM SPY). Jan Holub je v soucˇasne´ dobeˇ garantem oboru Syste´move´ programovańı´ v magisterske´m studijnı´m programu Informatika na FIT CˇVUT v Praze, prˇedna´sˇejıćı´m dvou bakala´ˇrskyćh, dvou magisterskyćh a jednoho doktorandske´ho prˇedmeˇtu. Jan Holub je spolecˇneˇ s doc. Danem Svozilem z VSˇCHT v Praze tvu˚rcem meziuniverzitnı´ho bakala´rˇske´ho i magisterske´ho studijnı´ho oboru Bioinformatika, ktery´ byl akreditovań v za´rˇ´ı 2013 a bude vyucˇovań ve spolupraći VSˇCHT, FIT CˇVUT v Praze a AV CˇR. Da´le je cˇlenem Veˇdecke´ rady FIT CˇVUT v Praze, mı´stoprˇedsedou Oborove´ rady doktorske´ho studijnı´ho programu na FIT CˇVUT v Praze a cˇlen Rady doktorske´ho studijnı´ho oboru 4I2 Softwarove´ syste´my na MFF UK v Praze, cˇlenem Eticke´ komise CˇVUT v Praze. 4

1

´ vod U

Stringologie je pocˇ´ıtacˇova´ veˇda o zpracovańı´ rˇeteˇzcu˚ a posloupnostı´ symbolu˚. Acˇkoliv prvnı´ proble´my v te´to oblasti zacˇaly by´t rˇesˇeny v sedmdesa´tyćh letech dvaca´te´ho stoletı´, pojem stringologie zavedl Zvi Galil azˇ v roce 1984 na workshopu NATO Advanced Research Workshop on Combinatorial Algorithms on Word [41]. Prvnı´ rˇesˇene´ u´lohy se ty´kaly nalezenı´ vzorku v textu. V textech se objevujı´ take´ chyby, takzˇe dalsˇ´ı aplikacı´ bylo prˇiblizˇne´ vyhleda´vańı´, kdy se hledajı´ vy´skyty vzorku s chybou. Stringologie se pak vyvı´jela smeˇrem k u´plny´m indexu˚m, ru˚zny´m definicı´m chyb a vyhleda´vańı´ pravidelnostı´ v textech. Komprese dat je pocˇ´ıtacˇova´ veˇda o u´sporne´m ukla´dańı´ dat. Prvnı´ metoda se objevila uzˇ v roce 1949, veˇtsˇ´ıho rozmachu se vsˇak docˇkala azˇ v sedmdesa´tyćh letech dvaca´te´ho stoletı´. Prvnı´ metody (statisticke´) uvazˇovaly pouze statisticke´ rozdeˇlenı´ jednotlivyćh symbolu˚. Nejcˇasteˇjsˇ´ım symbolu˚m byly prˇideˇlovańy nejkratsˇ´ı ko´dy. Dalsˇ´ı metody (slovnı´kove´) vyuzˇ´ıvaly opakovańı´ cˇa´stı´ textu. Opakujıćı´ se cˇa´sti textu nahrazovaly ukazateli na prˇedchozı´ vy´skyty. Kontextove´ metody vyuzˇ´ıvajı´ kontextu k prˇedvı´dańı´ na´sledujıćı´ho symbolu. Navıć umozˇnily i fultextove´ vyhleda´vańı´ v komprimovanyćh datech.

Stringologie

Komprese dat

pˇresn´ e vyhled´ av´ an´ı

statistick´ e metody

pˇribliˇ zn´ e vyhled´ av´ an´ı

slovn´ıkov´ e metody

indexov´ an´ı

kontextov´ e metody

neurˇ cit´ e ˇretˇ ezce

komprese pˇrirozen´ eho jazyka

Biologie sekvenace genomu

Bioinformatika sestaven´ı genomu ukl´ ad´ an´ı genom˚ u vyhled´ av´ an´ı v genomech fylogenetick´ a anal´ yza

Obra´zek 1: Vza´jemny´ vztah Stringologie, Komprese dat a Biologie Biologie je veˇda zkoumajıćı´ vesˇkere´ organismy od u´rovneˇ subcelula´rnı´ azˇ po u´rovenˇ populacı´, spolecˇenstev a ekosyste´mu˚. Aplikacı´ informatiky v molekula´rnı´ biologii se zaby´va´ bioinformatika. Pojem bioinformatika byl zaveden jizˇ v polovineˇ osmdesa´tyćh let dvaca´te´ho stoletı´. Tehdy vsˇak byla definice tohoto pojmu velmi obecna´. Jednı´m z hlavnıćh u´kolu˚ bio5

informatiky je zpracovańı´ a analy´za DNA. Toto te´ma je rozdeˇleno na dveˇ hlavnı´ cˇa´sti [90]: 1. funkcˇnı´ genomika, ktera´ se zaby´va´ urcˇenı´m role sekvence v zˇivoteˇ bunˇky; 2. komparativnı´ genomika, ve ktere´ jsou sekvence ru˚znyćh organismu˚, ale i jednotlivcu˚ jednoho druhu, porovna´vańy k urcˇenı´ pu˚vodu˚ a korelacı´ nemocı´. Oblasti stringologie, komprese dat a biologie se vyvı´jely pomeˇrneˇ neza´visle. Postupem cˇasu se zacˇaly k sobeˇ prˇiblizˇovat oblast stringologie s hlavnı´m u´kolem vyhleda´vat a komprese dat s hlavnı´m u´kolem data komprimovat, efektivneˇ ukla´dat. Da´le u´koly ze stringologie nacha´zely uplatneˇnı´ v bioinformatice nebo naopak bioinformatika vytva´rˇela u´koly pro stringologii. Poslednı´ vy´voj v oblasti biologie, kde nove´ technologie produkujı´ obrovska´ mnozˇstvı´ dat, ve kteryćh je potrˇeba vyhleda´vat, vola´ po spolecˇne´ aplikaci stringologie a komprese dat v oblasti bioinformatiky. Zı´skana´ data je nutne´ prˇedevsˇ´ım efektivneˇ ulozˇit a vyhleda´vat v nich. Vazby mezi teˇmito obory jsou zna´zorneˇny na obra´zku 1. Tento text obsahuje strucˇny´ prˇehled za´kladnıćh algoritmu˚ a datovyćh struktur v oblasti stringologie (v kapitole 2) a komprese dat (v kapitole 3). Aplikaci stringologie a komprese dat v biologii pak popisuje kapitola 4.

6

2

Stringologie

Cı´lem te´to kapitoly je prˇedstavit typicke´ u´lohy stringologie, jako je prˇesne´ a prˇiblizˇne´ vyhleda´vańı´, vytva´rˇenı´ u´plne´ho indexu, komprimovane´ho u´plne´ho indexu, cˇi praće s neurcˇity´mi rˇeteˇzci. Sekce 2.6 pak shrnuje praći v oblasti stringologie s ućˇastı´ autora tohoto textu.

2.1 Prˇesne´ vyhleda´vańı´ Prvnı´ u´lohou stringologie bylo nalezenı´ vy´skytu vzorku p = p[1..m] de´lky m v textu t = t[1..n] de´lky n, kde p i t jsou rˇeteˇzce nad abecedou Σ (znacˇ´ıme p, t ∈ Σ∗ ). Proble´m je mozˇne´ ˇresˇit pomocı´ mnoha algoritmu˚. a, g, t

c

c c

0

c g, t

1 g, t

a

c 2

a

3

c

4

a

5

a, g, t g, t a, g, t

Obra´zek 2: Deterministicky´ konecˇny´ automat pro vyhledańı´ vzorku p = caaca, Σ = {a, c, g, t} Jednı´m z prvnıćh rˇesˇenı´ bylo pouzˇitı´ deterministicke´ho konecˇne´ho automatu [3] (DKA, viz obra´zek 2), ktery´ je definovań jako usporˇa´dana´ peˇtice M = (Q, Σ, δ, q0 , F), kde Q je konecˇna´ mnozˇina stavu˚, Σ je konecˇna´ vstupnı´ abeceda, δ je prˇechodova´ funkce Q × Σ 7→ Q, q0 ∈ Q je pocˇa´tecˇnı´ stav a F ⊆ Q je mnozˇina koncovyćh stavu˚. Tento automat zpracova´va´ vstupnı´ text a prˇechodem do koncove´ho stavu hla´sı´ jednotlive´ vy´skyty vzorku p v textu t. a, g, t

0

c

1

a

2

a

3

c

4

a

5

Obra´zek 3: KMP automat pro vyhledańı´ vzorku p = caaca, Σ = {a, c, g, t} (fail funkce f zobrazena tecˇkovanou cˇa´rou) Dalsˇ´ım velmi zna´my´ rˇesˇenı´m je algoritmus Knuth-Morris-Pratt [63] (KMP, viz obra´zek 3). Tento automat ma´ navıć definovanou tzv. fail funkci f , ktera´ se uplatnı´ v situaci, kdy pro dany´ vstupnı´ symbol nenı´ definovań prˇechod v prˇechodove´ funkci δ. Vy´hodou automatu KMP je, zˇe ma´ obeˇ prˇechodove´ funkce δ i f prostoroveˇ nena´rocˇne´, potrˇebujı´ pameˇt’o velikosti jen O(m). DKA prˇitom vyzˇaduje pro ulozˇenı´ prˇechodove´ funkce δ pameˇt’o velikosti O(m|Σ|). 7

Oba dva vy´sˇe uvedene´ algoritmy pracujı´ v cˇase O(n), cˇili linea´rnı´m s de´lkou textu t. V pru˚meˇru sublinea´rnı´ho cˇasu Ω(n/m) dosahuje algoritmus Boyer-Moore [18], pracujıćı´ na principu protismeˇrne´ho vyhleda´vańı´, kdy se vzorek k textu prˇikla´da´ zleva doprava, ale vzorek se s nı´m porovna´va´ zprava doleva. V prˇ´ıpadeˇ nalezenı´ neshody mezi vzorkem a textem, se vzorek posune doprava. Pro posun se vyuzˇ´ıvajı´ funkce bad-character shift a good-suffix shift. Funkce bad-character shift posouva´ vzorek tak, aby proti aktua´lnı´mu symbolu v textu lezˇel nejpraveˇjsˇ´ı vy´skyt tohoto symbolu ve vzorku. Funkce good-suffix shift zase vyuzˇ´ıva´ informaci o jizˇ porovnane´ prˇ´ıponeˇ u vzorku a posouva´ vzorek tak, aby vy´skyt u v textu lezˇel proti druhe´mu vy´skytu u zprava ve vzorku. Algoritmus Boyer-Moore dal vzniknout cele´ tzv. rodineˇ Boyer-Mooreovyćh algoritmu˚, naprˇ´ıklad [55, 102, 97, 59]. Da´le byly tyto algoritmy rozsˇ´ırˇeny o mozˇnost vyhleda´vat neˇkolik vzorku˚ najednou. Rozsˇ´ırˇenı´m algoritmu KMP vznikl algoritmus Aho-Corasick [2] pro sousmeˇrne´ vyhleda´vańı´ vıće vzorku˚ a rozsˇ´ırˇenı´m algoritmu Boyer-Moore vznikl algoritmus Commentz-Walter [28] pro protismeˇrne´ vyhleda´vańı´ vıće vzorku˚. Vy´sˇe uvedene´ algoritmy si prˇedzpracovaly vzorek a pote´ procha´zely textem. Naivnı´ algoritmus vzorek neprˇedzpracova´va´. Pouze prˇikla´da´ vzorek k textu a porovna´va´ s textem. Prˇi neshodeˇ posune vzorek o jednu pozici a znovu porovna´va´. Tento algoritmus pracuje v cˇase O(nm), cozˇ je v podstateˇ chovańı´ algoritmu Boyer-Moore v nejhorsˇ´ım prˇ´ıpadeˇ pro patologicky´ vzorek a text. sufixov´ y strom c

a

a a

c

a

a

a

c

minimalizace

zhutnˇen´ı c

a

kompaktn´ı sufixov´ y strom

sufixov´ y automat

aca a a c

a

a

c c

a

a

ca ca aca

kompaktn´ı sufixov´ y automat zhutnˇen´ı a ca

ca, aca

minimalizace

aca

Obra´zek 4: Vztahy mezi sufixovy´m stromem, kompaktnı´m sufixovy´m stromem, sufixovy´m automatem a kompaktnı´m sufixovy´m automatem ( p = caaca) 8

´ plny´ index 2.2 U Dalsˇ´ım prˇ´ıstupem k prˇesne´mu vyhleda´vańı´ v textu je prˇedzpracovańı´ samotne´ho textu, kdy se nad textem t vytvorˇ´ı u´plny´ index a vzorek plze pak vyhledat v cˇase O(m), cˇili neza´visle na de´lce textu t. Pro tyto ućˇely byl zkonstruovań sufixovy´ strom [40] (anglicky suffix trie). Sufixovy´ strom (viz obra´zek 4) je deterministicky´ konecˇny´ automat, ktery´ prˇijı´ma´ vsˇechny prˇ´ıpony (sufixy) dane´ho textu. Navıć doka´zˇe rozpoznat i vsˇechny podrˇeteˇzce dane´ho textu. Pokud pro rˇeteˇzec u existuje cesta z pocˇa´tecˇnı´ho stavu do neˇjake´ho stavu v sufixove´m automatu, pak je u podrˇeteˇzcem textu t. Jestlizˇe tato cesta koncˇ´ı v koncove´m stavu, pak je u navıć i prˇ´ıponou textu t. Pokud sufixovy´ strom zminimalizujeme1, zı´ska´me sufixovy´ automat [16, 15, 29, 12] (anglicky suffix automaton nebo DAWG2 ; viz obra´zek 4), cozˇ je minima´lnı´ deterministicky´ automat prˇijı´majıćı´ vsˇechny prˇ´ıpony textu t. Pokud na druhou stranu tzv. zhutnı´me sufixovy´ strom, zı´ska´me kompaktnı´ sufixovy´ strom [100, 73, 99] (anglicky suffix tree; viz obra´zek 4), ve ktere´m jsou prˇechody ohodnoceny rˇeteˇzci mı´sto symbolu˚. Prˇi procesu zhutneˇnı´ (anglicky compaction) se kazˇda´ posloupnost prˇechodu˚, ktera´ se neveˇtvı´ a neobsahuje koncove´ stavy, nahradı´ jednı´m prˇechodem ohodnoceny´m rˇeteˇzcem slozˇeny´m ze symbolu˚ ohodnocujıćı´ pu˚vodnı´ posloupnost prˇechodu˚. Procesem minimalizace sufixove´ho automatu nebo procesem zhutneˇnı´ kompaktnı´ho sufixove´ho stromu zı´ska´me kompaktnı´ sufixovy´ automat [17, 31, 61, 50] (anglicky compact suffix automaton nebo CDAWG3 ; viz obra´zek 4). 0

c

1 a

a

2

a

3

c

4

a

5

c

Obra´zek 5: Faktorovy´ oracle pro text t = caaca Pokud bychom v sufixove´m automatu oznacˇili vsˇechny stavy jako koncove´ a eliminovali vsˇechny stavy mimo tzv. 1 2 3 4 5 6 pa´terˇ (nejdelsˇ´ı posloupnost prˇechodu˚), zı´ska´me faktorovy´ t c a a c a $ oracle [4] (anglicky factor oracle; viz obra´zek 5). Jelikozˇ SA 6 5 2 3 4 1 tento automat ma´ meńeˇ stavu˚ nezˇ minima´lnı´ determinis$ a a a c c ticky´ automat prˇijı´majıćı´ vsˇechny podrˇeteˇzce (neboli fak$ a c a a tory) textu t, neˇco ztraćı´me. Tı´m je odpoveˇd’„ p je podrˇeteˇc a $ a zec textu t“. Faktorovy´ oracle prˇijı´ma´ vsˇechny podrˇeteˇzce a $ c textu t, ale take´ dalsˇ´ı rˇeteˇzce, jejichzˇ mnozˇina nasˇteˇstı´ nenı´ $ a velka´. Pokud faktorovy´ oracle odpovı´ „ p nenı´ podrˇeteˇzec $ textu t“, mu˚zˇeme se na tuto odpoveˇd’ spolehnout. Pokud na´m odpovı´ „ p pravdeˇpodobneˇ je podrˇeteˇzec textu t“, mu- Tabulka 1: Sufixove´ pole pro text sı´me tuto hypote´zu oveˇrˇit. Faktorovy´ oracle lze tedy pou- t = caaca zˇ´ıt jako filtr, ktery´ na´m propustı´ male´ procento falesˇnyćh vy´skytu˚. Toto je trend v nejnoveˇjsˇ´ıch metodaćh pro prˇesne´ vyhleda´vańı´, kdy je na cely´ text pouzˇit velmi jednoduchy´ a rychly´ stroj, jehozˇ vy´sledky je potrˇeba oveˇrˇit. 1 Jedna ´

se o standardnı´ minimalizaci deterministicke´ho konecˇne´ho automatu. znamena´ Directed Acyclic Word Graph. 3 CDAWG znamena ´ Compact Directed Acyclic Word Graph. 2 DAWG

9

Sufixove´ pole [71] (anglicky suffix array; viz rˇa´dek SA v tabulce 1) pro text t je pole indexu˚ identifikujıćıćh vsˇechny prˇ´ıpony textu t serˇazene´ lexikograficky. Sufixove´ pole lze sice vytvorˇit v cˇase O(n), avsˇak podle [89] je v praxi nejrychlejsˇ´ım algoritmem [72] beˇzˇ´ıcı´m v cˇase O(n2 log n). Indexovacı´ automaty hrajı´ svoji roli i ve vyhleda´vańı´, kdy prˇedzpracujeme text t. V algoritmu BDM (Backward DAWG Matching) [30] je vytvorˇen sufixovy´ automat pro reverzovany´ vzorek p. Tento automat je pouzˇit mı´sto porovna´vańı´ vzorku a textu v algoritmu Boyer-Moore. Doka´zˇe najı´t prˇedponu textu a tı´m identifikovat maxima´lnı´ mozˇny´ posun vzorku textem. Metoda BNDM (Backward Nondeterministic DAWG Matching) [81] pouzˇ´ıva´ nedeterministickou verzi sufixove´ho automatu a jeho simulaci pomocı´ bitove´ho paralelismu [34, 10, 47]. Metoda BOM (Backward Oracle Matching) [4] pak vyuzˇ´ıva´ faktorovy´ oracle. Metody zalozˇene´ na protismeˇrne´m vyhleda´vańı´ jsou nejrychlejsˇ´ımi metodami [35] pro prˇesne´ vyhleda´vańı´.

sufixovy´ strom (kompaktnı´) sufixovy´ strom sufixovy´ automat (kompaktnı´) sufixovy´ automat faktorovy´ oracle sufixove´ pole

cˇas vyhledańı´ O(m) O(m) O(m) O(m) O(m) O(m + log n)

cˇas konstrukce O(n2 ) O(n log |Σ|) O(n log |Σ|) O(n log |Σ|) O(n log |Σ|) O(n2 log n)

max. velikost n2 2n 2n − 1 n+1 n+1 n

Tabulka 2: Za´kladnı´ charakteristiky indexovacıćh struktur

Tabulka 2 ukazuje prˇehled indexovacıćh struktur s cˇasy vyhleda´vańı´, konstrukce a maxima´lnı´ velikostı´, ktera´ uda´va´ maxima´lnı´ pocˇet stavu˚ automatu nebo maxima´lnı´ velikost sufixove´ho pole.

2.3 Prˇiblizˇne´ vyhleda´vańı´ Protikladem k prˇesne´mu vyhleda´vańı´ je prˇiblizˇne´ vyhleda´vańı´, kdy nalezene´ vy´skyty vzorku p v textu t mohou obsahovat neˇjakou chybu. Odlisˇnost od vzorku je dańa editacˇnı´ vzda´lenostı´, ktera´ je pro dva rˇeteˇzce u, v ∈ Σ∗ definovańa jako minima´lnı´ pocˇet editacˇnıćh operacı´, ktere´ jsou zapotrˇebı´ pro prˇevedenı´ rˇeteˇzce u na rˇeteˇzec v. Hammingova vzda´lenost [46] zna´ jen jednu operaci, kterou je substituce, cˇili nahrazenı´ symbolu jiny´m. Levenshteinova vzda´lenost [69] navıć uvazˇuje i operace vlozˇenı´ symbolu a odstraneˇnı´ symbolu. Damerauova vzda´lenost [32] k vy´sˇe uvedeny´m operacı´m prˇida´va´ operaci transpozice, prˇi ktere´ jsou dva sousednı´ symboly prohozeny prˇicˇemzˇ kazˇdy´ symbol se mu˚zˇe zućˇastnit maxima´lneˇ jedne´ operace transpozice. Vzda´lenost indel (z anglicke´ho insert a delete) povoluje pouze operace vlozˇenı´ symbolu a odstraneˇnı´ symbolu. Prˇi prˇiblizˇne´m vyhleda´vańı´ je pro dany´ vzorek p vytvorˇen vyhleda´vacı´ automat [75, 76], ktery´ reprezentuje vsˇechny rˇeteˇzce v povolene´ vzda´lenosti od vzorku p. Tento automat dostane jako vstup text t a nalezne v neˇm vsˇechny prˇiblizˇne´ vy´skyty vzorku p. Jelikozˇ je tento automat nedeterministicky´ a determinizace by vedla na prˇ´ılisˇ velky´ deterministicky´ konecˇny´ automat, pouzˇ´ıvajı´ se simulacˇnı´ metody nazvane´ bitovy´ paralelismus [34, 10, 47] a dynamicke´ programovańı´ [94, 98, 48]. 10

text vzorek

nenı´ prˇedzpracovań je prˇedzpracovań

nenı´ prˇedzpracovań naivnı´ algoritmus

DKA, KMP, BM, . . .

je prˇedzpracovań (kompaktnı´) sufixovy´ strom, (kompaktnı´) sufixovy´ automat, faktorovy´ oracle, sufixove´ pole automat pru˚niku

Tabulka 3: Za´kladnı´ klasifikace algoritmu˚ podle prˇedzpracovańı´ vzorku a/nebo textu

Pokud chceme zkra´tit cˇas vyhleda´vańı´, ktery´ je dań de´lkou textu t, mu˚zˇeme jako v prˇ´ıpadeˇ prˇesne´ho vyhleda´vańı´ prˇedzpracovat text t, cˇili vytvorˇit indexovacı´ automat pro text t. Avsˇak mı´sto prˇedlozˇenı´ vzorku p tomuto automatu, cozˇ by vedlo k nalezenı´ jen prˇesnyćh vy´skytu˚ vzorku p, pouzˇijeme vyhleda´vacı´ automat vytvorˇeny´ pro vzorek p reprezentujıćı´ mnozˇinu rˇeteˇzcu˚ v povolene´ vzda´lenosti od vzorku p. Z teˇchto dvou automatu˚ vytvorˇ´ıme automat pru˚niku [51], ktery´ prˇijı´ma´ pru˚nik jazyku˚ pu˚vodnıćh automatu˚ a tı´m zı´ska´me vsˇechny prˇiblizˇne´ vy´skyty vzorku p v textu t. V tabulce 3 je uveden souhrn popisovanyćh metod podle toho, zda prˇedzpracova´vajı´ vzorek a/nebo text.

2.4 Autoindex V poslednıćh letech je snaha zkonstruovat pro text t datovou strukturu pro indexovańı´, ktera´ by byla prostoroveˇ meńeˇ na´rocˇna´ nezˇ prˇedchozı´ struktury. Byl zaveden pojem zhusˇteˇny´ index [80] (anglicky succinct index), ktery´ je co do velikosti u´meˇrny´ de´lce textu t (do de´lky 2n). Da´le byl zaveden pojem autoindex [80] (anglicky self-index), cozˇ je zhusˇteˇny´ index schopny´ nahradit pu˚vodnı´ text t. Kromeˇ schopnosti vyhleda´vat totizˇ umozˇnˇuje efektivneˇ zobrazit libovolny´ podrˇeteˇzec textu t. Prvnı´m autoindexem byl FM-Index [37], jehozˇ za´kladem je Burrows-Wheelerova transformace [22]. Tato transformace vyuzˇ´ıva´ sufixove´ pole a umozˇnˇuje vyhleda´vat vzorek p v textu t zprava doleva. Dalsˇ´ım autoindexem je komprimovane´ sufixove´ pole [43, 93] (anglicky compressed suffix array), ktere´ je komprimovanou formou sufixove´ho pole [71]. Princip pouzˇitı´ tohoto pole je stejny´, jen prˇ´ıstup do pole je pomalejsˇ´ı. Autoindexy jsou postaveny na implementacıćh operacı´ ranka select [62, 78, 25] pracujıćıćh v konstantnı´m cˇase nad bitovy´m vektorem B. Vy´sledkem operace rankb (B, i) je pocˇet bitu˚ b v bitove´m vektoru B do pozice i. Vy´sledkem operace selectb (B, i) je naopak pozice i-te´ho bitu b v bitove´m vektoru B. Pokud chceme podobneˇ pracovat s rˇeteˇzcem vytvorˇene´m nad veˇtsˇ´ı nezˇ bina´rnı´ abecedou, vyuzˇ´ıva´me struktury zvane´ vlnkovy´ strom [42] (anglicky wavelet tree; viz obra´zek 6). Vlnkovy´ strom ma´ v korˇeni cely´ text t, z neˇjzˇ vytvorˇ´ı rˇeteˇzec acacaa obsahujıćı´ symboly z prvnı´ poloviny abecedy ({a, c}) a rˇeteˇzec tgttt obsahujıćı´ symboly z druhe´ poloviny abecedy ({g, t}). Cely´ proces pak pokracˇuje rekurzivneˇ da´le smeˇrem k listu˚m, ktere´ odpovı´dajı´ jednotlivy´m symbolu˚m abecedy. Ve stromu jsou ulozˇeny pouze bitove´ vektory indikujıćı´, do ktere´ poloviny abecedy prˇ´ıslusˇny´ symbol rˇeteˇzce patrˇ´ı. Operace rank a select pak 11

actgactaatt 00110010011 {a, c}

{g, t}

acacaa 010100

tgttt 10111

{a}

a

{c}

c

{g}

g

{t}

t

Obra´zek 6: Vlnkovy´ strom pro text t = actgactaatt

pracujı´ nad rˇeteˇzci s abecedou Σ, |Σ| > 2, v cˇase O(log |Σ|), ktery´ je dań maxima´lnı´ hloubkou vlnkove´ho stromu.

2.5 Dalsˇ´ı proble´my stringologie Ve vsˇech vy´sˇe uvedenyćh u´lohaćh je vzorek i text jasneˇ dań. Stringologie vsˇak rˇesˇ´ı i proble´my, kdy vzorek je popsań svy´mi vlastnostmi. Vzorek mu˚zˇe by´t naprˇ´ıklad specifikovań jako rˇeteˇzec, ktery´ se v textu opakuje minima´lneˇ n kra´t. Vyhleda´vańı´ opakujıćıćh se vzorku˚ v textu je velmi ´ loha take´ mu˚zˇe znı´t jako nalezenı´ vsˇech rˇeteˇzcu˚, ktere´ se du˚lezˇite´ pro oblast komprese dat. U ve stejne´m porˇadı´ vyskytujı´ ve vsˇech textech z dane´ mnozˇiny [7]. Dalsˇ´ı dimenzı´ proble´mu˚ je praće s rˇeteˇzci, ve kteryćh jsou specia´lnı´ symboly. Tak zvany´ neurcˇity´ symbol [53] (anglicky indeterminate, degenerate nebo generalized) je symbol, ktery´ zastupuje vıće nezˇ jeden symbol za´kladnı´ abecedy. Neurcˇity´ symbol je zobecneˇnı´m don’t care symbolu [39, 60], ktery´ zastupuje libovolny´ symbol abecedy. Ma´me-li naprˇ. za´kladnı´ abecedu Σ = {a, c, g, t}, pak rozsˇ´ırˇena´ abeceda Σ′ = 2Σ \{∅} obsahuje i neurcˇite´ symboly, reprezentujıćı´ vıće nezˇ jednoprvkovou podmnozˇinu za´kladnı´ abecedy Σ. Jednı´m takovy´m symbolem mu˚zˇe by´t symbol b = {a, c}, ktery´ reprezentuje dva symboly ze za´kladnı´ abecedy. Du˚vodem mu˚zˇe by´t, zˇe prˇi cˇtenı´ (naprˇ´ıklad prˇi OCR4 ) textu nenı´ jasne´, jestli dany´ symbol na dane´ pozici v rˇeteˇzci byl a nebo c, nebo zˇe pro oba symboly majı´ v dane´ aplikaci stejny´ vy´znam. Zajı´mavy´m proble´mem je i vyhleda´vańı´ parametrizovanyćh rˇeteˇzcu˚ [11, 6] (anglicky parametrized string matching). Meˇjme dveˇ disjunktnı´ mnozˇiny Σ a Π, ktere´ reprezentujı´ ˇ eteˇzec u ∈ (Π ∪ Σ)∗ abecedu konstantnıćh symbolu˚ a abecedu parametrovyćh symbolu˚. R vytvorˇeny´ nad teˇmito abecedami nazveme parametrizovany´ rˇeteˇzec neboli p-rˇeteˇzec. Pro dva stejneˇ dlouhe´ p-rˇeteˇzce u a v rˇ´ıka´me, zˇe parametrizovaneˇ souhlası´, pokud existuje bijektivnı´ zobrazenı´ f : Π 7→ Π, ktere´ prˇevede u na v. Necht’ Σ = {A, B, C, D}, Π = {e, g, h}, u = AegeeBChggDe a v = AghggBCehhDg, pak u a v parametrizovaneˇ souhlası´ ( f (e) = g, f (g) = h, f (h) = e ). Tento proble´m nacha´zı´ uplatneˇnı´ v oblastech jako udrzˇovańı´ zdrojovyćh ko´du˚ a detekce plagia´tu˚. 4 Optical

12

character recognition

2.6 Proble´my stringologie rˇesˇene´ autorem a jeho ty´mem 2.6.1 Algoritmy prˇesne´ho vyhleda´vańı´ V sekci 2.2 byly zmıńeˇny nejrychlejsˇ´ı metody pro prˇesne´ vyhleda´vańı´, ktere´ jsou zalozˇeny na sufixove´m automatu. Autor tohoto textu se podı´lel na vy´voji dalsˇ´ıch metod pro prˇesne´ vyhleda´vańı´ [35]: Byla navrzˇena nova´ metoda FNDM (Forward Nondeterministic DAWG Matching), ktera´ kombinuje sufixovy´ automat pro doprˇedne´ vyhleda´vańı´ a bad-character shift. Metoda BNDMq vylepsˇuje metodu BNDM [81]. Metoda SBNDMq vylepsˇuje metodu SBNDM [83]. Metoda FNDMq vylepsˇuje metodu FNDM. Vylepsˇenı´ spocˇ´ıva´ v pouzˇitı´ q-gramu˚, cˇili rˇeteˇzcu˚ o de´lce q, mı´sto jednotlivyćh symbolu˚. 2.6.2 Simulace NKA pro prˇiblizˇne´ vyhleda´vańı´ V oblasti prˇiblizˇne´ho vyhleda´vańı´ (sekce 2.3) autor tohoto textu uka´zal [47, 48], zˇe existujıćı´ algoritmy pro prˇiblizˇne´ vyhleda´vańı´ bitovy´ paralelismus [34, 10] a dynamicke´ programovańı´ [94, 98] simulujı´ beˇh nedeterministicke´ho konecˇne´ho automatu pro prˇiblizˇne´ vyhleda´vańı´. Da´le uka´zal za´kladnı´ simulacˇnı´ metodu, ze ktere´ obeˇ vy´sˇe zmıńeˇne´ metody vycha´zejı´. Zpu˚sob simulace NKA pomocı´ bitove´ho paralelismu a dynamicke´ho programovańı´ umozˇnˇuje rychle´ nalezenı´ rˇesˇenı´ pro prˇ´ıbuzne´ proble´my, jako prˇ´ıpadeˇ Damerauovy vzda´lenosti. 2.6.3 Neurcˇite´ rˇeteˇzce V oblasti neurcˇityćh rˇeteˇzcu˚ (sekce 2.5) autor tohoto textu urcˇil za´kladnı´ vlastnosti neurcˇityćh rˇeteˇzcu˚ [53] a navrhl algoritmus na vy´pocˇet border array, cozˇ je za´kladnı´ struktura pouzˇita´ v algoritmech vyhleda´vańı´ jako je KMP [63] a BM [18]. Da´le pak navrhl efektivnı´ algoritmus [54] pro vyhleda´vańı´ v neurcˇityćh rˇeteˇzcıćh. 2.6.4 Implementace kompaktnı´ho sufixove´ho automatu V oblasti u´plne´ho indexu (sekce 2.2) autor vytvorˇil velmi efektivnı´ implementaci kompaktnı´ho sufixove´ho automatu [50]. Zde byly stavy automatu rozdeˇleny na 4 trˇ´ıdy podle maxima´lnı´ de´lky ohodnocenı´ odchozı´ho prˇechodu. Kazˇda´ takova´ trˇ´ıda byla zako´dovańa specia´lnı´m zpu˚sobem, cˇ´ımzˇ vznikla pameˇt’oveˇ velmi efektivnı´ implementace ve formeˇ bitove´ho proudu. Zatı´mco prˇedchozı´ zna´ma´ implementace potrˇebovala cca 10–15 bytu˚ na jeden znak vstupnı´ho textu, tato implementace potrˇebuje jen 1,5–3,02 bytu˚ na jeden znak vstupnı´ho textu. U DNA sekvencı´ to bylo snı´zˇenı´ z 23,55 na 5,24 bytu˚ na jeden znak vstupnı´ho textu.

13

3 Komprese dat Za´kladem komprese je odstraneˇnı´ redundance (nadbytecˇnosti) z dat. Existuje mnoho zpu˚sobu˚, jak toho dosa´hnout. Statisticke´ metody uvazˇujı´ pouze frekvence symbolu˚ v textu. Slovnı´kove´ metody nahrazujı´ cele´ rˇeteˇzce ukazateli do slovnı´ku vytvorˇene´ho z jizˇ zakomprimovane´ cˇa´sti textu. Kontextove´ metody vyuzˇ´ıvajı´ znalosti kontextu k predikci na´sledujıćı´ho symbolu. U metod komprese dat se v poslednıćh letech prˇida´va´ podpora operacı´ vyhleda´vańı´ v komprimovanyćh datech. Zatı´mco u statistickyćh metod se jedna´ jen o linea´rnı´ procha´zenı´ zakomprimovane´ho textu, u slovnı´kovyćh a hlavneˇ u kontextovyćh metod se jedna´ o tvorbu u´plne´ho indexu. Cı´lem te´to kapitoly je uve´st typicke´ algoritmy komprese a v sekci 3.4 pak prˇedstavit praći autora v oblasti komprese dat.

3.1 Statisticke´ metody 23 0

1

10 0

13 0

1

1

4 0

1

1

0

2 0

2

6 1

0

6 1

0

1

1

1

1

1

3

3

3

3

7

frekvence:

1

1

1

1

3

3

3

3

7

symbol:

l

d

h

n

i

o

a

t

e

Obra´zek 7: Huffmanu˚v ko´dovacı´ strom Prvnı´ metody komprese dat, Shannon-Fanovo ko´dovańı´ [36] a Huffmanovo ko´dovańı´ [58] vyuzˇ´ıvajı´ pouze znalosti frekvence symbolu˚ v textu. Nejcˇasteˇjsˇ´ı symboly jsou ko´dovańy kratsˇ´ımi ko´dy nezˇ meńeˇ cˇaste´ symboly. Na obra´zku 7 je videˇt Huffmanu˚v ko´dovacı´ strom zkonstruovany´ pro symboly Σ = {a, d, e, h, i, l, n, o, t} podle jejich frekvencı´. Cesta z korˇene stromu k listu uda´va´ ko´d symbolu v listu. Nejcˇasteˇjsˇ´ım symbolem je symbol e a ma´ take´ nejkratsˇ´ı ko´d 11. Na druhou stranu jednı´m z nejmeńeˇ cˇastyćh symbolu˚ je symbol d, ktery´ ma´ ko´d 0001. Vztah mezi minima´lnı´ de´lkou ko´dovyćh slov jednotlivyćh symbolu˚ a jejich pravdeˇpodobnostı´ je dań Kraft-McMillanovou nerovnostı´ [64, 74]. Pokud je porusˇena, vy´sledny´ ko´d nenı´ jednoznacˇny´. Huffmanovo ko´dovańı´ se pouzˇ´ıva´ v mnoha kompresnıćh forma´tech (naprˇ. gzip, pkzip, bzip2) pro kompresi neˇkteryćh dı´lcˇ´ıch cˇa´stı´. Jesˇteˇ lepsˇ´ıch vy´sledku˚ dosahuje Aritmeticke´ ko´dovańı´ [1, 91, 82], ktere´ neprˇirˇazuje ko´dove´ slovo kazˇde´mu symbolu, ale bitovy´ rˇeteˇzec je prˇirˇazen cele´mu komprimovane´mu textu. Nevznika´ tam tedy ztra´ta kompresnı´ho pomeˇru prˇi zaokrouhlovańı´ na cele´ bity prˇi tvorbeˇ ko´dovyćh slov pro jednotlive´ symboly. 14

3.2 Slovnı´kove´ metody Lepsˇ´ıho kompresnı´ho pomeˇru doka´zˇ´ı dosa´hnout slovnı´kove´ metody, ktere´ si tvorˇ´ı slovnı´k z jizˇ zakomprimovanyćh dat. Komprimovana´ data se pak sesta´vajı´ z odkazu˚ do tohoto slovnı´ku. s i r

s i d

e a s t m a n

zakomprimovan´ a ˇcást

e a s i l y nezakomprimovan´ a ˇcást

Obra´zek 8: Posuvne´ okno metody LZ77 Metoda LZ77 [103] (neboli metoda posuvne´ho okna) posouva´ textem okno, ktere´ ma´ ˇ eteˇzec v nezakomprimovane´ zakomprimovanou a nezakomprimovanou cˇa´st (viz obra´zek 8). R cˇa´sti okna je zakomprimovań odkazem do zakomprimovane´ cˇa´sti okna. Naprˇ´ıklad rˇeteˇzec „easi“ na obra´zku 8 se komprimuje 0 jako (8, 3, i): od pozice 8 zkopı´ruj 3 symboly a prˇipoj symbol c b a i. Pote´ se okno posune o 4 symboly doprava. Varianta metody LZ77 zvana´ deflate od P. Katze je pouzˇita naprˇ´ıklad v kompresnı´m 1 4 8 b a programech zip, gzip. Metoda LZ78 [104] (neboli metoda rostoucı´ho slovnı´ku) vy2 3 a a tva´rˇ´ı slovnı´k ze zakomprimovanyćh dat tak, zˇe sta´vajıćı´ fra´zi ve slovnı´ku rozsˇ´ırˇ´ı o jeden symbol. Data se pak komprimujı´ cˇ´ıs7 5 lem pouzˇite´ fra´ze a na´sledujıćı´m symbolem. Ma´me-li naprˇ´ıklad b slovnı´k na obra´zku 9, pak rˇeteˇzec „abab“ se zakomprimuje jako 6 (7, b), cˇili jako fra´ze cˇ´ıslo 7 rozsˇ´ırˇena´ o symbol b. Na´sledneˇ se do slovnı´ku vlozˇ´ı fra´ze „abab“, jakozˇto fra´ze cˇ´ıslo 9 rozsˇirˇujıćı´ fra´zi cˇ´ıslo 7 o symbol b. Velmi pouzˇ´ıvanou variantou te´to metody Obra´zek 9: Slovnı´k meje metoda LZW [101], ktera´ byla pouzˇita naprˇ´ıklad v kompres- tody LZ78 nı´m programu compress, winzip nebo forma´tech GIF, TIFF, PDF. Patent, ktery´ vyprsˇel v roce 2004, omezil veˇtsˇ´ı rozsˇ´ırˇenı´ te´to metody.

3.3 Kontextove´ metody Kontextove´ metody vyuzˇ´ıvajı´ kontextu aktua´lnı´ho symbolu k dosazˇenı´ efektivneˇjsˇ´ı komprese. V anglicˇtineˇ se naprˇ´ıklad po symbolu q v 99.99 % vyskytuje symbol u. Metoda PPM [27, 77] (Prediction with Partial Matching) je metoda, ktera´ si stavı´ sufixovy´ strom s omezenou hloubkou k. V tomto stromu ma´ ulozˇeny vsˇechny kontexty de´lky k − 1 a v nich se vyskytujıćı´ symboly. Aktua´lnı´ symbol je zako´dovań vzhledem k rozlozˇenı´ pravdeˇpodobnostı´ jednotlivyćh symbolu˚ v dane´m kontextu. V prˇ´ıpadeˇ, zˇe se symbol v dane´m kontextu jesˇteˇ nevyskytoval, je kontext zkraćen. K zako´dovańı´ aktua´lnı´ho symbolu v dane´m kontextu se pak pouzˇ´ıva´ aritmeticke´ ko´dovańı´. Metoda BW [22] (Burrows-Wheeler) pouzˇ´ıva´ Burrows-Wheelerovu transformaci (BWT), ktera´ vytvorˇ´ı vsˇechny cyklicke´ rotace textu t a lexikograficky je serˇadı´. Vy´sledkem transformace je pak poslednı´ sloupec L, viz obra´zek 10. V metodeˇ BW pak za transformacı´ na´sleduje metoda Move-to-Front [14] a Huffmanovo ko´dovańı´. BWT lze vypocˇ´ıtat pomocı´ sufixove´ho 15

t SA BWT

0 s 5 4

1 w 2 1

2 i 7 6

3 s 6 5

4 s 4 3

5 3 2

6 m 8 7

7 i 9 8

8 s 0 9

9 s 1 0

SA 5: 2: 7: 6: 4: 3: 8: 9: 0: 1:

F L missswiss iss misssw issswiss m missswiss s missswis ss missswi ssswiss mi sswiss mis swiss miss wiss misss

Obra´zek 10: Burrows-Wheelerova transformace pole. Oproti metodeˇ PPM, kde je kontext kazˇde´ho symbolu vlevo, v te´to metodeˇ je dı´ky cyklicke´ rotaci kontext vpravo od aktua´lnı´ho symbolu. To take´ urcˇuje smeˇr vyhleda´vańı´ v metodeˇ FM-Index [37], ktera´ je postavena nad Burrows-Wheelerovu transformacı´. Metoda FM-Index si ulozˇ´ı sloupec L pomocı´ vlnkove´ho stromu. Tı´m umozˇnı´ rychle´ nalezenı´ pozice i-te´ho symbolu c v rˇeteˇzci L (operace selectc (L, i)), nebo naopak zjisˇteˇnı´, kolik symbolu˚ c se vyskytuje do pozice j v rˇeteˇzci L (operace rankc (L, j)). Pro sloupec F si stacˇ´ı pro kazˇdy´ symbol abecedy zapamatovat jeho pocˇa´tecˇnı´ pozici v rˇeteˇzci. Vyhleda´vańı´ vzorku p pak probı´ha´ od poslednı´ho symbolu. Nalezneme pozici prvnı´ho (sp) a poslednı´ho (ep) vy´skytu symbolu p[m] v rˇeteˇzci F. V rˇeteˇzci L pak nalezneme symboly L[sp] a L[ep], vyskytujıćı´ se prˇed teˇmito symboly v pu˚vodnı´m textu. Nynı´ pomocı´ operacı´ rank a select nalezneme pozici prvnı´ho (sp′ ) a poslednı´ho (ep′ ) vy´skytu symbolu p[m − 1] v podrˇeteˇzci L[sp..ep]. Pote´ nalezneme ekvivalentnı´ pozice v rˇeteˇzci F a cely´ proces pokracˇuje.

3.4 Proble´my komprese dat rˇesˇene´ autorem a jeho ty´mem Pod vedenı´m autora byl prova´deˇn vy´zkum oblasti hustyćh ko´du˚, vytvorˇenı´ testovacıćho korpusu Prague Corpus a vytvorˇenı´ knihovny implementacı´ kompresnıćh algoritmu˚ ExCom. Prˇi vytva´rˇenı´ te´to knihovy byly vyuzˇity poslednı´ poznatky z oblasti stringologie, takzˇe vznikla vylepsˇenı´ vybranyćh metod [38]. 3.4.1 Komprese prˇirozene´ho textu V oblasti komprese prˇirozenyćh textu˚ se prosadila tzv. slovnı´ komprese (anglicky word-based compression). V nı´ jsou za zdrojove´ jednotky brańa cela´ slova mı´sto jednotlivyćh symbolu˚. Vznikly take´ metody jako slovnı´ Hufmannovo ko´dovańı´ [56] a slovnı´ LZW [56]. Dalsˇ´ım prˇ´ıstupem ke slovnı´ kompresi jsou huste´ ko´dy [21, 19, 20, 84, 85, 87] (anglicky dense codes). V teˇchto metodaćh se slovu˚m z komprimovanyćh textu˚ prˇirˇadı´ jedno- nebo vıće-bajtove´ ko´dy. Vy´hodou slovnı´ komprese je jejı´ maly´ kompresnı´ pomeˇr. Praće s bajty mı´sto bity velmi zrychlı´ kompresi a dekompresi, avsˇak nezhorsˇ´ı o tolik kompresnı´ pomeˇr. V te´to oblasti jsme navrhli ra´mec pro popis vsˇech hustyćh ko´du˚ nazvany´ Open Dense Code (ODC) [84, 87]. Da´le jsme navrhli ko´d Two Byte Dense Code (TBDC) [84, 87], ktery´ omezuje 16

ko´dova´ slova na maxima´lneˇ dva bajty. To je pro obycˇejne´ texty dostacˇujıćı´. Pro male´ soubory jsme dosa´hli nejlepsˇ´ıho kompresnı´ho pomeˇru ze vsˇech hustyćh ko´du˚. Semiadaptivnı´ varianta Semi-adaptive Two Byte Dense Code (STBDC) [85] zase dosahuje nejlepsˇ´ıho kompresnı´ho pomeˇru pro vıćejazycˇne´ texty. Pokud ma´me mnoho relativneˇ kra´tkyćh textu˚, mu˚zˇeme je zakomprimovat pomocı´ kombinace globa´lnı´ho slovnı´ku, ktery´ obsahuje slova spolecˇna´ vsˇem souboru˚m, a loka´lnı´ho slovnı´ku, ktery´ obsahuje slova specia´lnı´ pro ten ktery´ soubor [86]. V takove´m syste´mu pak lze efektivneˇ vyhleda´vat [86] vzorek s vyuzˇitı´m znalostı´ dat v jednotlivyćh slovnıćıćh. Vznikl tak vlastneˇ autoindex postaveny´ na hustyćh ko´dech. 3.4.2 Porovnańı´ kompresnıćh metod Pokud chceme porovna´vat ru˚zne´ kompresnı´ algoritmy, je potrˇeba zı´skat implementace porovna´vanyćh algoritmu˚ nebo testy spustit na stejnyćh datech. Z toho du˚vodu vznikly ru˚zne´ korpusy jako naprˇ´ıklad Calgary Coprus [13], Canterbury Corpus [9], Silesia [33] a Prague Corpus [52]. Nove´ metody jsou otestovańy na stejnyćh datech, proto je mozˇne´ porovnat tyto metody bez nutnosti zı´skańı´ te´ ktere´ implementace. Tı´mto zpu˚sobem se dajı´ ovsˇem porovnat jen kompresnı´ pomeˇry. U kompresnı´ algoritmu˚ je ovsˇem du˚lezˇite´ porovnat i cˇas komprese a dekomprese. V takove´m prˇ´ıpadeˇ je jizˇ nutne´ zı´skat implementace vsˇech porovna´vanyćh metod. Ne vzˇdy se ale podarˇ´ı zı´skat zdrojove´ ko´dy od autoru˚ implementacı´. I kdyzˇ se to podarˇ´ı, je nutne´ implementace jesˇteˇ upravit poprˇ. prˇeve´st do jine´ho programovacı´ho jazyka. To bylo motivacı´ pro vytvorˇenı´ verˇejneˇ prˇ´ıstupne´ knihovny zdrojovyćh ko´du˚ implementacı´ kompresnıćh metod ExCom5 [52] (Extendible Compression library). Cı´lem knihovny je nejen poskytnout zdrojove´ ko´dy pro ućˇely porovnańı´ kompresnıćh metod, ale navıć i testovacı´ prostrˇedı´. Da´le ma´ knihovna slouzˇit programa´toru˚m aplikacı´, aby nemuseli implementovat jizˇ implementovane´ algoritmy, ale mohli prˇ´ımo pouzˇ´ıt tuto knihovnu. Nevı´me o zˇa´dne´ jine´ knihovneˇ, ktera´ by obsahovala takove´ mnozˇstvı´ implementacı´ kompresnıćh algoritmu˚.

5 http://www.stringology.org/projects/ExCom

17

4 Biologie Cı´lem te´to kapitoly je uka´zat aktua´lnı´ proble´m v biologii, ktery´m je obrovske´ mnozˇstvı´ dat, ktere´ je potrˇeba zpracovat. Sekce 4.1 zbeˇzˇneˇ prˇedstavuje motivaci k proble´mu a sekce 4.2 pak ukazuje rˇesˇenı´, na nichzˇ se podı´lel autor tohoto textu.

4.1 Sekvenovańı´ genomu˚ Geneticka´ informace je v organismech uchova´vańa v DNA, neboli deoxyribonukleove´ kyselineˇ. DNA ma´ formu dvojsˇroubovice (viz obra´zek 116 .) a skla´da´ se ze cˇtyrˇ nukleovyćh ba´zı´: adenin (a), guanin (g), cytosin (c) a thymin (t). Mu˚zˇeme se tedy na DNA dı´vat jako na rˇeteˇzec nad abecedou Σ = {a, c, g, t}. DNA sekvence obsahuje geny a neko´dujıćı´ sekvence. Vesˇkerou genetickou informaci obsazˇenou v DNA konkre´tnı´ho organismu pak nazy´va´me genomem. Lidsky´ genom ma´ 3,3 miliardy symbolu˚. Poprve´ byl sekvenovań (prˇecˇten) prˇed 15 lety. Trvalo to celkem 13 let a cena byla 3,3 miliardy dolaru˚. Dnes to trva´ se sekvena´tory nove´ generace (viz obra´zek 127 ) jen dva dny a cena je 8 000 dolaru˚. Sekvena´tory nove´ generace produkujı´ azˇ 60 GB denneˇ [70]. Sekvenacˇnı´ centra majı´ takovyćh stroju˚ stovky, produkujı´ tedy azˇ terabajty dat denneˇ.

Obra´zek 11: DNA

Obra´zek 12: Illumina HiSeq 2500 – sekvena´tor nove´ generace Takove´ mnozˇstvı´ dat je du˚lezˇite´ velmi efektivneˇ ulozˇit a prˇitom umozˇnit rychle´ vyhleda´vańı´. Tı´m se dosta´va´me k vyuzˇitı´ jak oblasti stringologie tak oblasti komprese dat v biologii. Genom se v ra´mci jednoho druhu jen velmi ma´lo lisˇ´ı. Naprˇ´ıklad u lidı´ se genomy dvou jedincu˚ lisˇ´ı 6 Prˇevzato 7 Prˇevzato

18

z http://www.astrochem.org. z http://www.illumina.com.

v 0,1 % symbolech [95]. Tuto vlastnost vsˇak beˇzˇne´ kompresnı´ metody neumı´ vyuzˇ´ıt, je nutne´ pouzˇ´ıt specializovane´ metody. Cˇasteˇjsˇ´ı zmeˇnou mezi dveˇma genomy je zmeˇna typu SNP [95] (anglicky Single-nucleotide polymorphism) neboli jedno-nukleotidovy´ polymorfismus. Je to v podstateˇ na´hrada jednoho nukleotidu jiny´m, rˇecˇ´ı stringologie je to editacˇnı´ operace substituce. Meńeˇ cˇasty´mi zmeˇnami jsou pak vlozˇenı´ a odstraneˇnı´.

4.2 Komprese podobnyćh sekvencı´ Prˇedpokla´dejme, zˇe ma´me r rˇeteˇzcu˚ t 0 , t 1 , . . . , t r −1 ∈ Σ∗ , Σ = {a, c, g, t}, obsahujıćıćh ´ kolem je vytvorˇit nad touto sadou sekvencı´ DNA sekvence ru˚znyćh jedincu˚ stejne´ho druhu. U autoindex umozˇnˇujıćı´ v nich efektivneˇ vyhleda´vat. Prˇi kompresi DNA sekvencı´ vidı´me dva hlavnı´ prˇ´ıstupy, jak se postavit ke zmeˇna´m typu SNP a indel. Prvnı´ zahrnuje nalezenı´ a vyuzˇitı´ opakovańı´ cˇa´sti referencˇnı´ sekvence v komprimovane´ sekvenci. Druhy´ naopak zaznamena´va´ zmeˇny oproti referencˇnı´ sekvenci. Algoritmy z prvnı´ skupiny jsou obvykle zalozˇeny na LZ faktorizaci [103] sekvencı´. Jednı´m z prvnıćh algoritmu˚ zalozˇenyćh na LZ kompresi byl Biocompress [44]. Biocompress byl prvnı´m algoritmem, ktery´ vy´znamneˇ prˇekonal obecne´ kompresnı´ algoritmy prˇi kompresi DNA sekvencı´. Inspiroval podobneˇ zameˇrˇene´ algoritmy pro kompresi DNA jako naprˇ´ıklad Cfact [92] a Off-line [8]. Nicmeńeˇ vy´pocˇet LZ faktorizace je cˇasoveˇ velmi na´rocˇny´ a mu˚zˇe by´t prˇeka´zˇkou nasazenı´ v praxi. Proto autorˇi [67] prˇisˇli s mysˇlenkou relativnı´ faktorizace (RLZ), ktera´ je zalozˇena na odkazech do referencˇnı´ sekvence. Dalsˇ´ım velmi du˚lezˇity´m reprezentantem LZ faktorizace je LZ77 self-index [65], ktery´ kombinuje kompresi a indexovańı´ podobnyćh DNA sekvencı´. Dalsˇ´ım typem kompresnıćh algoritmu˚, ktere´ vyuzˇ´ıvajı´ opakovańı´ biologickyćh sekvencı´, jsou algoritmy zalozˇene´ na gramatikaćh. Tyto metody obvykle nahrazujı´ nejcˇasteˇjsˇ´ı bigramy (dvoupı´smenne´ rˇeteˇzce) netermina´lnı´m symbolem a tyto substituce pak formujı´ pravidla gramatiky. Jednou z neju´speˇsˇneˇjsˇ´ıch kompresnıćh metod je Comrad [66], ktera´ je zalozˇena na algoritmu Ray [23]. Dalsˇ´ı velmi slibnou metodou specia´lneˇ pro sekvence s vysokou podobnostı´ a pro hledańı´ kra´tkyćh sekvencı´ je Grammar-compressed self-index [26] zalozˇena´ na algoritmu RePair [68]. Prvnı´ metodou druhe´ho prˇ´ıstupu, cˇili zaznamena´vańı´ zmeˇn, je metoda Christie a kol. [24], kde je dosazˇeno komprese ukla´dańı´m zmeˇn komprimovane´ sekvence oproti referencˇnı´ sekvenci. Dalsˇ´ı metodou je Generalized compressed suffix array (GCSA) [96], ktera´ je zalozˇena na principu ukla´dańı´ sekvencı´ jako konecˇne´ho automatu, ktery´ je pak zaindexovań pomocı´ komprimovane´ho sufixove´ho pole. Dalsˇ´ı metoda byla navrzˇena v [57]. Pouzˇ´ıva´ BurrowsWheelerovu transformaci [22] na shodne´ segmenty a sufixove´ pole na zmeˇnove´ segmenty, aby mohla detekovat vsˇechny vy´skyty hledane´ho vzorku.

4.3 Proble´my bioinformatiky rˇesˇene´ autorem a jeho ty´mem 4.3.1 Vyhleda´vańı´ v genomech Pro vyhleda´vańı´ v genomech se dajı´ vyuzˇ´ıt techniky pro prˇesne´ vyhleda´vańı´ (viz sekce 2.1 a 2.2) i pro prˇiblizˇne´ vyhleda´vańı´ (viz sekce 2.3). Ve vyhleda´vańı´ se vyuzˇ´ıvajı´ i neurcˇite´ rˇeteˇzce. Naprˇ´ıklad aminokyselina isoleucin je ko´dovańa jako atH, kde H zastupuje symboly a, c a t. Podrobneˇji o tomto te´matu pojedna´va´ kapitola v knize [49]. 19

4.3.2 Komprese podobnyćh sekvencı´ vlnkov´ y strom t0

$ a ...a

t

100110101001 110110

000110

BW T (t0 )

1110

isLoc 0 0 0 0 1 0 ...

$

loc

g

c

0

t

a

Obra´zek 13: FM-index I0 vytvorˇeny´ pro referencˇnı´ sekvenci t 0

t0

...

a

...

ti

...

c

...

d

# ... c

sampleStart vlnkov´ y strom $ # ... #

t

100110101001

2 × lc − 1 ...

# +

isLoc 0 0 0 0 1 0 ...

1110

101

a

0 $

loc

aIndex

010110

000110

BW T (d )

#

c

t g

+

aBasePos aOffset aOp

Obra´zek 14: FM-index Id vytvorˇeny´ pro zrˇeteˇzenı´ za´znamu˚ zmeˇn d

Metoda BIO-FMI [88] vyuzˇ´ıva´ metody FM-index [37]. Touto metodou vytvorˇ´ı index I0 (viz obra´zek 13) nad referencˇnı´ sekvencı´ t 0 a oddeˇleny´ index Id (viz obra´zek 14) nad ˇreteˇzci reprezentujıćı´mi zmeˇny jednotlivyćh sekvencı´ t i , 0 < i < r, oproti referencˇnı´ sekvenci t 0 . Parametrem te´to metody je de´lka l c , na kterou je hledany´ vzorek p rozdeˇlen. Jednotlive´ cˇa´sti vzorku p jsou pak vyhleda´vańy jak v I0 tak v Id . Z nalezenyćh vy´skytu˚ jsou nakonec poskla´dańy vsˇechny vy´skyty vzorku p ve vsˇech sekvencıćh t i . Z experimenta´lnıćh vy´sledku˚ uvedenyćh v tabulce 4 vyply´va´, zˇe pro male´ velikosti de´lky l c dosahuje tato metoda nejlepsˇ´ıho kompresnı´ho pomeˇru (azˇ 2,26 %) a nejrychlejsˇ´ıho cˇasu vyhleda´vańı´. Na stroji s procesorem R Intel CoreTM 2 Duo CPU T6600 2, 20 GHz s 4 GB RAM je rychlost vyhleda´vańı´ pro nejmensˇ´ı vzorky (5 znaku˚) 2, 56 µs. Jiny´ prˇ´ıstup byl zvolen u metody [79], kde se vytva´rˇ´ı kompaktnı´ sufixovy´ strom. Ma´me-li dva rˇeteˇzce t 0 = aaabaaabbaaba# a t 1 = aaabaabaabbaba$. Oba tyto rˇeteˇzce mohu zapsat jako rˇeteˇzec s variacemi t 0+1 = aaabaa(abba/baabb)aba#. Metoda [79] vytva´ˇr´ı kompaktnı´ sufixovy´ strom pro rˇeteˇzec t 0+1 (viz obra´zek 15). Vy´sledny´ strom se pak da´ pouzˇ´ıt stejneˇ jako standardnı´ kompaktnı´ sufixovy´ strom. Na rozdı´l od zobecneˇne´ho kompaktnı´ho sufixove´ho stromu (anglicky generalized suffix tree) [5, 45], ktery´ stavı´ kompaktnı´ sufixovy´ 20

File m lc BIO-FMI RLCSA LZ77 LZ-End

5 5 2.26 % 2.56 µ s 6.38 % 13.83 µ s 3.47 % 133.96 µ s 6.19 % 33.60 µ s

s001 10 5 10 2.26 % 2.99 % 993.88 µ s 3.80 µ s 6.38 % 12.71 µ s 3.47 % 156.16 µ s 6.19 % 44.41 µ s

20 10 2.99 % 28.97 µ s

20 5.08 % 25.77 µ s 6.38 % 18.26 µ s 3.47 % 164.95 µ s 6.19 % 154.64 µ s

s005 10 5 10 6.01 % 8.69 % 956.41 µ s 3.71 µ s 9.32 % 22.78 µ s 8.18 % 122.85 µ s 16.01 % 83.22 µ s

5 5 6.01 % 2.37 µ s 9.32 % 19.83 µ s 8.18 % 82.10 µ s 16.01 % 44.00 µ s

20 10 8.69 % 30.83 µ s

20 14.15 % 25.94 µ s 9.32 % 23.80 µ s 8.18 % 166.67 µ s 16.01 % 156.25 µ s

Tabulka 4: Kompresnı´ pomeˇr a cˇasy nalezenı´ pro soubory s001 a s005 (pravdeˇpodobnost zmeˇny mezi t i a t 0 je 0, 1 % respektive 0, 5 %). strom pro zrˇeteˇzenı´ obou rˇeteˇzcu˚ a ma´ pameˇt’ovou na´rocˇnost danou soucˇtem obou rˇeteˇzcu˚, ma´ metoda [79] slozˇitost dańu jako O(n + l d + l 1 ), kde l d je soucˇet de´lek odlisˇnyćh segmentu˚ a l 1 je soucˇet neˇkteryćh spolecˇnyćh segmentu˚.

b

a

a#

a

bab

a#

a#

abb

a#

aab

aab

ab

a#

a

a a#

ab

ab bb

#

aa

ba

a#

ba

ab

bab

ba

ba# b)a aab

#

b

a/b

#

b

ba

a#

#

#

ba

ba

baab

abb

ba

a

b

ab

aa(

b

#

ab

a

Obra´zek 15: Kompaktnı´ sufixovy´ strom pro rˇeteˇzec s variacemi

21

5 Za´veˇr V textu byly prˇedstaveny vybrane´ proble´my z oblasti stringologie a komprese data jejich rˇesˇenı´. Tyto obory spojily sve´ u´silı´, ktere´ vedlo ke vzniku zhusˇteˇnyćh indexu˚ a autoindexu˚ poskytujıćh plnou funkcionalitu u´plne´ho indexu a za´rovenˇ u´sporneˇ ukla´dajıćh vstupnı´ text. Na´stup novyćh technologiı´ v biologii, ktere´ generujı´ obrovska´ mnozˇstvı´ dat, prˇina´sˇ´ı nove´ vy´zvy pro kompresi dat v podobeˇ nutnosti u´sporne´ho ukla´dańı´. Navıć nad takto zakomprimo´ speˇsˇne´ zvla´dnutı´ vany´mi daty je potrˇeba prova´deˇt vyhleda´vańı´, cozˇ je vy´zva pro stringologii. U prvnı´ho proble´mu znamena´, zˇe sekvenacˇnı´ centra nebudou muset zı´skana´ data po prohledańı´ ´ speˇsˇne´ zvla´dnutı´ druhe´ho proble´mu mazat, ale budou je moci uchova´vat pro dalsˇ´ı pouzˇitı´. U pak znamena´ vyhleda´vańı´ v datech bez jejich dekomprese, cozˇ podstatneˇ urychlı´ proces vyhleda´vańı´. Oba dva tyto proble´my rˇesˇ´ı metoda BIO-FMI [88], cozˇ bylo podporˇeno provedeny´mi experimenty ukazujıćı´mi kompresnı´ pomeˇr azˇ 2,26 %. Dalsˇ´ı rˇesˇenı´ pomocı´ kompaktnı´ho sufixove´ho stromu pro rˇeteˇzce s variacemi [79] na sve´ experimenta´lnı´ vyhodnocenı´ teprve cˇeka´. Obeˇ metody vyuzˇ´ıvajı´ vysoke´ podobnosti komprimovanyćh dat, ktera´ v prˇ´ıpadeˇ lidskyćh genomu˚ ru˚znyćh jedincu˚ cˇinı´ 99,9 %. Autor tohoto textu se podı´lel na urcˇenı´ za´kladnıćh vlastnostı´ neurcˇityćh rˇeteˇzcu˚ [53], ktere´ se dajı´ pouzˇ´ıt naprˇ´ıklad pro popis a vyhleda´vańı´ aminokyselin. Da´le se podı´lel na na´vrhu prvnı´ho efektivnı´ho algoritmu [54] pro vyhleda´vańı´ v neurcˇityćh rˇeteˇzcıćh, Mezi dalsˇ´ı praće autora patrˇ´ı efektivnı´ implementace indexovacı´ struktury zvane´ kompaktnı´ sufixovy´ automat, kde dosa´hl vy´znamne´ho zlepsˇenı´ pameˇt’ove´ slozˇitosti (cca 5 kra´t), cˇ´ımzˇ se tento automat stal prakticky pouzˇitelny´. Da´le autor dosa´hl vy´znamnyćh vy´sledku˚ v oblasti komprese prˇirozene´ho jazyka pomocı´ hustyćh ko´du˚ [84, 85, 87] a v oblasti testovańı´ vy´konnosti kompresnıćh metod (knihovna efektivnıćh implementacı´ kompresnıćh metod ExCom [52] a testovacı´ sada souboru˚ Prague Corpus [52]). V oblasti stringologie pak uka´zal, zˇe metody pouzˇ´ıvane´ pro prˇiblizˇne´ vyhleda´vańı´ simulujı´ praći nedeterministicke´ho konecˇne´ho automatu pro prˇiblizˇne´ vyhleda´vańı´ [47, 48]. O oblast komprese dat je velky´ za´jem. Datova´ centra prˇi pouzˇitı´ efektivnıćh algoritmu˚ na kompresi dat sˇetrˇ´ı na´klady na energie za servery a jejich chlazenı´. Komprese dat urychluje prˇenos dat. Biologie bez efektivnı´ komprese dat nemu˚zˇe uchova´vat zı´skana´ data. Spojenı´ oblastı´ stringologie a komprese dat umozˇnˇuje vyhleda´vańı´ nad rozsa´hly´mi biologicky´mi daty, cozˇ je velmi du˚lezˇite´ pro identifikaci prˇ´ıcˇin nemocı´ a nalezenı´ efektivnı´ lećˇby.

22

Pouzˇita´ literatura [1] N. Abramson. Information Theory and Coding. McGraw-Hill, New York, 1963. [2] A. V. Aho and M. J. Corasick. Efficient string matching: an aid to bibliographic search. Commun. ACM, 18(6):333–340, 1975. [3] A. V. Aho, J. E. Hopcroft, and J. D. Ullman. The design and analysis of computer algorithms. Addison-Wesley, Reading, MA, 1974. [4] C. Allauzen, M. Crochemore, and M. Raffinot. Factor oracle: A new structure for pattern matching. In J. Pavelka, G. Tel, and M. Bartosˇek, editors, SOFSEM’99, Theory and Practice of Informatics, number 1725 in Lecture Notes in Computer Science, pages 295–310, Milovy, Czech Republic, 1999. Springer-Verlag, Berlin. [5] A. Amir, M. Farach, Z. Galil, R. Giancarlo, and K. Park. Dynamic dictionary matching. J. Comput. Syst. Sci., 49(2):208–222, 1994. [6] A. Amir, M. Farach, and S. Muthukrishnan. Alphabet dependence in parameterized matching. Inf. Process. Lett., 49(3):111–115, 1994. [7] P. Antoniou, J. Holub, C. S. Iliopoulos, B. Melichar, and P. Peterlongo. Finding common motifs with gaps using finite automata. In O. H. Ibarra and H.-C. Yen, editors, Implementation and Application of Automata, number 4094 in Lecture Notes in Computer Science, pages 69–77. Springer-Verlag, Heidelberg, 2006. [8] A. Apostolico and S. Lonardi. Compression of biological sequences by greedy off-line textual substitution. In J. A. Storer and M. Cohn, editors, Proceedings Data Compression Conference, pages 143–152, Snowbird, UT, 2000. IEEE Computer Society Press. [9] R. Arnold and T. C. Bell. A corpus for the evaluation of lossless compression algorithms. In Data Compression Conference, pages 201–210, 1997. [10] R. A. Baeza-Yates and G. H. Gonnet. A new approach to text searching. Commun. ACM, 35(10):74–82, 1992. [11] B. S. Baker. A theory of parameterized pattern matching: algorithms and applications. In Proceedings of the 25th ACM Symposium on the Theory of Computing, pages 71–80, San Diego, CA, 1993. ACM Press. [12] M. Balı´k. DAWG versus suffix array. In J.-M. Champarnaud and D. Maurel, editors, Implementation and Application of Automata, number 2608 in Lecture Notes in Computer Science, pages 233–238. Springer-Verlag, Heidelberg, 2003. [13] T. C. Bell, I. H. Witten, and J. G. Cleary. Modeling for text compression. ACM Comput. Surv., 21(4):557–591, 1989. [14] J. L. Bentley, D. D. Sleator, R. E. Tarjan, and V. H. Wei. A locally adaptive data compression scheme. Commun. ACM, 29(4):320–330, April 1986. 23

[15] A. Blumer, J. Blumer, A. Ehrenfeucht, D. Haussler, M. T. Chen, and J. Seiferas. The smallest automaton recognizing the subwords of a text. Theor. Comput. Sci., 40(1):31– 55, 1985. [16] A. Blumer, J. Blumer, A. Ehrenfeucht, D. Haussler, and R. McConnel. Linear size finite automata for the set of all subwords of a word: an outline of results. Bull. Eur. Assoc. Theor. Comput. Sci., 21:12–20, 1983. [17] A. Blumer, A. Ehrenfeucht, and D. Haussler. Average size of suffix trees and DAWGS. Discret. Appl. Math., 24:37–45, 1989. [18] R. S. Boyer and J. S. Moore. A fast string searching algorithm. Commun. ACM, 20(10):762–772, 1977. [19] N. R. Brisaboa, A. Fariña, G. Navarro, and M. F. Esteller. (S, C)-dense coding: An optimized compression code for natural language text databases. In M. A. Nascimento, E. S. de Moura, and A. L. Oliveira, editors, Proceedings of String Processing and Information Retrieval, volume 2857 of Lecture Notes in Computer Science, pages 122– 136. Springer-Verlag, Berlin, 2003. [20] N. R. Brisaboa, A. Fariña, G. Navarro, and J. R. Parama´. Lightweight natural language text compression. Inf. Retr., 10(1):1–33, January 2007. [21] N. R. Brisaboa, E. L. Iglesias, G. Navarro, and J. R. Parama. An efficient compression code for text databases. In F. Sebastiani, editor, Advances in Information Retrieval, volume 2633 of Lecture Notes in Computer Science, pages 468–481. Springer-Verlag, Berlin, 2003. [22] M. Burrows and D. J. Wheeler. A block-sorting lossless data compression algorithm. SRC Research Report 124, Digital Equipment Corporation, 1994. [23] A. Cannane and H. E. Williams. General-purpose compression for efficient retrieval. J. Am. Soc. Inf. Sci. Technol, 52(5):430–437, 2001. [24] S. Christley, Y. Lu, C. Li, and X. Xie. Human genomes as email attachments. Bioinformatics, 25(2):274–275, 2009. [25] D. R. Clark. Compact pat trees. PhD thesis, University of Waterloo, Waterloo, Ont., Canada, Canada, 1996. [26] F. Claude, A. Fariña, M. A. Martinez-Prieto, and G. Navarro. Compressed q-gram indexing for highly repetitive biological sequences. In BioInformatics and BioEngineering, pages 86–91. IEEE Computer Society, 2010. [27] J. G. Cleary and I. H. Witten. Data compression using adaptive coding and partial string matching. IEEE Trans. Comput., 32:396–402, 1984. [28] B. Commentz-Walter. A string matching algorithm fast on the average. In H. A. Maurer, editor, Proceedings of the 6th International Colloquium on Automata, Languages and Programming, number 71 in Lecture Notes in Computer Science, pages 118–132, Graz, Austria, 1979. Springer-Verlag, Berlin. 24

[29] M. Crochemore. Transducers and repetitions. Theor. Comput. Sci., 45(1):63–86, 1986. [30] M. Crochemore and W. Rytter. Text algorithms. Oxford University Press, 1994. [31] M. Crochemore and R. Ve´rin. Direct construction of compact directed acyclic word graphs. In A. Apostolico and J. Hein, editors, Proceedings of the 8th Annual Symposium on Combinatorial Pattern Matching, number 1264 in Lecture Notes in Computer Science, pages 116–129, Aarhus, Denmark, 1997. Springer-Verlag, Berlin. [32] F. Damerau. A technique for computer detection and correction of spelling errors. Commun. ACM, 7(3):171–176, 1964. [33] S. Deorowicz. Silesia Corpus. PhD thesis, Silesian University of Technology, Poland, 2003. [34] B. Do¨mo¨lki. An algorithm for syntactical analysis. Computational Linguistics, 3:29–46, 1964. Hungarian Academy of Science, Budapest. ˇ urian, J. Holub, H. Peltola, and J. Tarhio. Improving practical exact string matching. [35] B. D Inf. Process. Lett., 110(4):148–152, 2010. [36] R. Fano. The transmission of information. Technical Report 65, Research Laboratory of Electronics, MIT, 1949. [37] P. Ferragina and G. Manzini. Opportunistic data structures with applications. In FOCS 2000: Proceedings of the 41st Annual Symposium on Foundations of Computer Science, pages 390–398, Washington, DC, USA, 2000. IEEE Computer Society. [38] M. Fiala and J. Holub. Dca using suffix arrays. In J. A. Storer and M. W. Marcellin, editors, Data Compression Conference, page 516. IEEE Computer Society, 2008. [39] M. J. Fischer and M. Paterson. String matching and other products. In R. M. Karp, editor, Proceedings SIAM-AMS Complexity of Computation, pages 113–125, Providence, RI, 1974. [40] E. Fredkin. Trie memory. Commun. ACM, 3(9):490–499, 1960. [41] Z. Galil. Open problems in stringology. In A. Apostolico and Z. Galil, editors, Combinatorial Algorithms on Words, volume 12 of NATO ASI Series F, pages 1–8. SpringerVerlag, Berlin, 1985. [42] R. Grossi, A. Gupta, and J. Vitter. High-order entropy-compressed text indexes. In Proc. 14th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA’03), pages 841– 850, 2003. [43] R. Grossi and J. S. Vitter. Compressed suffix arrays and suffix trees with applications to text indexing and string matching. In Proceedings ACM Symposium on the Theory of Computing, pages 397–406, Portland, Oregon, 2000. ACM Press. [44] S. Grumbach and F. Tahi. Compression of dna sequences. In J. A. Storer and M. Cohn, editors, Data Compression Conference, pages 340–350. IEEE Computer Society, 1993. 25

[45] D. Gusfield. Algorithms on strings, trees and sequences: computer science and computational biology. Cambridge University Press, Cambridge, 1997. [46] R. W. Hamming. Error detecting and error correcting codes. The Bell System Technical Journal, 29(2):147–160, 1950. [47] J. Holub. Bit parallelism—NFA simulation. In B.W. Watson and D. Wood, editors, Implementation and Application of Automata, number 2494 in Lecture Notes in Computer Science, pages 149–160. Springer-Verlag, Heidelberg, 2002. [48] J. Holub. Dynamic programming—NFA simulation. In J.-M. Champarnaud and D. Maurel, editors, Proceedings of the 7th Conference on Implementations and Applications of Automata, pages 287–292, University of Tours, Tours, France, 2002. [49] J. Holub. Finite automata in pattern matching. In M. Elloumi and A. Y. Zomaya, editors, Algorithms in Computational Molecular Biology: Techniques, Approaches and Applications, pages 51–71. John Wiley & Sons, 2011. [50] J. Holub and M. Crochemore. On the implementation of compact DAWG’s. In J.-M. Champarnaud and D. Maurel, editors, Implementation and Application of Automata, number 2608 in Lecture Notes in Computer Science, pages 289–294. Springer-Verlag, Heidelberg, 2003. [51] J. Holub and B. Melichar. Approximate string matching using factor automata. Theor. Comput. Sci., 249(2):305–311, 2000. ˇ eznıćˇek, and F. Sˇimek. Lossless data compression testbed: ExCom and [52] J. Holub, J. R Prague Corpus. In J. A. Storer and M. W. Marcellin, editors, Data Compression Conference, page 457. IEEE Computer Society, 2011. [53] J. Holub and W. F. Smyth. Algorithms on indeterminate strings. In M. Miller and K. Park, editors, Proceedings of the 14th Australasian Workshop On Combinatorial Algorithms, pages 36–45. Seoul National University, Seoul, Korea, 2003. [54] J. Holub, W. F. Smyth, and S. Wang. Fast pattern-matching on indeterminate strings. J. Discret. Algorithms, 6(1):37–50, 2008. [55] R. N. Horspool. Practical fast searching in strings. Softw. Pract. Exp., 10(6):501–506, 1980. [56] R.N. Horspool and G.V. Cormack. Constructing word-based text compression algorithms. In J.A. Storer and M. Cohn, editors, Data Compression Conference, pages 62–81, Snowbird, Utah, March 1992. IEEE Computer Society Press, Los Alamitos, California. [57] S. Huang, T. W. Lam, W.-K. Sung, S.-L. Tam, and S.-M. Yiu. Indexing similar dna sequences. In B. Chen, editor, Algorithmic Aspects in Information and Management, volume 6124 of Lecture Notes in Computer Science, pages 180–190. Springer, 2010. [58] D. A. Huffman. A method for the construction of minimum-redundancy codes. Proceedings of the Institute of Radio Engineers, 40(9):1098–1101, September 1952. 26

[59] A. Hume and D. M. Sunday. Fast string searching. Softw. Pract. Exp., 21(11):1221– 1248, 1991. [60] C. S. Iliopoulos, M. Mohamed, L. Mouchard, K. Perdikuri, W. F. Smyth, and A. Tsakalidis. String regularities with don’t cares. Nordic J. Comput., 10(1):40–51, 2003. [61] S. Inenaga, H. Hoshino, A. Shinohara, M. Takeda, S. Arikawa, G. Mauri, and G. Pavesi. On-line construction of compact directed acyclic word graphs. Lecture Notes in Computer Science, 2089:169–180, 2001. [62] G. Jacobson. Space-efficient static trees and graphs. In Annual IEEE Symposium on Foundations of Computer Science, pages 549–554, Los Alamitos, CA, USA, 1989. IEEE Computer Society. [63] D. E. Knuth, J. H. Morris, Jr, and V. R. Pratt. Fast pattern matching in strings. SIAM J. Comput., 6(2):323–350, 1977. [64] L. G. Kraft. A device for quantizing, grouping, and coding amplitude modulated pulses. Master’s thesis, Department of Electrical Engineering, MIT, 1949. [65] S. Kreft and G. Navarro. Self-indexing based on LZ77. In R. Giancarlo and G. Manzini, editors, Combinatorial pattern matching, volume 6661 of Lecture Notes in Computer Science, pages 41–54. Springer, 2011. [66] S. Kuruppu, B. Beresford-Smith, T. Conway, and J. Zobel. Iterative dictionary construction for compression of large dna data sets. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 9(1):137–149, 2012. [67] S. Kuruppu, S. J. Puglisi, and J. Zobel. Relative lempel-ziv compression of genomes for large-scale storage and retrieval. In E. Cha´vez and S. Lonardi, editors, String Processing and Information Retrieval, volume 6393 of Lecture Notes in Computer Science, pages 201–206. Springer, 2010. [68] N. J. Larsson and A. Moffat. Offline dictionary-based compression. In Data Compression Conference, pages 296–305. IEEE Computer Society, 1999. [69] V. I. Levenshtein. Binary codes capable of correcting deletions, insertions and reversals. Sov. Phys. Dokl., 6:707–710, 1966. [70] L. Liu, Y. Li, S. Li, N. Hu, Y. He, R. Pong, D. Lin, L. Lu, and M. Law. Comparison of next-generation sequencing systems. BioMed Research International, 2012. [71] U. Manber and G. Myers. Suffix arrays: a new method for on-line string searches. SIAM J. Comput., 22(5):935–948, 1993. [72] M. A. Maniscalco and S. J. Puglisi. An efficient, versatile approach to suffix sorting. J. Exp. Algorithmics, 12:1.2:1–1.2:23, June 2008. [73] E. M. McCreight. A space-economical suffix tree construction algorithm. J. Algorithms, 23(2):262–272, 1976. 27

[74] B. McMillan. Two inequalities implied by unique decipherability. IRE Transactions on Information Theory, 2(4):115–116, December 1956. [75] B. Melichar. Approximate string matching by finite automata. In V. Hlavaćˇ and R. Sˇa´ra, editors, Computer Analysis of Images and Patterns, number 970 in Lecture Notes in Computer Science, pages 342–349. Springer-Verlag, Berlin, 1995. [76] B. Melichar. String matching with k differences by finite automata. In Proceedings of the 13th International Conference on Pattern Recognition, volume II., pages 256–260, Vienna, Austria, 1996. IEEE Computer Society Press. [77] A. Moffat. Implementing the ppm data compression scheme. IEEE Trans. Comms., 38(11):1917–1921, November 1990. [78] J. I. Munro. Tables. In V. Chandru and V. Vinay, editors, Foundations of Software Technology and Theoretical Computer Science, volume 1180 of Lecture Notes in Computer Science, pages 37–42. Springer Berlin Heidelberg, 1996. [79] J. C. Na, H. Park, M. Crochemore, J. Holub, C. S. Iliopoulos, L. Mouchard, and K. Park. Suffix tree of alignment: An efficient index for similar data. In T. Lecroq and L. Mouchard, editors, Proceedings of the 24th Workshop on Combinatorial Algorithms, number 8288 in Lecture Notes in Computer Science, pages 337–348, 2013. [80] G. Navarro and V. Ma¨kinen. Compressed full-text indexes. ACM Comput. Surv., 39(1), April 2007. [81] G. Navarro and M. Raffinot. Fast and flexible string matching by combining bitparallelism and suffix automata. ACM Journal of Experimental Algorithmics (JEA), 5(4), 2000. http://www.jea.acm.org/2000/NavarroString. [82] R. C. Pasco. Source Coding Algorithms for Fast Data Compression. Ph.D. dissertation, Department of Electrical Engineering, Stanford University, Stanford, CA, USA, 1976. [83] H. Peltola and J. Tarhio. Alternative algorithms for bit-parallel string matching. In M. A. Nascimento, E. S. Moura, and A. L. Oliveira, editors, String Processing and Information Retrieval, volume 2857 of Lecture Notes in Computer Science, pages 80– 93. Springer-Verlag, Berlin, 2003. [84] P. Procha´zka and J. Holub. New word-based adaptive dense compressors. In J. Fiala, J. Kratochvı´l, and M. Miller, editors, Combinatorial Algorithms, number 5874 in Lecture Notes in Computer Science, pages 420–431. Springer-Verlag, Heidelberg, 2009. [85] P. Procha´zka and J. Holub. Natural language compression per blocks. In Proceedings of the First International Conference on Data Compression, Communications and Processing, pages 67–75. IEEE Computer Society Press, 2011. [86] P. Procha´zka and J. Holub. Natural language compression optimized for large set of files. In A. Bilgin, M. W. Marcellin, J. Serra-Sagrista`, and J. A. Storer, editors, Data Compression Conference, page 514, Washington, DC, USA, 2013. IEEE Computer Society Press. 28

[87] P. Procha´zka and J. Holub. ODC: Frame for definition of dense codes. Eur. J. Comb., 34(1):52–68, 2013. [88] P. Procha´zka and J. Holub. A compressing similar biological sequences using fm-index. In Data Compression Conference, pages 312–321, Washington, DC, USA, 2014. IEEE Computer Society Press. To appear. [89] S. J. Puglisi, W. F. Smyth, and A. Turpin. A taxonomy of suffix array construction algorithms. ACM Comput. Surv., 39(2), July 2007. [90] J. Ramsden. Bioinformatics: An Introduction. Computational Biology. Springer-Verlag, Berlin, 2009. [91] J. J. Rissanen. Generalized Kraft inequality and arithmetic coding. IBM Journal of Research and Development, 20(3):198–203, May 1976. [92] E. Rivals, J-P. Delahaye, M. Dauchet, and O. Delgrange. A guaranteed compression scheme for repetitive dna sequences. In J. A. Storer and M. Cohn, editors, Data Compression Conference, page 453. IEEE Computer Society, 1996. [93] K. Sadakane. Compressed text databases with efficient query algorithms based on the compressed suffix array. In G. Goos, J. Hartmanis, J. Leeuwen, D. T. Lee, and S.-H. Teng, editors, Algorithms and Computation, volume 1969 of Lecture Notes in Computer Science, pages 410–421. Springer Berlin Heidelberg, 2000. [94] P. H. Sellers. The theory and computation of evolutionary distances: Pattern recognition. J. Algorithms, 1(4):359–373, 1980. [95] B. S. Shastry. SNP alleles in human disease and evolution. J. Hum. Genet., 47(11):561– 566, 2002. [96] J. Sireń, N. Va¨lima¨ki, and V. Ma¨kinen. Indexing finite language representation of population genotypes. In T. M. Przytycka and M.-F. Sagot, editors, Algorithms in Bioinformatics, volume 6833 of Lecture Notes in Computer Science, pages 270–281. Springer, 2011. [97] D. M. Sunday. A very fast substring search algorithm. Commun. ACM, 33(8):132–142, 1990. [98] E. Ukkonen. Finding approximate patterns in strings. J. Algorithms, 6(1–3):132–137, 1985. [99] E. Ukkonen. On-line construction of suffix trees. Algorithmica, 14(3):249–260, 1995. [100] P. Weiner. Linear pattern matching algorithm. In Proceedings of the 14th Annual IEEE Symposium on Switching and Automata Theory, pages 1–11, Washington, DC, 1973. [101] T. A. Welch. A technique for high-performance data compression. Computer, 17(6):8– 19, June 1984. [102] R. F. Zhu and T. Takaoka. On improving the average case of the Boyer-Moore string matching algorithm. J. Inform. Process., 10(3):173–177, 1987. 29

[103] J. Ziv and A. Lempel. A universal algorithm for sequential data compression. IEEE Trans. Inf. Theory, 23:337–343, May 1977. [104] J. Ziv and A. Lempel. Compression of individual sequences via variable length coding. IEEE Trans. Inf. Theory, 24:530–536, 1978.

30

Abstrakt Praće prˇedstavuje pohled na sblizˇovańı´ oboru˚ stringologie (teorie o zpracovańı´ rˇeteˇzcu˚ a posloupnostı´), komprese dat a biologie. Nejdrˇ´ıve je uveden prˇehled ru˚znyćh proble´mu˚ z oblasti stringologie a komprese dat a jejich rˇesˇenı´. V prˇehledu jsou zmıńeˇny vy´sledky autora v oblasti neurcˇityćh rˇeteˇzcu˚, prˇesne´ho a prˇiblizˇne´ho vyhleda´vańı´, u´plne´ho indexu, komprese prˇirozene´ho jazyka a porovna´vańı´ vy´konu kompresnıćh metod. Pote´ je prˇedstavena oblast biologie, kde soucˇasne´ technologie produkujı´ obrovska´ mnozˇstvı´ vza´jemneˇ podobnyćh dat. Propojenı´m oblastı´ stringologie, komprese dat a biologie je pak komprimovany´ u´plny´ index specializovany´ na takova´ biologicka´ data. Jsou prˇedstaveny dva efektivnı´ algoritmy na kompresi takovyćh dat a za´rovenˇ jejich prohleda´vańı´, ktere´ byly navrzˇeny autorem.

Abstract The work presents convergence of three fields: stringology (theory of string and sequence processing), data compression and biology. First a survey of various problems and their solutions in the fields of stringology and data compression is presented. Author’s results in the fields are also presented, namely degenerate strings, exact and approximate string matching, fulltext index, natural language compression and performance of data compression methods. Then the field of biology is introduced, where current technologies produce a huge amount of similar data. The interconnection of the fields of stringology, data compression, and biology is a compressed fulltext index tailored to such biological data. Two efficient algorithms designed by the author for compression of such data and searching are introduced.

31

VYSOKÉ UČENÍ TECHNICKÉ V BRNĚ

Recommend Documents