Original title:
Komprese DNA sekvencí
Translated title:
DNA Sequence Compression
Authors:
Friedrich, Tomáš ; Burgetová, Ivana (referee) ; Martínek, Tomáš (advisor) Document type: Master’s theses
Year:
2010
Language:
cze Publisher:
Vysoké učení technické v Brně. Fakulta informačních technologií Abstract:
[cze][eng]
Vzrůstající objem biologických dat vyžaduje hledání nových způsobů uložení těchto dat v genetických bankách. Cílem této práce je navržení a implementace nového algoritmu pro kompresi DNA sekvencí, který je založen na porovnání DNA sekvencí s referenčním modelem a následném uložení rozdílů oproti danému referenčnímu modelu. Práce obsahuje základní znalosti z molekulární biologie potřebné k pochopení principu algoritmu. Dále vysvětluje problematiku zarovnávání a uvádí některé kompresní algoritmy vhodné pro uložení rozdílů oproti referenčnímu modelu. Práce pokračuje popisem implementace algoritmu, která je následována odvozením časové složitosti a porovnáním s již existujícími přístupy. Na závěr je diskutována možnost dalšího pokračování projektu.
The increasing volume of biological data requires finding new ways to save these data in genetic banks. The target of this work is design and implementation of a novel algorithm for compression of DNA sequences. The algorithm is based on aligning DNA sequences agains a reference sequence and storing only diferencies between sequence and reference model. The work contains basic prerequisities from molecular biology which are needed for understanding of algorithm details. Next aligment algorithms and common compress schemes suitable for storing of diferencies agains reference sequence are described. The work continues with a description of implementation, which is follewed by derivation of time and space complexity and comparison with common compression algorithms. Further continuation of this thesis is discussed in conclusion.
Keywords:
automata.; complexity; compresion algorithms; compression; DNA; fixed codes; huffman coding; Java; proteins; reference model; automat.; bílkoviny; DNA; fixní kódy; huffmanovo kódování; Java; komprese; kompresní algoritmy; referenční model; složitost
Institution: Brno University of Technology
(web)
Document availability information: Fulltext is available in the Brno University of Technology Digital Library. Original record: http://hdl.handle.net/11012/54365