Original title: Automatové techniky v analýze DNA
Translated title: Automata techniques in DNA analysis
Authors: Klímová, Lucie ; Síč, Juraj (referee) ; Holík, Lukáš (advisor)
Document type: Bachelor's theses
Year: 2025
Language: eng
Publisher: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstract: [eng] [cze]
Tato práce se zaměřuje na možnosti využití konečných automatů pro zrychlení detekce strukturních domén transpozonů. Hlavní část práce představuje metodu založenou na deterministických konečných automatech (DFA) jako rychlejší alternativu k nástroji BLASTX. Ten je využíván v rámci nástroje TE-greedy-nester, který slouží k detekci LTR retrotranspozonů. Jako výchozí bod byl využit nástroj HMMER, který velice přesně modeluje charakter hledané sekvence pomocí profilových skrytých Markovových modelů (PHMM). Vzhledem k vysoké míře nedeterminismu PHMM nebylo možné přímo vytvořit jeden deterministický model pro celou doménu. Místo toho byl navržen přístup, který PHMM transformuje na několik menších DFA navržených pro detekci podčástí domény. Blízké výskyty těchto podčástí pak indikují přítomnost celé domény. Výsledky testování ukázaly, že tento přístup zachovává vysokou přesnost a zároveň přináší až desetinásobné zrychlení vyhledávání oproti BLASTX. This thesis is focused on the possibilities of using finite automata to accelerate the detection of structural domains of transposons. The central part of the thesis introduces a method based on deterministic finite automata (DFA) as a faster alternative to the BLASTX tool. BLASTX is used by the TE-greedy-nester tool, which is designed to detect LTR retrotransposons. As a starting point, we used the HMMER tool, which uses a profile hidden Markov model (PHMM) to precisely describe the character of the searched sequence. Due to the significant nondeterminism of PHMMs, the determinization of the model of the entire domain proved unfeasible. Instead, a method to transform a PHMM into several smaller DFAs designed to detect domain subsequences was introduced. Closely located occurrences of these subsequences are subsequently interpreted as occurrences of the entire domain. The experimental evaluation demonstrated that the presented approach maintains high accuracy while achieving up to a tenfold search speedup compared to BLASTX.
Keywords: deterministické konečné automaty (DFA); LTR retrotranspozony; profilové skryté Markovovy modely (PHMM); deterministic finite automata (DFA); LTR retrotransposons; profile hidden Markov models (PHMM)

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/252797

Permalink: http://www.nusl.cz/ntk/nusl-682244


The record appears in these collections:
Universities and colleges > Public universities > Brno University of Technology
Academic theses (ETDs) > Bachelor's theses