|
|
Vyhledávání přibližných palindromů v DNA sekvencích
Remiáš, Richard ; Burgetová, Ivana (oponent) ; Martínek, Tomáš (vedoucí práce)
Práca sa zaoberá problematikou vyhľadávania presných a približných palindrómov. V súvislosti s vyhľadávaním presných palindrómov analyzuje naivný postup vyhľadávania ako aj postupy založené na sufixových stromoch, ktorých konštrukcia je tiež rozobraná. Vyhľadávanie približných palindrómov je realizované za pomoci princípov dynamického programovania. Samotné vyhľadávanie je rozdelené na tri časti: vyhľadanie palindrómov, filtrácia výsledkov a ich rekonštrukcia. Každá časť je popísaná algoritmom a implementovaná programom v prílohe práce.
|
|
|
Konstrukce sufixových stromů a jejich využití v bioinformatice
Hlaváček, Pavel ; Čermák, Martin (oponent) ; Martínek, Tomáš (vedoucí práce)
Práce se zabývá problematikou implementace sufixových stromů a jejich využití v bioinformatice. Jsou zde uvedeny různé druhy algoritmů pro tvorbu sufixových stromů. Především se zabývá implementací on-line metody pro tvorbu sufixového stromu navrženou E. Ukkonenem a přibližným vyhledáváním podřetězců. To je realizováno za pomoci dynamického programování, upraveného pro využití sufixových stromů. Obě tyto metody jsou popsány pseudokódem a implementovány v příloze práce.
|
|
|
Možnosti využití sufixových stromů
Chlubna, Pavel ; Hynek, Jiří (oponent) ; Burgetová, Ivana (vedoucí práce)
Tato práce pojednává o struktuře sufixových stromů, jejich implementaci a problematice, kterou pomocí sufixových stromů řešíme. Práce se také zaměřuje na konstrukci sufixového stromu, pomocí Ukkonenova algoritmu. Kromě samotné implementace se práce také zabývá porovnáním jiných používaných algoritmů se sufixovými stromu, z hlediska časové náročnosti. Výstupem této práce je ucelená aplikace s grafickým rozhraním, která demonstruje využití sufixových stromů při řešení různých problematik a nabízí porovnání této struktury s jinými algoritmy.
|
|
|
Suffix tree construction with minimized branching
Bašista, Peter ; Dvořák, Tomáš (vedoucí práce) ; Kadlec, Rudolf (oponent)
Sufixový strom je datová struktura, která v textu umožňuje rychle vykonávat operace podobné vyhledávání. Aby ji bylo možné používat efektivně, musí být vytvořená rychle. V této práci se zaměříme na nový způsob simulace sufixových hran nazývaný "minimalizace větvení", který se snaží zvýšit rychlost konstrukce sufixového stromu pomocí znížení počtu větvícich operací. Naš hlavní cíl je předvést porovnání současných metod pro konstrukci sufixového stromu a poukázat na některé výhody a nevýhody jednotlivých postupů. Představíme, implementujeme a prakticky posoudíme několik variant standardních algoritmů jako jsou McCreightův a Ukkonenův, stejně tak jako algoritmu PWOTD, který byl původně navržen pro diskově orientovanou konstrukci. Náším hlavním výsledkem je ucelený popis a implementace těchto algoritmů, na kterých se dá dále stavět. Také předložíme jednoduchá doporučení ohledně toho kdy je vhodné použít konkrétní algoritmus a proč.
|
|
|
Možnosti využití sufixových stromů
Chlubna, Pavel ; Hynek, Jiří (oponent) ; Burgetová, Ivana (vedoucí práce)
Tato práce pojednává o struktuře sufixových stromů, jejich implementaci a problematice, kterou pomocí sufixových stromů řešíme. Práce se také zaměřuje na konstrukci sufixového stromu, pomocí Ukkonenova algoritmu. Kromě samotné implementace se práce také zabývá porovnáním jiných používaných algoritmů se sufixovými stromu, z hlediska časové náročnosti. Výstupem této práce je ucelená aplikace s grafickým rozhraním, která demonstruje využití sufixových stromů při řešení různých problematik a nabízí porovnání této struktury s jinými algoritmy.
|
|
|
Suffix Graphs and Lossless Data Compression
Senft, Martin ; Dvořák, Tomáš (vedoucí práce) ; Dvorský, Jiří (oponent) ; Smyth, William F. (oponent)
Název práce: Sufixové grafy a bezeztrátová komprese dat Autor: Martin Senft Katedra: Katedra software a výuky informatiky Vedoucí doktorské práce: doc. RNDr. Tomáš Dvorˇák, CSc., Katedra software a výuky informatiky Abstrakt: Sufixový strom a prˇíbuzné datové struktury umožnˇují asymptoticky optimálneˇ rěšit rˇadu úloh o rětežcích a jejich vlastností lze též využít k imple- mentacimetodbezztrátovékompresedat. Cílemprácejeprozkoumatmožnosti opacňéhoprˇístupu,tedy využití vlastností sufixovýchgrafu˚ k návrhukompres- ních algoritmu˚. Práce popisuje univerzální konstrukcňí algoritmus pro sufixo- vý trie,sufixový strom,DAWGa CDAWG,doprovázený analýzousimulaceim- plicitních sufixových hran, která prˇináší dveˇ praktické alternativy k tradicňímu rěšení. Protožekompresnímetody vyžadují udržování textuvposuvnémokneˇ, je trěba rozebrat chování sufixových grafu˚ v této situaci. V práci je oveřěno, že pouze sufixový strom je schopen udržovat posuvné okno v amortizovaneˇ kon- stantním cˇase, zatímco CDAWG (podobneˇ jako DAWG) vyžaduje cˇas úmeřný délce okna, což rěší hypotézu Inenagy a kol. Na tomto základeˇ je popsána trˇí- da kompresních algoritmu˚, založených pouze na popisu konstrukce sufixové- ho grafu nad komprimovaným textem. Zatímco neˇkteré z algoritmu˚ odpoví- dají klasickým slovníkovým cˇi kontextovým...
|
|
|
Suffix tree construction with minimized branching
Bašista, Peter ; Dvořák, Tomáš (vedoucí práce) ; Kadlec, Rudolf (oponent)
Sufixový strom je datová struktura, která v textu umožňuje rychle vykonávat operace podobné vyhledávání. Aby ji bylo možné používat efektivně, musí být vytvořená rychle. V této práci se zaměříme na nový způsob simulace sufixových hran nazývaný "minimalizace větvení", který se snaží zvýšit rychlost konstrukce sufixového stromu pomocí znížení počtu větvícich operací. Naš hlavní cíl je předvést porovnání současných metod pro konstrukci sufixového stromu a poukázat na některé výhody a nevýhody jednotlivých postupů. Představíme, implementujeme a prakticky posoudíme několik variant standardních algoritmů jako jsou McCreightův a Ukkonenův, stejně tak jako algoritmu PWOTD, který byl původně navržen pro diskově orientovanou konstrukci. Náším hlavním výsledkem je ucelený popis a implementace těchto algoritmů, na kterých se dá dále stavět. Také předložíme jednoduchá doporučení ohledně toho kdy je vhodné použít konkrétní algoritmus a proč.
|
|
|
Konstrukce sufixových stromů a jejich využití v bioinformatice
Hlaváček, Pavel ; Čermák, Martin (oponent) ; Martínek, Tomáš (vedoucí práce)
Práce se zabývá problematikou implementace sufixových stromů a jejich využití v bioinformatice. Jsou zde uvedeny různé druhy algoritmů pro tvorbu sufixových stromů. Především se zabývá implementací on-line metody pro tvorbu sufixového stromu navrženou E. Ukkonenem a přibližným vyhledáváním podřetězců. To je realizováno za pomoci dynamického programování, upraveného pro využití sufixových stromů. Obě tyto metody jsou popsány pseudokódem a implementovány v příloze práce.
|
|
|
Vyhledávání přibližných palindromů v DNA sekvencích
Remiáš, Richard ; Burgetová, Ivana (oponent) ; Martínek, Tomáš (vedoucí práce)
Práca sa zaoberá problematikou vyhľadávania presných a približných palindrómov. V súvislosti s vyhľadávaním presných palindrómov analyzuje naivný postup vyhľadávania ako aj postupy založené na sufixových stromoch, ktorých konštrukcia je tiež rozobraná. Vyhľadávanie približných palindrómov je realizované za pomoci princípov dynamického programovania. Samotné vyhľadávanie je rozdelené na tri časti: vyhľadanie palindrómov, filtrácia výsledkov a ich rekonštrukcia. Každá časť je popísaná algoritmom a implementovaná programom v prílohe práce.
|
host ::
RSS.