Computational Biology
@ Comenius University in Bratislava

Jakub Kováč (ml). Kompresia genómu za pomoci skrytých Markovovských modelov. Bachelor thesis, Comenius University in Bratislava, 2012. Supervised by Tomáš Vinař.

Download preprint: 12jmkth.pdf, 499Kb

Download from publisher: not available

Related web page: not available

Bibliography entry: BibTeX

Abstract:

Kompresia vznikla ako odpoveď na efektívne uchovávanie dát a tiež na 
urýchlenie prenosu informácie na sieťach s pomalým tokom dát. Vzniklo 
viacero algoritmov bezstratovej kompresie dát, či už všeobecných alebo 
určených pre konkrétny typ dát. S rozvojom genetiky sa objavil úplne nový 
typ dát hovoriaci o poradí báz v kyseline deoxyribonukleovej (sekvencie 
DNA). Tieto dáta nie je možné komprimovať bežne používanými všeobecnými 
algoritmami. Naše riešenie problému kompresie DNA je založené na použití 
aritmetického kódovania so skrytým Markovovským modelom (HMM) ako 
adaptívnym modelom zdroja. Po implementovaní programu sme na sekvencii DNA 
natrénovali niekoľko HMM, ktorými sme modelovali rôzne vlastnosti 
sekvencie DNA. Následne sme týmito modelmi komprimovali inú sekvenciu DNA. 
Na rozdiel od všeobecných komprimačných algoritmov, pri ktorých mala 
komprimovaná sekvencia väčšiu veľkosť ako nekomprimovaná sa nám podarilo 
dosiahnuť nepatrné zlepšenie aj oproti priamočiaremu zakódovaniu každej 
bázy dvomi bitmi. Otvorenou otázkou ostáva hľadanie vhodnejších HMM 
sekvencie DNA a aký je najlepší kopresný pomer dosiahnuteľný touto 
metódou. Tu treba mať na zreteli, že zväčšenie a spresnenie použitého HMM 
spomaľuje kompresiu a následnú dekompresiu DNA.