Original title:
Konstrukce sufixových polí a jejich využití v bioinformatice
Translated title:
Suffix Arrays Construction and Their Use in Bioinformatics
Authors:
Hlávka, Ondřej ; Čermák, Martin (referee) ; Martínek, Tomáš (advisor) Document type: Bachelor's theses
Year:
2011
Language:
cze Publisher:
Vysoké učení technické v Brně. Fakulta informačních technologií Abstract:
[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.
Keywords:
approximate matching; exact matching; qsufsort; QUASAR; suffix; Suffix array; přesné vyhledávání; přibližné vyhledávání; qsufsort; QUASAR; sufix; Sufixové pole
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/55673