| 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.
|
|---|