prof. Ing. Bořivoj Melichar, DrSc.

Projekty

Algoritmy pro Next-Generation Sequencers

Program
Studentská grantová soutěž ČVUT
Poskytovatel
Jiný tuzemský poskytovatel
Kód
SGS11/082/OHK3/1T/18
Období
2011
Popis
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

Vyhledávání a indexování stromových datových struktur

Program
Studentská grantová soutěž ČVUT
Poskytovatel
Jiný tuzemský poskytovatel
Kód
SGS12/092/OHK3/1T/18
Období
2012
Popis
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ů. Příkladem aplikací stromů může být optimalizace abstraktních syntaktických stromů při kompilaci, přepisování termů, mechanické provádění důkazů, hledání v fylogenetických stromech, indexování sekundární struktury RNA, hledání v XML dokumentech a vyhodnocování zdrojového kódu funkcionálních jazyků. Proto jsme založili novou výzkumnou disciplínu, Arbologii, odnož Stringologie, která se zabývá stromovými strukturami. Používáme zásobníkového automatu jako výpočetního modelu, jelikož lineární zápisy stromů jsou generovány bezkontextovými gramatikami a tudíž jsou bezkontextovými jazyky. 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

Vyhledávání ve stromech

Program
Studentská grantová soutěž ČVUT
Poskytovatel
Jiný tuzemský poskytovatel
Kód
SGS10/225/OHK3/2T/18
Období
2010 - 2011
Popis
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ů. Příkladem aplikací stromů může být optimalizace abstraktních syntaktických stromů při kompilaci, přepisování termů, mechanické provádění důkazů, hledání v fylogenetických stromech, indexování sekundární struktury RNA, hledání v XML dokumentech a vyhodnocování zdrojového kódu funkcionálních jazyků. Proto jsme založili novou výzkumnou disciplínu, Arbologii, odnož Stringologie, která se zabývá stromovými strukturami. Používáme zásobníkového automatu jako výpočetního modelu, jelikož lineární zápisy stromů jsou generovány bezkontextovými gramatikami a tudíž jsou bezkontextovými jazyky. 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