prof. Ing. Jan Holub, Ph.D.

Levná technologie pro sekvenování genomu odstartovala obrovský nárůst dat, která je potřeba uložit a zpracovat. Takto obrovský objem dat je potřeba pro personalizovanou medicínu, pro výzkum pangenomu nebo pro hledání biomarkerů pro různé nemoci. Tradiční indexy umožňující efektivní vyhledávání tentokrát selhávají kvůli překročení dostupné paměti. Také nevyužívají důležitou vlastnost vysoké podobnosti sekvencí lidského genomu.

Poslední vývoj v oblasti stringologie přinesl různé komprimované indexy založené na Burrows-Wheelerově transformaci. Cílem projektu je nalézt efektivnější metody pro ukládání a indexování dat pro různé úlohy v bioinformatice.

Claude Shannon provedl experiment v roce 1951 a dospěl k závěru, že entropie anglického textu je 0,6-1,3 bitů na znak. Model takového experimentu zahrnuje znalost anglické gramatiky, anglické slovní zásoby a nejběžnějších anglických frází.

Cílem práce je zvýšit efektivitu komprese textů přirozeného jazyka pomocí relaxace výše uvedeného modelu. Několik fází analýzy přirozeného jazyka bude použito jak k porozumění textu, tak k efektivnější kompresi textu.

Datový formát XML byl zaveden před mnoha lety a dnes je široce používán jako defacto standard pro reprezentaci a výměnu dat přes WWW. Bylo vyvinuto mnoho technik komprese XML. Některé neumožňují dotazy bez dekomprese celého XML dokumentu, některé ano. Nejnovější vývoj ve stringologii nám však přinesl rychlé a komprimované datové struktury pro ukládání dat na základě Burrows-Wheelerovy transformace. Cílem dizertační práce je nalézt efektivnější metody pro ukládání a dotazování dat ve formátu XML. Tyto metody by měly zachovat snadný a rychlý přístup k uloženým datům a zároveň zlepšit složitost paměti.

prof. Ing. Jan Holub, Ph.D.

Ing. Miroslav Balík, Ph.D.

Katedra teoretické informatiky

prof. Ing. Jan Holub, Ph.D.

Ing. Jan Trávníček, Ph.D.

Katedra teoretické informatiky

prof. Ing. Jan Holub, Ph.D.

Ing. Petr Procházka, Ph.D.

Katedra teoretické informatiky

Práce se zaměřuje na přibližné vyhledávání s nejvýše k chybami. Chyby jsou definovány s využitím Levenshteinovy vzdálenosti. Pro řešení této úlohy jsem navrhl filtrační algoritmus založený na pigeonhole principu. Prohledávaný text se předpokládá velký, implementovaný algoritmus proto používá FM-Index. Program je na poli vyhledávání v DNA srovnán s nástrojem BLAST. Experimenty ukázaly, že v některých aspektech je má implementace lepší.

Práce na DSpace

prof. Ing. Jan Holub, Ph.D.

Ing. Petr Procházka, Ph.D.

Katedra teoretické informatiky

Tato práce se zabývá vývojem nové kompresní metody založené na LZW a zarovnání řetězců. Algoritmus je pojmenován ALZW a je navržen pro kompresi velmi podobných řetězců. Daná množina řetězců je komprimována pomocí předem určeného referenčního řetězce. V porovnání s podobně zaměřeným RLZ a všeobecně použitelným GZipem umožňuje ALZW velmi rychlou kompresi a pro podobné genetické sekvence dosahuje dobrých kompresních poměrů. V případě lidského chromozomu 20 dosahuje algoritmus dokonce lepších výsledků, něž podobně zaměřený algoritmus RLZ.

Práce na DSpace

prof. Ing. Jan Holub, Ph.D.

doc. Ing. Ivan Šimeček, Ph.D.

Katedra teoretické informatiky

Tato práce se zabývá paralelní bezeztrátovou kompresí dat se zaměřením na využití výpočtů na grafické kartě. Uvádí čtenáře do problematiky datové komprese a do problematiky architektur a technologií pro paralelní výpočty. Zkoumá existující řešení pro paralelní bezeztrátovou kompresi včetně algoritmů určených pro grafické karty. Hlavním přínosem této práce je nová implementace PMLZSS, což je slovníková kompresní metoda pro grafické karty založená na LZSS, kterou v roce 2015 navrhli Bin Zhou, Hai Jin a Ran Zheng. Jsou popsána a vyhodnocena navržená technologická a algoritmická vylepšení. Práce experimentálně porovnává vytvořenou implementaci PMLZSS se sekvenční implementací LZSS a existujícími paralelními řešeními pro vícejádrové procesory a grafické karty. PMLZSS byla na testovaných datech 9,4krát až 22krát rychlejší než sekvenční verze. Pro soubory z několika kategorií dosáhla implementace PMLZSS z testovaných řešení nejvyšší rychlosti zpracování.

