Meno:Jakub
Priezvisko:Kováč
Názov:Kompresia genómu za pomoci skrytých Markovovských modelov
Vedúci:Mgr. Tomáš Vinař, PhD.
Rok:2012
Kľúčové slová:kompresia, DNA, HMM, aritmetické kódovanie, genóm
Abstrakt: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.

Súbory bakalárskej práce:

main.pdf
priloha-jmk.zip