Metode izgradnje polja najduljih zajedničkih prefiksa niza

undergraduate thesis

• Title (english): Methods for the longest common prefix array construction
• Author: Marko Mesarić
• Mentor: Mirjana Domazet-Lošo (mentor)
• Committee member: Mirjana Domazet-Lošo (predsjednik povjerenstva)
• Committee member: Zdravko Galić (član povjerenstva)
• Committee member: Boris Milašinović (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2018-07-13, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

U okviru ovog završnog rada obrađene su strukture podataka koje se često koriste u bioinformatici: sufiksno polje, polje najduljih zajedničkih prefiksa (LCP polje) i Burrows-Wheelerova transformacija znakovnog niza. Analizirane su različite metode izgradnje LCP i BWT polja s posebnim osvrtom na nedavno objavljeni algoritam u kojemu je dodatni memorijski prostor za izgradnju LCP polja O(1). Algoritmi za izgradnju BWT i LCP polja implementirani su u programskom jeziku C++. Uspoređene su različite metode izgradnje LCP polja prema vremenu izvođenja i memorijskoj potrošnji te su potom i uspoređena s postojećim programskim rješenjima.

Abstract (english)

In this thesis I present data structures commonly used in the field of bioinformatics: the suffix array, the longest common prefix array and the Burrows-Wheeler transformation. Analysis of different methods of the LCP and the BWT construction is shown with a focus on recently published algorithm, which builds LCP array using O(1) extra memory space and runs in O(n2) time. All algorithms featured in this work are implemented in C++. The analysis include memory and time comparison of the underlying implementations.

• Keywords: polje najduljih zajedničkih prefiksa niza; algoritmi indeksiranja teksta; Burrows-Wheelerova transformacija; sufiksno polje
• Keywords (english): longest common prefix array; text indexing algorithms; Burrows-Wheeler transformation; suffix array
• Language: croatian
• URN:NBN: urn:nbn:hr:168:344397
• Study programme: Title: Computing; Study programme type: university; Study level: undergraduate; Academic / professional title: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2019-03-13 22:58:40