prof. Ing. Jan Holub, Ph.D.

Závěrečné práce

Dizertační práce

Indexování dat pro Bioinformatiku

Stupeň
Téma dizertační práce
Popis tématu

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.

Komprese textů v přirozeném jazyce

Stupeň
Téma dizertační práce
Popis tématu

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.

Komprese XML dat

Stupeň
Téma dizertační práce
Popis tématu

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.

Diplomové práce

Inkrementální komprese založená na clusterování

Autor
Luboš Krčál
Rok
2014
Typ
Diplomová práce
Vedoucí
prof. Ing. Jan Holub, Ph.D.
Oponenti
Ing. Jan Trávníček, Ph.D.

Přibližné vyhledávání nad vlastními indexy

Autor
Lukáš Hrbek
Rok
2015
Typ
Diplomová práce
Vedoucí
prof. Ing. Jan Holub, Ph.D.
Oponenti
Ing. Petr Procházka, Ph.D.
Anotace
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ší.

Komprese přirozeného českého textu

Autor
Jan Navara
Rok
2017
Typ
Diplomová práce
Vedoucí
prof. Ing. Jan Holub, Ph.D.
Oponenti
Ing. Petr Procházka, Ph.D.
Anotace
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.

Použití LZW pro kompresi a indexaci velmi podobných řetězců

Autor
Ondřej Perutka
Rok
2015
Typ
Diplomová práce
Vedoucí
prof. Ing. Jan Holub, Ph.D.
Oponenti
Ing. Petr Procházka, Ph.D.
Anotace
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.

Kompresní metoda PPM využívající de Bruijnovy grafy

Autor
Jakub Kulík
Rok
2019
Typ
Diplomová práce
Vedoucí
prof. Ing. Jan Holub, Ph.D.
Oponenti
Ing. Petr Procházka, Ph.D.
Anotace
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.

Komprese souborů s notovými zápisy

Autor
Jan Baier
Rok
2012
Typ
Diplomová práce
Vedoucí
prof. Ing. Jan Holub, Ph.D.
Oponenti
Ing. Miroslav Balík, Ph.D.

Vyhledávání CRISPR segmentů využívající self-index

Autor
Ondřej Cvacho
Rok
2016
Typ
Diplomová práce
Vedoucí
prof. Ing. Jan Holub, Ph.D.
Oponenti
Ing. Petr Procházka, Ph.D.
Anotace
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.

Bioinformatický indexovací nástroj pro vyhledávání v elastických degenerativních řetězcích

Autor
Dominika Draesslerová
Rok
2023
Typ
Diplomová práce
Vedoucí
prof. Ing. Jan Holub, Ph.D.
Oponenti
Ing. Luboš Krčál, Ph.D.
Anotace
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.

Paralelní bezeztrátová komprese dat

Autor
Ondřej Fiedler
Rok
2016
Typ
Diplomová práce
Vedoucí
prof. Ing. Jan Holub, Ph.D.
Oponenti
doc. Ing. Ivan Šimeček, Ph.D.
Anotace
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í.