Název:
Konstrukce sufixových polí a jejich využití v bioinformatice
Překlad názvu:
Suffix Arrays Construction and Their Use in Bioinformatics
Autoři:
Hlávka, Ondřej ; Čermák, Martin (oponent) ; Martínek, Tomáš (vedoucí práce) Typ dokumentu: Bakalářské práce
Rok:
2011
Jazyk:
cze
Nakladatel: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstrakt: [cze][eng]
Práce pojednává o perspektivní datové struktuře, která se nazývá sufixové pole. Tato datová struktura je zde podrobněji popsána a v práci je dále uvedeno rozdělení algoritmů pro konstrukci tohoto pole. Je zde popsáno několik konstrukčních algoritmů a nejpodrobněji se práce zaobírá algoritmem nazývaným qsufsort. Nakonec si ukážeme využití sufixového pole pro vyhledávání přesných (pomocí binárního vyhledávání) a přibližných (metoda QUASAR) vzorů v sekvencích DNA.
This work describes perspective data structure called suffix array. This data structure is described in more detail and this paper also contains taxonomy of suffix array construction algorithms. A few algorithms are described more precisely and most space is devoted to algorithm called qsufsort. Finally we will show how can be suffix array used in practice. This work shows usage of suffix array in exact (binary search) and approximate (QUASAR) string matching in DNA sequences.
Klíčová slova:
přesné vyhledávání; přibližné vyhledávání; qsufsort; QUASAR; sufix; Sufixové pole; approximate matching; exact matching; qsufsort; QUASAR; suffix; Suffix array
Instituce: Vysoké učení technické v Brně
(web)
Informace o dostupnosti dokumentu:
Plný text je dostupný v Digitální knihovně VUT. Původní záznam: http://hdl.handle.net/11012/55673