Original title:
Klasifikace biologických sekvencí s využitím bezeztrátové komprese
Translated title:
Biological sequence classification utilizing lossless data compression algorithms
Authors:
Kruml, Ondřej ; Provazník, Ivo (referee) ; Škutková, Helena (advisor) Document type: Master’s theses
Year:
2016
Language:
eng Publisher:
Vysoké učení technické v Brně. Fakulta elektrotechniky a komunikačních technologií Abstract:
[eng][cze]
Tato diplomová práce se zabývá možností využití bezeztrátových kompresních algoritmů ke klasifikaci biologických sekvencí. Nejdříve je představena literární rešerše o bezeztrátových kompresních algoritmech, která byla využita k výběru slovníkového algoritmu vytvořeného A. Lempelem a J. Zivem v roce 1976 (LZ77). Tento algoritmus je běžně používán k datové kompresi a v předkládané práci byl modifikován tak, aby umožnil klasifikaci biologických sekvencí. K algoritmu byly navrženy další modifikace, které rozvíjí jeho klasifikační možnosti. V průběhu práce byla sestavena sada datasetů biologických sekvencí, která umožnila podrobné testování algoritmu. Algoritmus byl porovnán s klasickými zarovnávacími metodami: Jukes-Cantor, Tamura a Kimura. Bylo ukázáno, že algoritmus dosahuje srovnatelných výsledků v oblasti klasifikace biologických sekvencí a dokonce je u 20% datasetů překonává. Lepší výsledky dosahuje zejména u sekvencí, jež jsou si vzájemně vzdálené.
This master thesis is developing the idea of using lossless compression algorithms as a mean of classification of biological sequences. At first an overview of lossless data compression algorithms is presented, based on which the dictionary algorithm created by A. Lempel and J. Ziv in 1976 (LZ77) has been selected. This algorithm, that commonly serves for data compression, has been modified in order to enable the classification of biological sequences. Further modifications have been introduced to enhance the classification capabilities of the algorithm. Several datasets of biological sequences have been collected enabling a correct assessment of the LZ algorithm capability. The algorithm was compared to the classical alignment based methods: Jukes-Cantor, Tamura and Kimura. It has been proven that the algorithm has comparable results in the field of classification of biological sequences and even surpasses the alignment methods in 20% of the datasets. Best results are especially achieved with distant sequences.
Keywords:
Datová komprese; DNA; fylogenetika; klasifikace; Lempel-Ziv; LZ77; classification; Data compression; DNA; Lempel-Ziv; LZ77; phylogenetic
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/59960