prof. Ing. Jan Holub, Ph.D.

Ing. Petr Procházka, Ph.D.

Katedra teoretické informatiky

V rámci práce byly navrženy a implementovány 4 algoritmy pro bezeztrátovou kompresi přirozeného českého textu využívající lemmatizátor, morfologický tagger a morfologický generátor obsažený v softwaru MorphoDiTa. První z algoritmů je založen na ukládání lemmat jednotlivých slov a generování slovních tvarů, druhý modeluje pravděpodobnosti jednotlivých slov na základě uložené informace o jejich slovním druhu, třetí modeluje pravděpodobnosti slov na základě slovního druhu předchozího slova a čtvrtý je rozšířením prvního, kdy jsou společně s lemmaty ukládány i některé části tagu. Výsledné kompresní poměry byly porovnány s kompresními poměry dosaženými referenčním algoritmem základní slovní komprese. Z porovnání vyplynulo, že druhý a třetí popsaný algoritmus zlepšení nepřináší, zatímco první a čtvrtý algoritmus dokáže kompresní poměr při vhodných konfiguracích zlepšit, typicky v řádu desetin procenta. Hlavním přínosem práce je důkaz, že použití lingvistických nástrojů může být při kompresi českých textů z hlediska kompresního poměru výhodné. Významným vedlejším produktem práce je široce použitelná implementace adaptivní verze kompresního algoritmu PPM, na níž jsou výše popsané algoritmy založeny.

Práce na DSpace

prof. Ing. Jan Holub, Ph.D.

Ing. Petr Procházka, Ph.D.

Katedra teoretické informatiky

Práce se zaměřuje na využití kompaktních datových struktur v hledání CRISPR segmentů za použití self-indexů. Hledání CRISPR segmentů je srovnatelné s přibližným vyhledáváním řetězce za pomoci generování a vyhledávání všech podobných segmentů s možnou chybou až m. Navržené řešení se snaží redukovat takovou množinu všech podobných řetězců za použití De Bruijnových grafů. Experimentální vyhodnocení prokázalo možnost redukce až o čtyřnásobek.

Práce na DSpace

prof. Ing. Jan Holub, Ph.D.

Ing. Petr Procházka, Ph.D.

Katedra teoretické informatiky

Tato práce pojednavá o odlišném přístupu k PPM kompresnímu algoritmu založeném na succinct de Bruijnových grafech. Využívá dynamické binární vektory a waveletové stromy sloučené do jediného stromu pro vytvoření vysoce výkonné dynamické succinct datové struktury schopné reprezentovat grafy používané kompresorem. Přestože je algorithmus pomalý ve srovnání s ostatními běžně užívanými kompresory, dosahuje dobrých kompresních poměrů při využití výrazně menšího množství paměti.

Práce na DSpace

prof. Ing. Jan Holub, Ph.D.

Ing. Luboš Krčál, Ph.D.

Katedra teoretické informatiky

Schopnost efektivně prohledávat veliké množství dat je důležitou součástí nejen v bioinformatické a informatické sféře, ale v celém moderním světe. Každý organismus je originální a vytvořit komplexní strukturu, která by vhodně reprezentovala genomy a jeho varianty a uměla s nimi efektivně pracovat, je hlavním směrem pangenomického výzkumu. V této práci diskutujeme a implementujeme poměrně nový algoritmus zvaný BIO-FMI, který má potenciál k tomu efektivně komprimovat a vyhledávat nad množinou vysoce repetitivních dat, jako jsou právě DNA sequence. V současné době je způsob ukládání nevyhovující vzhledem k postavení vůči jednomu referenčnímu genomu a hledají se alternativní řešení. Tato práce se zabývá modifikací algoritmu BIO-FMI na formát elastických degenerovaných řetězců (EDS), které jsou kandidátními reprezentanty pro ukládání variant. Práce ukazuje slibné výsledky v rychlosti sestavení indexu, variabilitě nastavení a porovnává je s dalšími algoritmy z této oblasti, kterými jsou LZ-RLBWT a r-index.

Práce na DSpace