prof. Ing. Jan Holub, Ph.D.

2011

Sekvencovací technologie urazily velký kus cesty od dob, kdy první zmapování lidského genomu zabralo laboratořím po celém světě více než deset let práce. Dnes, díky technologiím next-generation sequencing (NGS), zabere sekvencování genomu čas v řádu dnů či hodin a cena procesu se snížila o několik řádů. To z NGS činí dostupnou techniku pro experimenty v mnoha laboratořích. Dostupnost sekvencování neustále narůstá. Vzhledem k tomu, že každé sekvencování znamená ohromné množství zpracovaných dat, může trend snižování ceny a času sekvencování pokračovat jedině za pomoci nových, lepších algoritmů pro sestavování genomů z milionů krátkých sekvencí (reads). Návrh těchto algoritmů je úkolem computer science. Potřeba efektivnějších metod mapování reads na genom byla poprvé adresována v roce 2002, kdy byl modifikován algoritmus BLAST tím, že začaly být používány referenční vzorky. První opravdu rychlý a efektivní mapovací software byl ELAND, systém dodávaný společně s Illumina GA pipeline. Tent

2009 - 2011

Informační společnost používá výsledky vyhledávání každý den a jejich význam stále roste. Vyhledávání již není omezeno na obyčejné texty. Vyžaduje se vyhledávání ve složitějších strukturách jako jsou stromy (datové struktury pro XML), 2D obrázky nebo komprimovaná data. Navrhovaný projekt si klade za cíl nejen rozšířit naše výsledky v oblasti stringologie, ale také využít naše znalosti v relativně novém oboru vyhledávajícím ve stromech, který jsme nazvali arborologie. Ve stringologii bychom rádi pokračovali v tématech jako vícerozměrné vyhledávání, hledání pravidelností v textu, vyhledávání v zobecněných řetězcích a paralelní vyhledávání. V oblasti komprese dat jsme vyvinuli algoritmy vyhledávající v komprimovaném textu. Chceme zlepšit naše současné výsledky a zaměřit se také na přibližné vyhledávání v komprimovaných datech.

2019 - 2020

Index je způsob jak výrazně urychlit vyhledávání v datech, která máme k dispozici dopředu. Vytvořený index umožňuje vyhledávat vzorek v čase závislém na délce vzorku a počtu jeho výskytů. Cílem projektu je vyvinout nové algoritmy a datové struktury pro oblasti zpracovávající velká množství dat (DNA/RNA sekvence) umožňující složitější úlohy typu vyhledávání degenerativního či elastického vzorku. Přes existenci pokročilých technik pro indexu pro řetězce, stále existují výzvy v podobě speciálních typů úloh pro indexování velmi podobných řetězců (např. genomy jedinců stejného druhu), kde klasické indexační metody selhávají. Dále budou vyvinuty i metody pro online vyhledávání elastických vzorků.

2010 - 2012

Projekt si klade za cíl návrh a implementaci nových metod komprese dat. Kontextové metody jsou součástí bezeztrátových kompresních metod, které umožňují získat z komprimovaných dat původní, identické informace. Tyto metody jsou založeny na podobnostech v kódovaných datech. Hlavní směr výzkumu je dnes zaměřen k slovním kontextovým metodám a s nimi spojeným transformacím. Slovní metody přinášejí rychlejší adaptivitu ke komprimovaným datům, při čemž využívají striktně definovaných struktur především přirozených či formálních jazyků, čímž dosahují lepší kompresní poměr ve srovnání s ostatními metodami. Cílem projektu je využít uvedených možností při návrhu nových metod pro kompresi přirozených jazyků, které budou disponovat kompresním poměrem lepším či srovnatelným s nejlepšími současnými metodami komprese dat. Zároveň se projekt chce zaměřit na návrh metod s vyváženým kompresním poměrem a časovou výpočetní náročností. Dalším cílem projektu je dokončení projektu knihovny ExCom (Extensib

2013

Pro ukládání, indexování a další zpracování velkého množství dat je zapotřebí využívat speciálních datových struktur. Pro hierarchickou organizaci dat je takovou typickou strukturou strom. Pro indexování, čtení a další zpracování dat v nich uložených je zapotřebí specializovaných algoritmů. Cílem tohoto výzkumu je navrhnout efektivní a snadno pochopitelné algoritmy cílené na vyhledávání (přesné i přibližné) a indexování ve stromech, a poté poskytnout jejich implementaci. Projekt si dále klade za cíl návrh a implementaci nových metod komprese dat ve dvou hlavních směrech: komprese notových zápisů a komprese textů přirozených jazyků.

2013 - 2015

Projekt se zabývá výzkumem čtyř relativně úzce propojených oblastí: arbologií, kompresí přirozených jazyků a vybranými tématy ze stringologie a bioinformatiky. V oblasti arbologie zkoumáme nové indexovací a vyhledávací algoritmy na stromech. V bioinformatice pracujeme na řešení rychlého mapování miliónů krátkých sekvencí na DNA řetězec a indexování DNA řetězců. V oblasti komprese dat se zaměřujeme na výkonné algoritmy pro rychlou kompresi a dekompresi textu přirozeného jazyka a algoritmy pro rychlé vyhledávání v komprimovaném textu. Ve stringologii pracujeme na indexování 2D textu a na algoritmech pro identifikaci opsaných textů a zdrojových kódů, které mohou být navíc komprimované.